---

Structuri dinamice de date

---

Structurile dinamice de date sunt date structurate ale caror componente se aloca in mod dinamic.

Avantajul alocarii dinamice fata de alocarea acelorasi structuri de date in mod static (in segmentul de date) sau volatil (in segmentul de stiva) sunt:

- memorie suplimentara pentru programe

- posibilitatea de a utiliza aceasta memorie

Alocarea dinamica a componentelor structurii impune un mecanism prin care o noua componenta aparuta este legata in succesiune logica de corpul structurii deja format pana atunci. Rezulta ca fiecare componenta, pe langa informatia propriu-zisa pe care o detine, trebuie sa contina si o informatie de legatura cu componenta cu care se leaga logic in succesiune. Aceasta informatie de legatura va fi adresa componentei spre care se realizeaza succesiunea logica, iar mecanismul se mai numeste si alocare inlantuita dupa adrese.

In HEAP, structura respectiva va avea zone alocate componentelor sale in locurile gasite disponibile, care nu se succed intotdeauna in ordinea in care este realizata inlantuirea logica.

In functie de tipul inlantuirii realizate intre componente, exista urmatoarele tipuri de organizari:

- structuri liniare (de exeplu o lista care prelucreaza elevii care se inscriu la un examen)

o liste simplu inlantuite (liniare si circulare)

o liste dublu inlantuite (liniare si circulare)

- structuri arborescente (de exemplu reteaua ierarhica a angajatilor dintr-o firma)

- structuri retea (de exemplu o retea de orase care schimba materiale, combustibili etc)

Liste liniare simplu inlantuite

O componenta a unei liste simplu inlantuite se declara ca o data structurata de tip inregistrare, formata din doua campuri: informatia propriu-zisa (care poate fi de orice tip: numeric, caracter, pointer, tablou, inregistrare) si informatia de legatura (adresa la care e memorata urmatoarea componenta). Ultima componenta va avea informatia de legatura NULL, cu semnificatia ca dupa ea nu mai urmeaza nimic (retine adresa „nici o adresa” a urmatoarei componente).

Se poate defini un tip de date structurat numit nod, ale carui campuri le numim info si next.

De exemplu, pentru o lista de numere reale, putem defini:

struct nod

{float info;

nod *next;};

Componentele listei se vor aloca dinamic. Avem nevoie de o variabila statica sau locala cu ajutorul careia sa putem accesa primul element al listei. Fie acesta cap. Cu ajutorul ei putem accesa prima componenta, care contine o legatura catre ce-a de-a doua etc. Din aproape in aproape putem ajunge la ultimul element al listei.

nod *cap;

Referirea la informatia primului nod al listei se va face astfel:

cap->info

Referirea la adresa la care e memorat al doilea nod al listei se va face astfel:

cap->next

Referirea la informatia celui de-al nod al listei se va face astfel:

cap->next->info

Operatiile care se pot face utilizand liste simplu inlantuite sunt:

- crearea listei

- adaugarea unui element la inceputul listei

- adaugarea unui element la sfarsitul listei

- adaugarea unui element in interiorul listei

- stergerea elementului de la inceputul listei

- stergerea elementului de la sfarsitul listei

- stergerea unui element din interiorul listei

- traversarea listei, cu prelucrarea elementelor acesteia

Aplicatie: Sa se implementeze operatiile cu liste liniare simplu inlantuite. Se va realiza cate o functie pentru fiecare operatie.