Liste înlănţuite
- 1. Liste înlănţuite Definiţie O mulţime dinamică de structuri recursive de acelaşi tip şi care satisfac una sau mai multe relaţii de ordine introduse prin pointeri se numeşte listă înlănţuită. Elementele listei se mai numesc noduri. Cele mai utilizate tipuri de listă sunt: - lista simplu înlănţuită (unidirecțională); - lista dublu înlănţuită (bidirecțională); - circulară; - stive; - cozi. Lista simplu înlănţuită este structura de reprezentare a informaţiilor cea mai cunoscută şi implicit cea mai utilizată atunci când ne referim la alocarea dinamică a memoriei. O listă simplu înlănţuită este formată dintr-o colecţie de elemente de acelaşi tip. Fiecare element conţine în afară de elementul propriu-zis şi o legatură care ne spune unde putem găsi un alt element din mulţime. Elementele listei vor fi numite şi noduri. Ideea este că fiecare nod dintr-o listă simplu înlănţuită conţine informaţii despre cum putem localiza un alt nod dintr-o mulţime de noduri. Accesul imediat la fiecare nod din mulţime nu este necesar pentru că fiecare nod conduce la un altul. Acest tip de element se numeste NOD. Prin inf înţelegem informaţia ataşată elementului respectiv, şi care poate fi de orice tip de date cunoscut de către limbajul C++, iar prin leg înţelegem un câmp de tip referinţă care va conţine adresa următorului element din mulţimea de elemente. Pentru a putea construi şi a folosi cât mai eficient o listă simplu înlănţuită este necesară o variabilă de tip referinţă care să indice primul element din listă. Convenim să notăm cu prim – adresa primului nod. Uneori, întâlnim aplicaţii care necesită şi folosirea adresei ultimului nod, notată cu ultim. O formă grafică sugestivă pentru o listă simplu înlănţuită ar fi următoarea: Avantaje: Listele simplu înlănţuite reprezintă o utilizare foarte importanta a alocarii dinamice a memoriei deoarece: 1. Sunt mai flexibile decât stiva şi coada (care restricţionează operaţiile de adăugare, acces şi ştergere a elementelor conform definiţiilor lor) 2. Se recomandă folosirea listelor simplu înlănţuite în rezolvarea problemelor specifice vectorilor, deoarece se utilizează eficient memoria care poate fi alocată sau eliberată în funcţie de cerinţele programatorului 3. Anumite genuri de probleme (cum ar fi operaţiile cu matrici rare; respectiv polinoame rare) îşi găsesc o rezolvare mai rapidă, eficientă şi utilă folosind listele Declaraţiile necesare lucrului cu o listă simplu înlănţuită sunt: typedef struct tnod {
- 2. tip inf; // informatia propriu-zisa struct tnod *leg; // informatia de legatura } LISTA; LISTA *prim,*ultim; /* adresa primului, respectiv a ultimului element din lista */ Cu listele simplu înlănţuite se pot face următoarele operaţii: 1) Iniţializarea listei (crearea unei liste vide) void init(TNOD *prim) { prim=NULL; } 2) Adăugarea unui element în listă Aceasta operaţie se poate face în trei moduri, în funcţie de locul unde se inserează elementul în listă. Astfel putem avea: a) Inserarea unui element la începutul listei b) Inserarea unui element la sfârşitul listei c) Inserarea unui element în interiorul listei Adăugarea unui element la începutul listei se poate reprezenta grafic astfel: Etapele adăugarii unui element la începutul listei: • alocarea zonei de memorie necesare noului element (Se foloseşte un pointer de lucru p) - (a) • completarea informaţiei utile pentru noul element (notată cu nou) - (b) • completarea informaţiei de legătură cu adresa conţinută în variabila prim (ţinând cont că acesta va deveni primul element al listei şi, conform definirii acesteia, trebuie să conţină adresa elementului următor din listă, deci cel care era primul înainte de a face inserarea) - (c) • Actualizarea variabilei referinţă prim cu adresa elementului creat, care în acest moment devine primul element al listei - (d) void adaug_la_inceput( tip x, LISTA *prim ) // x reprezinta informatia ce se adauga la începutul listei { LISTA *p; // pointerul de lucru p=new LISTA; // (a) p->inf=x; // (b) p->leg=prim; // (c) prim=p; // (d) } a) Adăugarea unui element la sfârşitul listei, presupune inserarea acestuia după ultimul nod al listei. În acest caz avem nevoie de variabila ultim care indică nodul după care se va insera. Descrierea operaţiilor necesare se pot deduce şi de această dată folosind o reprezentare grafică a listei:
- 3. Paşii algoritmului de adăugare a unui element la sfârşitul listei: • Alocarea zonei de memorie necesară pentru noul element - (a) • Completarea informaţiei de legătură a elementului creat cu NULL, deoarece el va deveni ultim element - (b) • Completarea informaţiei utile - (c) • Informaţia de legatură a celui ce a fost înainte ultimul element al listei îşi schimbă valoarea cu adresa noului element (îl va indica pe acesta) - (d) • Se actualizează pointerul ultim cu adresa nodului adăugat listei - (e) void adauga_la_sfarsit( tip x, LISTA *ultim ) // realizeaza adaugarea valorii x la sfarşitul listei { LISTA *p; // pointer de lucru p=new LISTA; // (a) p->leg=NULL; // (b) p->inf=x; // (c) ultim->leg=p; // (d) ultim=p; // (e) } Adăugarea unui element în interiorul listei • Această operaţie se poate face înaintea sau după un element al listei. • Cel mai comod se face inserarea după un element specificat al listei. • Deoarece se realizează o inserare după un nod, acest lucru poate determina o adăugare la sfârşitul listei în cazul în care nodul respectiv este ultimul nod din această listă, operaţie descrisă anterior în funcţia adaug_la_sfarsit. Sunt necesari doi pointeri de lucru: – q – indică nodul după care este facută inserarea – p – pointer de lucru necesar pentru crearea unui nou element Presupunem că avem o listă cu cel puţin două elemente, unde după nodul indicat de q vom adăuga un nou element cu valoarea informaţiei propriu-zise x. Succesiunea logică a etapelor necesare inserării după un nod (indicat de q) este următoarea: • alocarea zonei de memorie necesară noului element (folosirea pointerului p) - (a) • iniţializarea informaţiei utile ( cu valoarea notată nou ) - (b) • iniţializarea informaţiei de legătură cu adresa următorului nod (cu adresa reţinută în acest moment în variabila q->leg) - (c) • actualizarea informaţiei de legatură din nodul după care s-a inserat noul element cu adresa zonei de memorie alocată pentru acesta (p) - (d) void adaug_dupa_o_valoare( int x, LISTA *q) { // adauga valoarea lui x într-un nod ce urmeaza nodului indicat de q în lista LISTA *p; // pointer de lucru p=new LISTA; // (a) p->inf=x; // (b) p->leg=q->leg; // (c) q->leg=p; // (d) }