| CATEGORII DOCUMENTE |
Lista simplu inlantuita
Lista reprezinta o multime de dimensiune variabila, formata din elemente de acelasi tip. Intelegem prin lista - o multime dinamica si omogena, a carei dimensiune se modifica in timpul rularii programului.
Memorarea structurilor de date de tip lista se poate face in doua maniere:
secvential - elementele listei sunt memorate la adrese consecutive
inlantuit - elementele listei nu ocupa adrese consecutive, fiecare element contine pe langa informatia propriu-zisa si o legatura spre urmatorul element.
Memorarea secventiala se poate produce prin folosirea structurilor de date de tip tablou. Dinamica listei secventiale se realizeaza in aceasta situatie prin retinerea unui parametru suplimentar cu semnificatia dimensiunii curente a tabloului. Pentru listele organizate static, sub forma de tablou, ordinea elementelor este cea implicita in tablou.
In ciuda simplitatii acestei abordari se prefera varianta elementelor inlantuite si alocate dinamice. Argumentul folosirii listelor inlantuite rezida din necesitatea economiei de memorie. Folosirea tablourilor forteaza o declararea a numarului maxim de elemente ceea ce rareori este cunoscut la momentul dezvoltarii programului. In consecinta, folosirea unui tablou de o dimensiune mult mai mica decat maximul declarat, permite manevrarea elementelor sale dar in acelasi timp produce o risipa inutila a unui bloc memorie alocat si neutilizat.
In spiritul economiei de memorie, abordarea structurilor de date de tip lista prin liste inlantuite alocate dinamic este avantajoasa. Organizarea acestor structuri de date in C se face prin folosirea unor legaturi care nu sunt altceva decat pointeri (adrese) spre urmatoarele elemente din lista. Pentru listele organizate dinamic, sub forma inlantuita, ordinea elementelor este data de pointeri.Pointerii legatura din compunerea unui element al listei indica adresele unor alte elemente de acelasi tip. Elementele unei liste se denumesc in mod uzual noduri. Prin folosirea pointer-ilor (legaturi), structura unui nod al listei devine recursiva.
Liste inlantuite pot fi: simplu, dublu sau multiplu inlantuite. Clasificarea listelor se face in functie de numarul legaturilor din compunerea unui element.
Operatiile principale cu liste sunt urmatoarele:
Lista simplu inlantuita
Structura nodului listei simplu inlantuite:
Figura urmatoare prezinta in mod grafic structura unui nod al listei simplu inlantuite, punandu-se in evidenta cele doua parti ale nodului:
O structura care descrie compunerea unui element de acest gen este urmatoarea:
struct nod
Convenim ca informatia din noduri contine un camp special (cheie) ale carui valori sunt distincte pentru elementele aceleiasi liste (cheie nu este un camp obligatoriu). Pentru a simplifica exemplele urmatoare, vom introduce un nou tip de data, tipul nodurilor, denumit TNod.
typedef struct nod
Tnod;
Gestionarea unei liste de astfel de noduri necesita cunasterea adresei primului si eventual al ultimului nod din lista. Retinandu-se doar adresa primului nod, celelalte noduri pot fi parcurse, accesate, prin urmarirea legaturilor urm continute in nodurile curente.
Adresa fiecarui nod este continuta de nodul precedent, cu exceptia primului nod al listei, pentru care nu exista un nod precedent. Ultimul nod nu va referi niciun alt nod urmator, fapt care se marcheaza prin pointerul urm care devine Null. Figura urmatoare sugereaza organizarea unei liste simplu inlantuite:
Pentru implementarea operatiilor specifice listelor inlantuite este utila declararea a doi pointeri la tipul Tnod, cu semnificatia adreselor primului si ultimului element din lista:
Tnod *prim, *ultim;
Parcurgerea listei
Parcurgerea listei presupune accesarea sau prelucrarea elementelor listei in ordinarea stabilita de legaturile continute de noduri. Cunoscand primul element prim , acesta contine adresa urmatorului element, care la randul sau contine adresa urmatorului, etc. In acest mod, prin urmarirea adreselor de legatura pot fi accesati toti membrii listei. Terminarea operatiei de parcurgere a listei consta in accesarea ultimului element, marcat prin adresa nula a pointerului urm.
Considerand p adresa nodului curent din lista, trecerea la nodul urmator se obtine prin asignarea: p=p->urm;
Daca nodul curent p este Null (p==0), se incheie parcurgerea.
Pasii parcurgerii unei liste sunt urmatorii:
initializeaza pointer-ul curent cu adresa primului nod : p=prim
cattimp (pointerul curent este diferit de 0: p!=0 ) executa
a. prelucrare nodul referit de p (accesare, modificare continut)
b. trecerere la urmatorul nod p=p->urm
Oferim in continuare o functie C prin care se parcurge lista simplu inlantuita gestionata de prim si ultim si sunt afisate informatiile nodurilor traversate.
void tiparire_lista()
Crearea listei vide
Crearea unei liste inlantuite care nu contine niciun element presupune initializarea celor doi pointeri prim si ultim cu valoarea 0:
prim=ultim=0;
Crearea unei liste cu mai mult de 0 noduri presupune adaugarea in mod repetat a noilor noduri pana la intalnirea unei conditii de terminare a procedeului. Noile noduri pot fi adaugate sistematic dupa ultimul element al listei, sau inaintea primului nod. In procesul de adaugarea a unui nou nod se tine cont de doua aspecte:
nodul nou trebuie alocat in memorie si incarcat cu informatie
anumite legaturi din lista trebuie refacute pentru a asigura consistenta organizarii
Prezentam in continuare o functie C care are efectul alocarii si incarcarii unui nou nod de tipul Tnod. Utilitatea acestei functii o vom intelege in construirea functiilor de inserare - adaugare noduri la lista:
tnod * incarca_nod()
Inserarea unui nou element:
Inaintea primului nod
Etapele introducerii unui nou nod inaintea primului nod al listei gestionate prin pointerii prim si ultim sunt urmatoarele:
Observatie: daca lista este vida in momentul incercarii de a adauga un nod nou, efectul operatiei consta in obtinerea unei liste cu un singur element, fapt pentru care capetelor listei prim si ultim sunt confundate si este necesara tratarea acestui caz particular.
void adaugare_prim()
p->urm=prim;
prim=p;
Dupa ultimul nod
Etapele introducerii unui nou nod dupa ultimul nod al listei gestionate prin pointerii prim si ultim sunt urmatoarele:
alocarea si incarcarea noului nod:
stabilirea faptului ca acest ultimul nod va adresa ca urmator element pe noul nod: ultim->urm=nou (1)
stabilirea noului nod ca ultim element al listei, si marcarea acestuia ca ultim nod din lista: ultim=nou; nou->urm =0; (2)
daca lista este vida in momentul incercarii de a adauga un nod nou, se va trata distinct acest caz
void adaugare_ultim()
ultim->urm=nou;
ultim=nou; ultim->urm=0;
Inserarea unui nod inaintea unui nod specificat
Acest tip de operatie se realizeaza in doua etape:
cautarea nodului inaintea caruia se va insera un nou nod
inserarea propriu-zisa a noului nod
Cautarea unui nod specificat prin cheie se realizeaza printr-un algoritm elementar de parcurgere sistematica a listei pana la intalnirea nodului ce contine cheia cautata. In acest scop se poate construi o functie care returneaza adresa nodului cautat, si 0 in caz de insucces (daca nodul de cheie data nu exista in lista). Argumentul functiei este valoarea cheii cautate.
Cautarea nodului inaintea caruia se va insera noul nod poate fi realizata in aceiasi functie in care se face inserarea. Procedura de inserare tine cont de cazul particular in care nodul specificat prin cheie este primul nod.
Stabilirea legaturilor dintre noduri trebuie facuta corect pentru a nu genera pierderea unei sub-liste de noduri. In acest sens este necesara retinerea in permanenta a adresei nodului precedent nodului curent, pentru ca ulterior noul nod sa poate fi inlantuit intre nodurile precedent si curent. Imaginea urmatoare sugereaza etapele inserarii noului nod, cunoscandu-se adresa prev (nodul precedent= si adresa nodului curent p:
nodul nou va contine adresa nodul curent: nou->urm=p;
precedentul nod va contine adresa noului nod prev->urm=nou; - atribuire prin care vechea inlantuirea a nodurilor prev si p se pierde.
Functia urmatoare descrie operatia de inserare inaintea unui nod cautat dupa valoarea cheii:
void adaugare_inainte()
else
else
}
}
}//sfarsit functie
Dupa un nod stabilit de o cheie:
Operatia de inserare dupa un nod specificat este similara celei anterioare. Cazul particular al procedeului consta in gasirea ca nod de referinta chiar ultimul nod al listei, fapt pentru care operatia se reduce la adaugarea dupa ultim (functie deja construita).
In plus, retinerea unei adresa a precedentului nodului curent nu mai este necesara. In fapt, nodul nou se va insera intre nodul gasit (curent) si urmatorul nod al nodului curent. Insa, prin maniera de inlantuire, adresa urmatorului nod al nodului gasit este cunoscuta, fiind memorata ca legatura chiar in nodul gasit: p->urm .
Considerand nodul de cheie data gasit: p, etapele inserarii noului nod sunt:
nou->urm=p->urm (1)
void adaugare_dupa()
else
else
}
}
Stergerea unui element
Stergerea primului element al listei necesita eliberarea memoriei dar si actualizarea pointer-ului prim necesar in gestionarea ulterioara a listei. Actualizarea prim-ului nod al listei se face prin asignarea prim=prim->urm, prin care urmatorul nodului prim (secundul) devine prim al listei
void stergere_prim()
prim=prim->urm; //actualizare prim
free(primvechi);//eliberarea memoriei adresata de prim
Stergerea ultimului presupune refacerea legaturilor, eliberarea unei zone de memorie si actualizarea pointer-ului ultim (util in gestionarea listei). In contradictie cu operatia de stergere a primului nod, stergerea ultimului nod al listei necesita o parcurgere in totalitate a listei, pentru a determina adresa precedentului nodului ultim. Acest lucru este necesar pentru a realiza operatia de actualizare a pointer-ului ultim. Adresa urmatorului nod dupa prim se poate determina in mod elementar prin campul urm, insa, adresa nodului anterior ultimului se determina printr-un procedeu suplimentar de traversare a listei, generand un cost suplimentar al algoritmului.
Etapele stergerii ultimului element al unei liste sunt:
void stergere_ultim()
while (p!=ultim)
//traversarea listei si retinerea precedentului nodului //curent
//in acest punct prec este adresa penultimului nod
ultimvechi=p; //salvare vechiul nod ultim
ultim=prec; ultim->urm=0; //actualizare si marcare ultim
free (ultimvechi); //eliberare memorie
Stergerea unui element precizat
Stergerea unui element precizat prin valoarea cheii se executa prin urmatorii pasi:
cautarea nodului p ce va fi sters si retinerea adresei precedentului acestuia: prev
refacerea legaturilor: prev->urm= p->urm (1)
eliberarea memoriei
Cazurile particulare ale procedurii sunt tratate distinct prin procedurile specifice de stergere a primului sau ultimului nod.
void stergere_oarecare()
//caz particular
if (p==ultim)
//caz particular
//cazul general
pvechi=p; //salvare adresa nod curent
prev->urm=p->urm; //refacere legaturi
free(pvechi); //eliberare memorie
return;
}
else
}
Stergerea listei
Stergerea completa a listei se poate realiza prin apelul repetat al functiilor deja construit de stergere a primului, respectiv, a ultimului nod pana cand lista devine vida (pointer-ul prim devine Null). Din punct de vedere al eficientei, variante stergerii listei prin apelul functiei stergere_prim este preferata deoarece nu necesita traversarea listei pentru fiecare operatie de stergere a unui nod.
O varianta simpla dar gresita de stergere a listei consta in distrugerea capetelor listei prim si ultim, fapt pentru care gestionarea ulterioara a listei ( accesarea si prelucrarea nodurilor sale ) devine imposibila. Cu toate acestea, memoria ramane alocata nodurilor intermediare. Prin aceasta s-a distrus doar mecanismul de accesare a nodurilor, nu s-au distrus efectiv nodurile listei.
Functia urmatoare este o varianta de stergere a listei, prin stergerea repetata a nodurilor din capatul listei.
void stergere_lista()
else
}
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 3309
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
