Extras din referat

Alaturi de folosirea algoritmilor de calcul, pentru a rezolva o problema cu ajutorul calculatorului este necesara modelarea datelor specifice problemei cu ajutorul unor structuri de date. Acestea reprezinta modul de codificare/stocare a datelor in spatiul de memorie al masinii de calcul pe care se executa algoritmul precum si specificarea modului de a crea, modifica sau a avea acces la respectivele date.

O structura de date este compusa din urmatoarele trei componente:

- (1) o multime de operatii pentru manipularea tipurilor de date caracteristice obiectelor abstracte

- (2) o structura (spatiu in memorie) folosita pentru stocarea obiectelor abstracte

- (3) implementarea fiecarei operatii dintre cele specificate la (1) folosind ca suport structura de memorare specificata la (2).

Un tip de date abstracte (TDA) este o multime de operatii (abstracte) pentru manipularea unor obiecte abstracte (este vorba deci de prima componenta a definitiei unei structuri de date). TDA-ul nu contine nici o referire la modul de implementare a acestor operatii abstracte (i.e. la componentele (2) respectiv (3) ale definitiei unei structuri de date). Prin utilizarea tipurilor de date abstracte in dezvoltarea unei aplicatii de programare proiectantul poate gandi in termenii operatiilor abstracte, urmand ca implementarea efectiva a acestor operatii sa fie realizata ulterior. Modul de a realiza o aplicatie prin separarea algoritmului propriu-zis de structurile de date pe care acesta le utilizeaza se numeste abstractizarea datelor.

Folosirea tipurilor de date abstracte este strans legata de programarea modulara. Aceasta este o metoda de dezvoltare a unei aplicatii prin impartirea ei in mai multe module separate avand interfetele riguros specificate. Modulele pot fi proiectate, implementate, depanate separat si reutilizate in diferite aplicatii.

Evident, abstractizarea datelor se poate face la diferite nivele. Majoritatea limbajelor de programare au tipuri de date abstracte predefinite. De exemplu folosirea tipului de date int permite proiectantului unei aplicatii C sa gandeasca direct la nivelul operatiilor de adunare, scadere, inmultire, comparatie etc. fara a fi nevoit sa ia in considerare modul in care aceste operatii sunt efectiv implementate. Alte tipuri de date abstracte cum ar fi: lista, stiva, coada, multimea, graful, pot fi considerate plasate pe "nivele superioare" ale gandirii abstracte. Unii autori ([Aho 83]) considera ca tipurile de date abstracte sunt generalizari ale tipurilor de date primitive (cum ar fi tipul int) iar functiile/procedurile (vazute ca operatii abstracte) sunt generalizari ale operatiilor primitive (+, -, *, / etc.).

In continuare vom prezenta cateva tipuri de date abstracte utilizate adesea in problemele de geometrie algoritmica care sunt folosite in grafica pe calculator precum si modul de implementare a acestor TDA-uri. Implementarea este realizata in cazul unui spatiu de date bidimensional (i.e. datele geometrice sunt reprezentari ale unor obiecte situate in plan) dar sunt prezentate si TDA-uri folosite pentru datele 3D

1,1 Tipul de date abstracte punct (in spatiul 2D)

Un punct p in spatiul 2D este reprezentat printr-o pereche de numere reale (x,y), coordonatele carteziene ale punctului. Aceeasi reprezentare (Figura 2.1) poate fi data si vectorului de pozitie al lui p: rP=xi+yj unde x si y vor reprezenta proiectiile acestui vector pe axele de coordonate iar i si j sunt respectiv versorii (vectorii unitate) celor doua axe ale sistemului de coordonate carteziene asociat planului. De aceea unele din subiectele tratate in cursul acestui capitol se vor referi la vectori in spatiul 2D.

Operatiile fundamentale ce pot fi aplicate vectorilor sunt:

- adunarea a doi vectori:rP+rQ=(xP+xQ, yP+yQ)

- inmultirea unui vector cu un scalar: krP=(kxP, kyP)

- determinarea lungimii unui vector: ?rP?=(xP2+yP2)1/2

- normalizarea vectorului (i.e. determinarea unui versor cu aceeasi orientare):

- determinarea directiei unui vector (i.e. a unghiului (polar) pe care acesta il face cu semiaxa Ox pozitiva)

Operatiile abstracte ce corespund TDA-ului punct sunt:

- dif_p2d - decide daca doua puncte sunt sau nu diferite intre ele

- copy_p2d - copiaza un punct

- cons_p2d - construieste reprezentarea unui punct pornind de la coordonatele sale

- dfr_p2d - determina vectorul diferenta a vectorilor de pozitie (punctelor) asociati la doua puncte p1, p2 acest vector va avea aceeasi orientare cu vectorul care are originea in punctul p1 si varful (destinatia) in punctul p2

- lung_vec_poz - determina lungimea vectorului de pozitie asociat unui punct

- clasif_p2d_dr - stabileste pozitia unui punct in raport cu o dreapta determinata de alte doua puncte

- polar - determina directia (unghiul polar) vectorului de pozitie asociat unui punct

- afis_p2d - afiseaza punctul de pe ecran (coordonate intregi) situat cel mai aproape fata de un punct dat

Pentru implementarea acestor operatii fundamentale vom reprezenta punctul 2D sub forma unei structuri cu doua campuri:

typedefstruct p2d {

double x, y;

} punct, *rpunct;

Doua puncte p1, p2 se considera distincte, daca cel putin una dintre coordonatele lui p1 difera de coordonata corespunzatoare a lui p2 prin cel putin EPS. Deoarece coordonatele celor doua puncte pot rezulta prin procese care implica anumite erori de calcul, comparatiile coordonatelor nu se efectueaza direct prin intermediul operatorilor == sau != (O valoare tipica pentru constanta EPS este 1.0E-4)

int dif_p2d(rpunct p1, rpunct p2)

{ return (fabs(p1->x-p2->x)>EPS || fabs(p1->y-p2->y)>EPS); }

Functiile C pentru copierea unui punct si respectiv constructia unui punct pornind de la coordonatele sale sunt:

void copy_p2d(rpunct s, rpunct d)