Liste înlăntuite. Multimi realizate ca liste

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 constanta NULL (un "pointer către nicăieri"), fie adresa primului element din listă (listă circulară sau inel).

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.