Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


LISTA SIMPLU INLANTUITA

c



+ Font mai mare | - Font mai mic



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:

  1. parcurgere
  2. creare
  3. distrugere (stergere)
  4. adaugare nou element
  5. stergere element

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:

  1. zona de informatii, formata din unul sau mai multe campuri
  2. legatura spre alt nod de acelasi fel

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:

    1. alocarea si incarcarea noului nod:
    2. stabilirea faptului ca acest nou nod va adresa ca urmator element chiar pe nodul prim: nou->urm=prim
    3. stabilirea noului nod ca prim element al listei: prim=nou

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:

  1. stabileste adresa urm a nodului nou ca fiind adresa nodul urmator al lui p:

nou->urm=p->urm (1)

  1. stabile;te adresa urm a lui p ca fiind adresa lui nou: p->urm=nou. Prin aceasta asignare s-a pierdut automat inlantuirea veche intre p si p->urm

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:

    1. traversarea listei pentru a determina adresa penultimului element
    2. actualizarea ultimului nod
    3. eliberarea memoriei

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



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 3159
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved