Liste Liniare
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)
O listã înlãntuitã este o structurã dinamicã, flexibilã, care se poate adapta cerintelor aplicatiei, fãrã ca utilizatorul sã fie preocupat de posibilitatea depãsirii unei dimensiuni estimate initial .
Avantajul folosirii listelor consta in gestionarea dinamica a memoriei. Alocarea sau eliberarea nodurilor se face dinamic, la fiecare inserare respectiv stergere,ceea ce face ca nodurile listei sa fie plasate dispersat in memorie (in cazul vectorilor – structuri de date omogene alocate static, zona de memorie folosita este contigua). Legatura dintre nodurile invecinate trebuie facuta logic explicit de catre programator, prin pastrarea informatiilor de legatura in fiecare nod (pe langa valoarea utila).
liste simplu inlantuite
liste dublu inlantuite
PROGRAME SURSA |
PROBLEME PROPUSE |
| creare.cpp |
liste_simplu_inlantuite1.doc |
| liste_simplu_inlantuite.cxx |
liste_simplu_inlantuite2.doc |
| liste_dublu.cpp |
GRILE
Grile_alocare_dinamica_C++.doc
</div>