Introducere
Din punctul de vedere al unui programator, memoria este împărțită în octeți (succesiune
de octeți), referirea la un octet realizându-se cu ajutorul unor adrese de memorie. În memorie
se alocă zone pentru toate variabilele cu care lucrează un program. Această alocare se poate
face: static (la declararea variabilei respective, zona fiind ocupată până la terminarea execuției
programului) sau dinamic (mediul de execuție sau programatorul gestionează alocarea sau
eliberarea unei zone).
Spațiul de memorie aferent datelor statice se definește și se rezervă la dimensiune
maximă, corespunzătoare tipului datei respective, și este un spațiu propriu care nu poate fi
disponibilizat și nici împărțit cu alte date, chiar dacă în diverse momente/faze ale execuției
programului nu este în întregime utilizat (rezervare statică sau la momentul compilării). De
asemenea, componentele structurilor statice ocupă locuri prestabilite în spațiul rezervat,
determinate de relația de ordonare specifică fiecărei structuri. Totodată, limbajul definește
operațiile admise cu valorile componentelor, potrivit tipului de bază al structurii, astfel încât
numărul maxim și ordinea componentelor structurii nu pot fi modificate.
În aceste condiții, în rezolvarea problemelor care prelucrează mulțimi de date pentru
care numărul și ordinea componentelor se modifică frecvent în timpul execuției programului,
structurile statice sunt dificil de utilizat. Pentru astfel de situații, limbajele de programare oferă
posibilitatea utilizării datelor de tip dinamic, cărora li se pot aloca și elibera zone de memorie
pe parcursul execuției programului.
O structură de date este formată dintr-un set de date grupate împreună sub același nume.
Aceste date, denumite membrii, pot avea tipuri și lungimi diferite. In C++ structurile de date
se declară în modul următor:
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. Între acolade se precizează membrii structurii și tipul acestora. Odată cu
declararea structurii, a fost creat un nou tip de date numit structure_name care poate fi
utilizat în restul programului ca orice alt tip de date fundamentale.
Structurile dinamice de date sunt date structurate ale căror componente se aloca în mod
dinamic. Alocarea dinamica a componentelor structurii impune un mecanism prin care o nouă
componentă introdusă este legată în succesiune logică de corpul structurii deja format până
atunci. Rezultă că este necesar ca fiecare componentă, pe lângă informația propriu-zisa pe care
o deține, trebuie sa conțină și o informație de legătura cu componenta cu care se leagă logic în
succesiune.
Datele alocate dinamic sunt memorate într-o zonă de memorie dedicată numită HEAP
a cărei dimensiune este variabilă, în funcție de necesități.
In HEAP, structura respectivă va avea zone alocate componentelor sale în locurile
găsite disponibile, care nu se succed întotdeauna în ordinea în care este realizată înlănțuirea
logică.
Definiție.
O listă liniară este o colecție de n≥0 noduri, x1,x2,...,xn aflate într-o relație de
ordine. Astfel x1 este primul nod al listei, x2 este al doilea nod al listei, și așa mai departe până
la xn care este ultimul nod al listei. Operațiile permise sunt:
- accesul la oricare nod al listei în scopul citirii sau modificării informației din;
- adăugarea unui nod, indiferent de poziția pe care o ocupă în listă;
- ștergerea unui nod, indiferent de poziția pe care o ocupă în listă;
- schimbarea poziției unui nod în cadrul listei
Relația de ordine de la listele liniare simplu înlănțuite o reprezintă, de obicei, relația de
succesor, adică fiecare nod conține o adresă către următorul nod al listei. În astfel de liste există
numai un nod care nu are succesor (ultimul nod) și numai un nod care nu e succesorul nimănui
(primul nod sau capul listei). Prin convenție, variabila care va memora adresa primului nod se
va numi baza.
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.