Introducere
Din punctul de vedere al unui programator, memoria este impartita in octeti (succesiune
de octeti), referirea la un octet realizandu-se cu ajutorul unor adrese de memorie. In memorie
se aloca zone pentru toate variabilele cu care lucreaza un program. Aceasta alocare se poate
face: static (la declararea variabilei respective, zona fiind ocupata pana la terminarea executiei
programului) sau dinamic (mediul de executie sau programatorul gestioneaza alocarea sau
eliberarea unei zone).
Spatiul de memorie aferent datelor statice se defineste si se rezerva la dimensiune
maxima, corespunzatoare tipului datei respective, si este un spatiu propriu care nu poate fi
disponibilizat si nici impartit cu alte date, chiar daca in diverse momente/faze ale executiei
programului nu este in intregime utilizat (rezervare statica sau la momentul compilarii). De
asemenea, componentele structurilor statice ocupa locuri prestabilite in spatiul rezervat,
determinate de relatia de ordonare specifica fiecarei structuri. Totodata, limbajul defineste
operatiile admise cu valorile componentelor, potrivit tipului de baza al structurii, astfel incat
numarul maxim si ordinea componentelor structurii nu pot fi modificate.
In aceste conditii, in rezolvarea problemelor care prelucreaza multimi de date pentru
care numarul si ordinea componentelor se modifica frecvent in timpul executiei programului,
structurile statice sunt dificil de utilizat. Pentru astfel de situatii, limbajele de programare ofera
posibilitatea utilizarii datelor de tip dinamic, carora li se pot aloca si elibera zone de memorie
pe parcursul executiei programului.
O structura de date este formata dintr-un set de date grupate impreuna sub acelasi nume.
Aceste date, denumite membrii, pot avea tipuri si lungimi diferite. In C++ structurile de date
se declara in modul urmator:
struct structure_name {
type1 member_name1;
type2 member_name2;
type3 member_name3;
} object_names;
unde object_names este un set valid de identificatori pentru obiecte care sunt de tipul
acestei structuri. Intre acolade se precizeaza membrii structurii si tipul acestora. Odata cu
declararea structurii, a fost creat un nou tip de date numit structure_name care poate fi
utilizat in restul programului ca orice alt tip de date fundamentale.
Structurile dinamice de date sunt date structurate ale caror componente se aloca in mod
dinamic. Alocarea dinamica a componentelor structurii impune un mecanism prin care o noua
componenta introdusa este legata in succesiune logica de corpul structurii deja format pana
atunci. Rezulta ca este necesar 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.
Datele alocate dinamic sunt memorate intr-o zona de memorie dedicata numita HEAP
a carei dimensiune este variabila, in functie de necesitati.
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.
Definitie.
O lista liniara este o colectie de n>=0 noduri, x1,x2,...,xn aflate intr-o relatie de
ordine. Astfel x1 este primul nod al listei, x2 este al doilea nod al listei, si asa mai departe pana
la xn care este ultimul nod al listei. Operatiile permise sunt:
- accesul la oricare nod al listei in scopul citirii sau modificarii informatiei din;
- adaugarea unui nod, indiferent de pozitia pe care o ocupa in lista;
- stergerea unui nod, indiferent de pozitia pe care o ocupa in lista;
- schimbarea pozitiei unui nod in cadrul listei
Relatia de ordine de la listele liniare simplu inlantuite o reprezinta, de obicei, relatia de
succesor, adica fiecare nod contine o adresa catre urmatorul nod al listei. In astfel de liste exista
numai un nod care nu are succesor (ultimul nod) si numai un nod care nu e succesorul nimanui
(primul nod sau capul listei). Prin conventie, variabila care va memora adresa primului nod se
va numi baza.
Primești proiectul în câteva minute,
cu sau fără cont