Liste liniare dublu înlănțuite

CAP. STRUCTURI DE DATE

Structura de date este o notiune abstracta, caracterizata prin operatiile care se executa asupra ei, in timp ce tipul de date reprezinta aspectul concret, referitor la implementare.

I. Clasificarea structurilor de date

In functie de tipul datelor memorate in cadrul structurii, structurile de date se pot clasifica in:

- Structuri de date omogene- toate datele componente sunt de acelasi tip. De exemplu, tabloul este o structura de date omogena.

- Structuri de date neomogene- pot contine date de tipuri diferite. De exemplu, articolul nu este o structura de date omogena.

Alocarea memoriei pentru structurile de date se poate face in

doua moduri

- Static: structura de date ocupa o zona de memorie de dimensiune fixa, alocata pe intreaga durata de executie a programului sau subprogramului in care a fost declarata;

- Dinamic: structura de date aloca sau se elibereaza memorie la cererea programatorului atunci cand se adauga, respectiv se sterge un element, deci zona de memorie alocata este variabila.

Alocarea dinamica a componentelor unei structuri de date determina aparitia in timp a unor noi componente care trebuie legate in structura de celelalte, ceea ce implica faptul ca orice element (componenta) a unei structuri dinamice de date contine pe langa informatia propriu-zisa si o informatie de legatura prin care se realize inlantuirea.

In functie de modul de legatura intre elemente, structurile dinamice de date se clasifica astfel:

- Structuri liniare(liste liniare);

- Structuri arborescente;

- Structuri retea;

II. LISTE LINIARE

Lista este o structura de date, construita dintr-o succesiune de componente de acelasi tip, in care fiecare element are un predecesor (cu exceptia primului), respectiv un succesor (cu exceptia ultimului). Numarul de elemente din lista este variabil, putandu-se modifica prin stergerea unor componente, sau prin adaugarea unora noi.

La randul lor listele liniare sunt de mai multe tipuri si anume: liste liniare simplu inlantuite, liste liniare dublu inlantuite, stive, cozi, liste circulare.

LISTE DUBLU INLANTUITE

O lista liniara dublu inlantuita este o lista liniara care respecta urmatoarele reguli:

- fiecare element al listei memoreaza o informatie de acelasi tip;

- oricare element din interiorul listei are un procesor si un succesor;

- exista un element pentru care nu exista decat succesor, pe care-l vom numi primul element;

- exista un element al listei care nu are decat predecesor si pe care il vom numi ultimul element.

Fiind structuri de date inlantuite avem nevoie de un tip de date care sa memoreze informatia, precum si adresele elementului predecesor si a elementului succesor.

1. Definirea unei liste dublu inlantuite

type lista=^nod;

nod=record

info:integer;

urm,pred:lista;

end;

inf-campul de informatie utila;

urm-pointer ce retine adresa elementului urmator;

pred-pointer ce retine adresa elementului anterior(predecesor);

campul campul