Listă simplă

Listele simplu inlantuite sunt structuri de date dinamice omogene. Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente separate de memorie. Fiecare nod al listei contine, in afara de informatia utila, adresa urmatorului element. Aceasta organizare permite numai acces secvential la elementele listei.

Pentru accesarea listei trebuie cunoscuta adresa primului element (numita capul listei); elementele urmatoare sunt accesate parcurgand lista.

Lista simplu inlantuita poate fi reprezentata grafic astfel:

Lista simpla este o structura dinamica. Se caracterizeaza prin:

- o variabila pointer, care contine adresa unei zone de memorie numita primul element al listei;

- zona de memorie se compune din doua subzone: o zona cu informatii utile si o variabila pointer ce contine adresa elementului urmator;

- celelalte elemente ale listei sunt legate intre ele;

- ultimul element al listei care are variabila pointer initializata cu NULL pentru a marca inexistenta unui element urmator.

Modelul graf presupune:

- o multime de noduri;

- o multime de arce;

- fiecare nod este legat de altul PRINTR-UN SINGUR ARC;

- un nod care nu are un arc incident spre el;

- un nod care nu are nici un arc incident spre exterior.

Modelul text sursa presupune o secventa de definire recursiva de articole.

Modelul analitic presupune existenta elementelor E1, E2, E3,....,Ex. Fiecare element are un camp de informatie utila IU si un pointer de legatura PL. Exista o variabila pointer cu care se refera primul element P1.

cont(P1)=adr(E1)

cont(Ei.PL)=adr(Ei+1)

i=1,2,3,..,x-1

cont(Ex.PL)=NULL

cont(Ei.IU) = siri, i=1,2,..,x

Daca elementele listei simple se definesc prin:

struct lista_simpla

{

int info;

struct lista_simpla *next;

};

struct lista_simpla a,b,c, *p;

si daca se initializeaza corespunzator aceste variabile, atunci referirea elementelor direct folosind pointerul i presupune folosirea repetata a operatorului de referire cu variabile pointeri.

1. Traversarea unei liste simplu inlantuite

Daca nodul de inceput al listei este indicat de variabila inceput, o variabila auxiliara q, care parcurge toate nodurile listei pana cand valoarea ei devine NULL, permite accesul la fiecare nod si efectuarea operatiei specifice traversarii:

for(q=inceput;q!=NULL;q=q->urmator)

//prelucrarea nodului indicat de q

Daca lista are doua noduri fictive, unul de inceput si unul de sfarsit, secventa de traversare devin