2. Liste înlãntuite. Multimi realizate ca liste.
Liste înlãntuite
O listã înlãntuitã este o structurã dinamicã, flexibilã, care se poate adapta cerintelor aplicatiei, fãrã ca utilizatorul sã fie preocupat de posibilitatea depãsirii unei dimensiuni estimate initial .
O listã înlãntuitã (listã cu legãturi =
"Linked List") este o colectie de variabile structurã, alocate dinamic,
dispersate în memorie, dar legate între ele prin pointeri, ca într-un lant.
Intr-o listã liniarã simplu înlãntuitã fiecare element al listei contine adresa
elementului urmãtor din listã. Ultimul element poate contine ca adresã de
legaturã fie
Adresa primului element din listã este memoratã într-o variabilã cu nume (alocatã la compilare) si numitã cap de listã ("list head").
Structura de listã înlãntuitã are avantajul fatã de un vector cã lungimea listei este egalã cu numãrul efectiv de elemente introduse în listã (nu este necesarã o alocare estimativã).
Un element din listã (numit si nod de listã) este de un 313t1912d tip structurã si are (cel putin) douã câmpuri: un câmp de date si un câmp de legãturã. Definitii pentru o listã cu date de tipul T:
typedef int T; // orice tip numeric
typedef struct snod Nod, * Pnod;
typedef Nod * List; // tipul lista este un pointer la nod
Continutul si tipul câmpului de date (care poate fi un tip înregistrare) depind de datele memorate în listã si deci de aplicatia care o foloseste.
Operatii cu liste înlãntuite
O listã înlãntuitã este complet caracterizatã de variabila "cap de listã", care contine adresa primului nod (sau a ultimului nod, într-o listã circularã). Operatiile uzuale cu o listã înlãntuitã sunt:
- Initializare listã ( a variabilei cap de listã );
- Adãugarea unui nou element la o listã;
- Eliminarea unui element dintr-o listã;
- Parcurgerea tuturor nodurilor din listã (traversare lista).
- Cãutarea unei valori date într-o listã.
Accesul la elementele unei liste cu legãturi este strict secvential, pornind de la primul nod si trecând prin toate nodurile precedente celui cãutat, sau pornind din elementul curent al listei, dacã se memoreazã si adresa elementului curent al listei. Se foloseste o variabilã cursor, de tip pointer, care se initializeazã cu adresa cap de listã; pentru avans la urmãtorul element se foloseste adresa din câmpul de legãturã al nodului curent. Exemplu de afisare a continutului unei liste înlãntuite:
void printL ( Nod* lst)
Cãutarea unei valori date într-o listã este asemãnãtoare operatiei de traversare pentru afisare:
Nod* findL (Nod* lst, T x)
Structura de listã înlãntuitã poate fi definitã ca o structurã recursivã: o listã este formatã dintr-un element (eventual nul) legat de o altã listã. Acest punct de vedere poate conduce la functii recursive pentru operatii cu liste, dar fãrã nici un avantaj fatã de functiile iterative.
void printL ( nod* lst)
Urmeazã o variantã recursivã pentru functia de cãutare :
// cãutare in listã - recursiv
Nod* findL ( Nod* lst, T x)
Crearea unui nou element de listã necesitã apelarea functiei "malloc". Verificarea rezultatului acestei functii, care este NULL dacã cererea de alocare nu poate fi satisfãcutã, se poate face printr-o instructiune "if" sau prin macroinstructiunea "assert".
Adãugarea unui element la o listã înlãntuitã se poate face:
- Mereu la începutul listei;
- Mereu la sfârsitul listei;
- Intr-o pozitie determinatã de valoarea noului nod.
Dacã ordinea datelor din listã este indiferentã pentru aplicatie, atunci cel mai simplu este ca adãugarea sã se facã numai la începutul listei. In acest caz lista este de fapt o stivã iar afisarea valorilor din listã se face în ordine inversã introducerii în listã.
void main ()
while (lst != NULL)
Functia de adãugare a unui element la o listã poate modifica adresa de început a listei, deci variabila pointer primitã ca parametru. O solutie este o functie cu rezultat pointer care are ca rezultat noua adresã de început a listei, dupã insertie. Exemplu:
List insL (List lst, T x)
Se poate evita modificarea adresei de început a listei dacã lista contine în permanentã un prim element fãrã date (element sentinelã), creat la initializare.
In exemplele anterioare functia de adãugare a primit ca argument valoarea ce trebuie introdusã în listã, ceea ce o face dependentã de tipul datelor memorate în listã. O altã idee este de creare a elementului de listã în afara functiei (în programul principal, de exemplu) si de transmitere ca parametru a adresei noului element. Tot în afara functiei se poate face si determinarea pozitiei unde va fi inserat noul element. Exemple:
// adaugare nod cu adr. px dupa nodul cu adr. crt
void addL (List crt, List px)
// adaugare nod cu adr. px înaintea nodului cu adr. crt
void insL (List crt, List px)
Liste înlãntuite ordonate
Listele înlãntuite ordonate se folosesc în aplicatiile care fac multe operatii de adãugare la listã (poate si de stergere) si care necesitã mentinerea permanentã a unei ordini în listã. Este posibil sã facem adãugãri la o listã ordonatã cu pãstrarea ordinii, iar ordonarea unei liste înlãntuite este o operatie ineficientã si evitatã.
In comparatie cu inserarea într-un vector ordonat, inserarea într-o listã este mai rapidã si mai simplã deoarece nu necesitã mutarea unor elemente în memorie. Pe de altã parte, cãutarea unei valori într-o listã înlãntuitã ordonatã nu poate fi asa eficientã ca si cãutarea într-un vector ordonat (cãutarea binarã nu se poate aplica la liste înlãntuite).
Crearea si afisarea unei liste înlãntuite ordonate poate fi consideratã si ca o metodã de ordonare a unei colectii de date.
Operatia de insertie a unei valori la o lista ordonatã este precedatã de o cãutare a locului unde se face insertia, adicã de gãsirea nodului de care se va lega noul element. Mai exact, se cautã primul nod cu valoare mai mare decât valoarea care se adaugã.
Dupã cãutare pot apare 3 situatii:
- Noul element se insereazã înaintea primului nod din listã;
- Noul element se adaugã dupã ultimul element din listã;
- Noul element se intercaleazã între douã noduri existente.
Prima situatie necesitã modificarea capului de listã si de aceea este tratatã separat.
Pentru inserarea valorii 40 într-o listã cu nodurile 10,30,50,70 se cautã prima valoare mai mare ca 40 si se insereazã 40 înaintea nodului cu 50. Operatia presupune modificarea adresei de legãturã a nodului precedent (cu valoarea 30), deci trebuie sã dispunem si de adresa lui. In exemplul urmãtor se foloseste o variabilã pointer q pentru a retine mereu adresa nodului anterior nodului p, unde p este nodul a cãrui valoare se comparã cu valoarea de adãugat (deci q->leg == p).
Adãugarea unui nod la o listã ordonatã necesitã:
- crearea unui nod nou: alocare de memorie si completare câmp de date;
- cãutarea pozitiei din listã unde trebuie legat noul nod;
- legarea efectivã prin modificarea a doi pointeri: adresa de legãturã a nodului precedent si legãtura noului nod.
Cazul adãugãrii înaintea primului nod trebuie tratat separat. Exemplu de functie care foloseste doi pointeri q si p, cu insertia noului element între q si p:
List insL (List lst, int x)
else
n->leg=p; q->leg=n; // n între q si p
}
return lst;
Stergerea unui element cu valoare datã dintr-o listã începe cu cãutarea elementului în listã, urmatã de modificarea adresei de legãturã a nodului precedent celui sters. Fie p adresa nodului ce trebuie eliminat si q adresa nodului precedent. Eliminarea unui nod p (diferit de primul) se realizeazã prin urmãtoarele operatii:
q->leg = p->leg; // succesorul lui p devine succesorul lui q
free(p);
Insertia si stergerea într-o listã ordonatã se pot exprima si recursiv, mai compact. Exemplu:
// insertie in listã ordonatã
List insL (List lst, int x)
Variante de liste înlãntuite liniare
Variantele de liste întâlnite utile în aplicatii sunt: liste circulare, liste cu element sentinelã, liste dublu înlãntuite.
Intr-o listã circularã ultimul element contine adresa primului element. Intr-o listã cu sentinelã operatiile de adãugare si de stergere sunt mai simple, deoarece lista nu este niciodatã vidã si adresa de început nu se mai modificã dupã initializare.
Functia de inserare a unui nod, ca si cea de stergere a unui nod trebuie sã testeze dacã este necesarã modificarea adresei primului nod din listã. O micã modificare în structura listei poate elimina acest test si deci poate simplifica procedurile de adãugare si de eliminare. Ideea este ca lista sã continã mereu ca prim element un nod fãrã date (numit si element sentinelã); adresa acestui nod nu se modificã niciodatã si deci adresa cap de listã nu trebuie modificatã dupã initializarea listei cu acest prim element. Exemplu:
// initializare lista cu sentinela
List initL ()
// afisare lista cu sentinela
void printL ( List lst)
// insertie in lista ordonata cu sentinela
void insL (List L, int x)
n->leg=p; q->leg=n;
// stergere din lista ordonata
void delL (List L, int x)
if (p)
Insertia în lista ordonatã se poate face si folosind o singurã variabilã pointer:
void insL (List lst, int x)
O altã variantã interesantã de listã este o listã circularã definitã prin adresa ultimului element. Avantajul este accesul imediat atât la ultimul nod, cât si la primul nod (care este succesorul ultimului nod). O astfel de listã poate avea un prim element sentinelã.
O listã dublu înlãntuitã este o listã în care fiecare element contine doi pointeri: o legãturã la elementul urmãtor si o legãturã la elementul precedent. Consumul suplimentar de memorie se justificã numai dacã lista trebuie parcursã în ambele sensuri, sau dacã este de dorit ca o cãutare sã plece din pozitia curentã si nu mereu de la începutul listei.
Exemplu de definire nod de listã dublu înlãntuitã:
typedef struct sn Nod, * Pnod, * List;
O variantã bunã de listã dublu-înlãntuitã este o listã circularã cu element sentinelã. La crearea listei se creazã elementul sentinelã, cu legãturi la el însusi.
List initDL ()
Pentru o astfel de listã nu mai trebuie transmisã adresa de început a listei la operatiile de insertie si de stergere a unui element dintr-o pozitie datã, ci numai adresa nodului curent. Testul de listã vidã se poate face comparând adresa elementului curent cu adresa succesorului sãu: pentru nodul sentinelã adresele sunt identice.
Multimi implementate prin liste
Operatia de cãutare într-o listã necesitã un timp direct proportional cu lungimea listei si care nu poate fi redus nici prin mentinerea listei în ordine. In consecintã si operatiile cu douã multimi necesitã un timp mai mare, cu exceptia operatiei de adãugare a unei liste la o altã listã (realizatã prin modificarea unui singur pointer si fãrã cãutare în liste).
In programele cu una sau douã multimi si cu cãutãri frecvente nu trebuie folosite liste înlãntuite.
Se recomandã utilizarea de multimi liste numai atunci când aplicatia foloseste mai multe liste mici, al cãror continut se modificã frecvent si în care se fac putine cãutãri. Colectia de multimi liste se implementeazã printr-un vector de pointeri la liste înlãntuite, vector care reuneste adresele de început ale listelor din colectie. Multimile sunt liste simplu înlãntuite, cu adãugare mereu la început sau la sfârsit. Pentru multimi ordonate se vor folosi liste înlãntuite ordonate.
Urmeazã functii pentru operatii cu o multime realizatã ca listã cu santinelã de pointeri:
// definire tip "Set"
typedef struct lst Nod, *Set;
// initializare multime
Set initS ()
// test apartenenta la multime
int containsS (Set a, void * x, int (*cmp)(void*,void*))
// adaugare la multime
void addS ( Set a, void * x,int (*cmp)(void*,void*) )
// afisare multime
void printS( Set a, void (*prn)(void*))
}
Aceste functii pot înlocui functiile care lucrau cu o multime vector din aplicatia în care se afisau cuvintele distincte dintr-un fisier text, împreunã cu numãrul primei linii în care apare acel cuvânt.
|
