STRUCTURI DE DATE

STRUCTURI DE DATE

Structura de date - se defineste ca o colectie de date intre care sa stabilit o serie de relatii care conduc la un anumit mecanism de selectie si identificare a componentelor. Componentele structurii pot fi individualizate si identificate prin nume sau prin pozitia pe care o ocupa structura.

Daca localizarea unei componente se face prin parcurgerea tuturor componentelor care se afla Inaintea sa in ordinea specificata, atunci structura are acces secvential.

Daca o componenta din structura poate fi selectata fara a tine seama de celelalte componente, atunci structura are acces direct.

Asupra unei structuri de date se pot efectua o multitudine de operatii care se pot referi atat la valori cat si la structura, cum ar fi:

creerea, respectiv numerotarea datelor in forma initiala pe suportul de memorie;

consultarea, respectiv accesul la componentele structurii in vederea prelucrarii valorilor;

actualizarea, respectiv schimbarea starii structurii prin adaugarea, stergerea unor elemente, modificarea valorii unor elemente, modificarea relatiilor dintre elemente;

sortarea, respectiv aranjarea elementelor unei structuri dupa anumite criterii;

fuzionarea, respectiv formarea unei structuri noi din doua sau mai multe structuri;

ventilarea, respectiv spargerea structurii in doua sau mai multe structuri;

copierea;

interclasarea.

Operatiile la care poate fi supusa o structura de date si eficienta cu care pot fi acestea realizate, depind in mare masura de relatiile intre datele materializate pe suportul de memorie.

Clasificarea structurilor de date se face in functie de mai multe criterii astfel:

dupa tipul componentelor pot fi:

- omogene, atunci cand componentele sunt de acelasi tip;

- eterogene, atunci cand componentele sunt de tipuri diferite;

dupa posibilitatea de descompunere in structuri de acelasi tip pot fi recursive sau nu;

dupa posibilitatea de modificare a valorilor si/sau a structurii pot fi:

- statice, care pe tot parcursul existentei lor au acelasi numar de componente in aceeasi ordine;

- dinamice, care permit modificarea valorilor si/sau structurii prin aplicarea operatorilor;

din punct de vedere al nivelului de structurare al datelor pot fi:

- logice, care se refera la modul de ordonare al datelor;

- fizice, care se refera la modul de implementare, de reprezentare efectiva pe suporti informationali.

Toate structurile de date care au aceeasi organizare si sunt supuse acelorasi operatii formeaza un anumit tip de structura de date.

Deci, un tip de structura de date este o multime ordonata de date, intre care s-au stabilit anumite relatii si pentru realizarea operatiilor se foloseste un grup de operatori de baza cu o anumita semantica.

Principalele tipuri de structuri logice de date sunt:

structura punctuala - care este reprezentata de o entitate grup izolata;

structura liniara - atunci cand intre elementele unei colectii de date exista o relatie de ordine totala, adica:

- orice element neterminal are un succesor imediat unic;

- primul element nu are predecesori;

- ultimul element nu are succesori;

- relatiile stabilite intre date sunt de tipul "1la 1";

a1 a2 a3 a4

Figura 3: Structura liniara simpla

a1 a2 a3 a4

Figura 4: Structura inelara

structura arborescenta - care se mai numeste ierarhica sau descendenta si se intalneste atunci cand intre elemente este o relatie de ordine cu urmatoarele proprietati:

- exista un element unic numit radacina arborelui;

- orice nod diferit de radacina are un predecesor imediat unic;

- orice nod neterminal are un numar finit de succesori imediati;

- relatiile stabilite intre noduri sunt de la 1 la m;

NOTA: Structura liniara si cea arborescenta sunt considerate structuri de baza din combinarea carora se pot construi structuri cat mai complexe.

a

b c

d e f

i j

Figura 5: Arbore binar

structura retea - atunci cand intre elementele unei colectii de date exista o relatie de preordine caracterizata de urmatoarele proprietati:

- o retea este un graf in care dintre doua noduri exista legaturi bidirectionale;

- un nod are mai multi predecesori si el insusi poate fi predecesor pentru propriul sau predecesor, putand aparea astfel in cicluri, adica drumuri in care nodul initial este acelasi cu nodul final;

b e i

f

a c j l m

g

d h k

Figura 6.a: Retea simpla cu nod de intrare si nod de iesire

c

d

f

Figura 6.b: Retea complexa

structura relationala - care este formata din mai multe tabele de date elementare, fara o legatura aparenta intre ele, componentele unei tabele fiind aduse intr-o forma normala. O forma normala este starea in care se afla structura unui tabel in functie de diferite cerinte impuse. Operatiile pe aceste structuri sunt realizate cu operatori relationari ai algebrei relationare sau ai calcului relationar.

Figura 7: Tabela de date