Structuri alocate dinamic

În cazul variabilelor structură alocate dinamic şi care nu au nume se va face o indirectare printrun pointer pentru a ajunge la variabila structură. Avem de ales între următoarele două notaţii echivalente: pt->camp (*pt).camp unde pt este o variabilă care conţine un pointer la o structură cu câmpul camp. O colecţie de variabile structură alocate dinamic se poate memora în două moduri: Ca un vector de pointeri la variabilele structură alocate dinamic; Ca o listă înlăntuită de variabile structură, în care fiecare element al listei conţine şi un câmp de legătură către elementul următor (ca pointer la structură). Pentru primul mod de memorare a se vedea Vectori de pointeri la date alocate dinamic.

Liste înlănţuite

O listă înlănţuită (“linked list”) este o colecţie de variabile alocate dinamic (de acelaşi tip), dispersate în memorie, dar legate între ele prin pointeri, ca într-un lanţ. Într-o listă liniară simplu înlănţuită fiecare element al listei conţine adresa elementului următor din listă. Ultimul element poate conţine ca adresă de legatură fie constanta NULL, fie adresa primului element din listă (lista circulară). Adresa primului element din listă este memorată într-o variabilă cu nume şi numită cap de lista (“list head”). Pentru o listă vidă variabila cap de listă este NULL. Structura de listă este recomandată atunci când colecţia de elemente are un conţinut foarte variabil (pe parcursul execuţiei) sau când trebuie păstrate mai multe liste cu conţinut foarte variabil. Un element din listă (un nod de listă) este de un tip structură şi are (cel puţin) două câmpuri: un câmp de date (sau mai multe) un câmp de legătură Definiţia unui nod de listă este o definitie recursivă, deoarece în definirea câmpului de legătură se foloseşte tipul în curs de definire.

Exemplu pentru o listă de întregi:

typedef struct snod {

int val ; // camp de date

struct snod * leg ; // camp de legatura

}

nod;

Programul următor arată cum se poate crea şi afisa o listă cu adăugare la început (o stivă realizată ca listă înlănţuită):

int main ( ) {

nod *lst=NULL, *nou, * p; // lst = adresa cap de lista

int x; // creare lista cu numere citite

while (scanf(“%d”,&x) > 0) { // citire numar intreg x

nou=(nod*)malloc(sizeof(nod));// creare nod nou

nou->val=x; // completare camp de date din nod

nou->leg=lst;

lst=nou; // legare nod nou la lista } // afisare listă (fara modificare cap de lista)

p=lst;

while ( p != NULL) { // cat mai sunt noduri

printf(“%d “, pval); // afisare numar de la adr p

p=p->leg; // avans la nodul urmator

}

}

Câmpul de date poate fi la rândul lui o structură specifică aplicaţiei sau poate fi un pointer la date alocate dinamic (un şir de caractere, de exemplu). De obicei se definesc funcţii pentru operaţiile uzuale cu liste.

Alte structuri dinamice folosesc câte doi pointeri sau chiar un vector de pointeri; într-un arbore binar fiecare nod conţine adresa succesorului la stânga şi adresa succesorului la dreapta, într-un arbore multicăi fiecare nod conţine un vector de pointeri către succesorii acelui nod.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s