Access	Adobe photoshop	Algoritmi	Autocad	Baze de date	C	C sharp
Calculatoare	Corel draw	Dot net	Excel	Fox pro	Frontpage	Hardware
Html	Internet	Java	Linux	Matlab	Ms dos	Pascal
Php	Power point	Retele calculatoare	Sql	Tutorials	Webdesign	Windows
Word	Xml

LISTE CU LEGATURI - LISTE INLANTUITE

c

+ Font mai mare | - Font mai mic

 

cap val leg val leg val leg

Un element din lista (numit si nod de lista) este de un tip structura si are (cel putin) doua campuri: un camp de date (sau mai multe) si un camp de legatura. In C este permisa o definitie recursiva, care foloseste tipul in curs de definire. Exemplu:

typedef int T; // orice tip numeric

typedef struct nod Nod;

Continutul si tipul campului de date depind de informatiile memorate in lista si deci de aplicatia care o foloseste. Toate functiile care urmeaza sunt direct aplicabile daca tipul de date nedefinit T este un tip numeric (aritmetic).

Tipul "List" poate fi definit ca un tip pointer sau ca un tip structura, pentru a fi usor de inlocuit cu un alt tip de colectie (de ex. cu un vector):

typedef Nod * List; // lista ca pointer

typedef struct List; // lista ca structura

O lista inlantuita este complet caracterizata de variabila 'cap de lista', care contine adresa primului nod (sau a ultimului nod, intr-o lista circulara).

Operatii cu liste inlantuite

Operatiile uzuale cu o lista inlantuita sunt :

- Initializare lista ( a variabilei cap de lista ): initL (List &)

- Adaugarea unui nou element la o lista: addL (List&, T)

- Eliminarea unui element dintr-o lista: delL (List&, T)

- Cautarea unei valori date intr-o lista: findL (List, T)

- Test de lista vida: emptyL(List)

- Parcurgerea tuturor nodurilor din lista (traversare lista).

Accesul la elementele unei liste cu legaturi este strict secvential, pornind de la primul element si trecand prin toate nodurile precedente celui cautat, sau pornind din elementul 'curent' al listei, daca se memoreaza si adresa elementului curent al listei.

Pentru parcurgere se foloseste o variabila cursor, de tip pointer catre nod, care se initializeaza cu adresa cap de lista; pentru a avansa la urmatorul element din list se foloseste adresa din campul de legatura al nodului curent:

Nod *p, *prim;

p = prim; // adresa primului element

p = p leg; // avans la urmatorul nod

Structura de lista inlantuita poate fi definita ca o structura recursiva: o lista este formata dintr-un element (eventual nul) legat de o alta lista. Acest punct de vedere poate conduce la functii recursive pentru operatii cu liste, dar fara nici un avantaj fata de functiile iterative.

// afisare recursiva lista inlantuita

void printL ( Nod* lst)

}

Varianta iterativa foloseste un ciclu pentru vizitarea fiecarui element din lista, repetat pana se ajunge la o legatura nula (inexistenta). Exemplu:

void printL ( Nod* lst)

}

Cautarea secventiala a unei valori date intr-o lista este asemanatoare operatiei de afisare, dar are ca rezultat adresa nodului ce contine valoarea cautata .

// cautare intr-o lista neordonata

Nod* findL (Nod* lst, T x)

}

Operatia de initializare a unei liste modifica adresa de inceput a listei:

void initL (Nod* & lst)

Crearea unui nou element de lista necesita alocarea de memorie. Verificarea rezultatului functiei 'malloc' (NULL daca alocare imposibila) se poate face printr-o instructiune "if" sau prin functia "assert". Exemple:

pn = (Nod*) malloc( sizeof(Nod));

assert (pn != NULL); // se include <assert.h>

In exemplele urmatoare nu vom face nici o verificare asupra rezultatului functiei "malloc" pentru simplificarea programelor.

Adaugarea unui element la o lista inlantuita se poate face:

- Mereu la inceputul listei;

- Mereu la sfarsitul listei;

- Intr-o pozitie determinata de valoarea noului element.

Daca ordinea datelor din lista este indiferenta pentru aplicatie, atunci cel mai simplu este ca adaugarea sa se faca numai la inceputul listei. In acest caz lista este de fapt o stiva iar afisarea valorilor din lista se face in ordine inversa introducerii in lista.

Exemplu de creare si afisare a unei liste inlantuite, cu adaugare la inceput de lista:

typedef Nod* List; // ptr a permite redefinirea tipului 'List'

void main ()

while (lst != NULL)

}

Operatiile elementare cu liste se scriu ca functii, pentru a fi reutilizate in diferite aplicatii. Exemplu de insertie element la inceput de lista:

void insL ( List & lst, T x)

Se poate evita modificarea adresei de inceput a listei daca lista contine in permanenta un prim element fara date ('santinela'), creat la initializare.

Exemplu de adaugare a unui nou element la sfarsitul unei liste:

void addL ( List & lst, T x)

// leaga nou dupa ultimul element din lista

p=lst; // pentru a nu modifica adresa de inceput a listei !

while (p leg !=NULL) // repeta cat timp exista un element urmator

p=p leg;

p leg=nou; // acum p este adresa ultimului nod din lista

}

In exemplele anterioare functia de adaugare a primit ca argument valoarea ce trebuie introdusa in lista, ceea ce o face dependenta de tipul datelor memorate in lista. O alta idee este de a crea elementul de lista in afara functiei (in programul principal, de exemplu) si de a transmite ca parametru adresa noului element. Exemple:

// adaugare nod cu adr. px dupa nodul cu adr. crt

void addL (List crt, List px)

// adaugare nod cu adr. px inaintea nodului cu adr. crt

void insL (List crt, List px)

Comparatie intre vectori si liste

Un vector este recomandat atunci cand este necesar un acces aleator frecvent la elementele listei (complexitate O(1)), ca in anumite metode de sortare (de ex. Quicksort), sau cand este necesara o regasire rapida pe baza pozitiei in lista sau pentru listele al caror continut nu se mai modifica si trebuie mentinute in ordine (fiind posibila si o cautare binara). Insertia si eliminarea de elemente intr-un vector au insa complexitatea O(n), unde "n" este dimensiunea vectorului.

O lista inlantuita se recomanda atunci cand dimensiunea listei este greu de estimat, fiind posibile multe adaugari si/sau stergeri din lista, sau atunci cand sunt necesare inserari de elemente in interiorul listei. Desi este posibil accesul pozitional, printr-un indice intreg, la elementele unei liste inlantuite, utilizarea sa frecventa afecteaza negativ performantele aplicatiei (complexitatea O(n)).

Vectorii au proprietatea de localizare a referintelor, ceea ce permite un acces secvential mai rapid prin utilizarea unei memorii "cache" (asa cum au procesoarele moderne); memoria "cache" nu ajuta in aceeasi masura si la reducerea timpului de prelucrare succesiva a elementelor unei liste inlantuite (mai dispersate in memorie). Din acelasi motiv structura de lista inlantuita nu se foloseste pentru date memorate pe un suport extern (disc magnetic sau optic).

Ideea memoriei "cache" este de a inlocui accesul individual la date dintr-o memorie (cu timp de acces mai mare) prin citirea unor grupuri de date adiacente intr-o memorie mai rapida (de capacitate mai mica), in speranta ca programele fac un acces secvential la date ( foloseste datele in ordinea in care sunt memorate).

Memorarea explicita de pointeri poate aduce un consum suplimentar de memorie; din acest motiv un text modificat frecvent (de catre un procesor de texte) nu se memoreaza ca o lista inlantuita de caractere (sau de linii de text), ci intr-un vector sau intr-o alta structura fara pointeri sau cu mai putini pointeri.

Problema lui Josephus este un exemplu care pune in evidenta avantajele si dezavantajele vectorilor si listelor intr-o aplicatie care necesita atat acces aleator la elementele colectiei, cat si modificarea colectiei (prin eliminarea de elemente).

Problema porneste cu o lista de n elemente (numere, de exemplu) situate intr-un cerc si elimina elementul gasit la distanta m fata de pozitia curenta (deplasand la stanga elementele urmatoare pentru a pastra lista compacta), repetand eliminarea pana cand ramane un singur element in lista. Fie lista initiala:

a b c d e f g h

si m=2. Daca se numara de la primul element atunci evolutia listei va fi in acest caz:

Lista pozitie curenta Element eliminat

a b c d e f g h 3 c

a b d e f g 5 f

a b d e g 2 b

a d e g 4 g

a d e 3 e

a d 1 a

d

Lista se poate memora ca un vector (un buffer circular) sau ca o lista inlantuita circulara. In cazul folosirii unui vector vom avea un cod C de forma urmatoare:

void josephus (int a[], int n, int m)

}

In cazul utilizarii unei liste simplu inlantuite circulare secventele importante de cod vor arata astfel:

//nod de lista

typedef

struct nod Nod;

// creare lista circulara pe baza unui vector

void buildL ( Nod*& lst, char a[], int n)

// eliminare succesiva din lista circulara

void josephus (Nod* lst, int m)

// afiseaza si elimina elementul din pozitia p

printf ('%c ', p->val);

q->leg =p->leg;

free(p);

p=q->leg; // noua pozitie curenta

}

}

Colectii de liste

O colectie de liste se implementeaza de obicei printr-un vector de pointeri care reuneste adresele de inceput ale listelor.

O aplicatie care foloseste mai multe liste de lungime foarte variabila este sortarea dupa ranguri sau pe compartimente ("Radix Sort" sau "Bin Sort").

Sortarea unui vector de n numere (cu maxim d cifre zecimale fiecare) se face in d treceri: la fiecare trecere k se distribuie cele n numere in 10 "compartimente" (liste) dupa valoarea cifrei din pozitia k (k=1 ptr. cifra din dreapta), si apoi se reunesc listele in vectorul de n numere (in care ordinea se modifica dupa fiecare trecere). Exemplu cu n=9 si d=3 :

Initial Trecerea 1 Trecerea 2 Trecerea 3

Vector cifra liste vector cifra liste vector cifra liste vector

Algoritmul poate fi descris astfel:

repeta pentru k de la 1 la d // pentru fiecare rang

initializare vector de liste t

repeta pentru i de la 1 la n // distribuie elem. din x in 10 liste

extrage in c cifra din pozitia k a lui x[i]

adauga x[i] la lista t[c]

repeta pentru j de la 0 la 9 // reunire liste in vectorul x

adauga toata lista j la vectorul x

Pentru a obtine cifra din pozitia k a unui numar y vom folosi relatia:

c = (y / pow(10,k-1)) % 10;

Adaugarea de elemente la o lista (in faza de distribuire) se face mereu la sfarsitul listei, dar extragerea din liste (in faza de colectare a listelor) se face mereu de la inceputul listelor, ceea ce face ca fiecare lista sa se comporte ca o coada.

Functia urmatoare implementeaza algoritmul de sortare pe ranguri:

void radsort (int x[ ], int n)

// reuneste liste din t in x

i=0;

for (c=0;c<10;c++) // si se adauga la vectorul x

div=div*10; // divizor ptr rangul urmator

}

}

Tipul abstract "Colectie de multimi disjuncte" poate fi implementat si printr-o colectie de liste, cu cate o lista pentru fiecare multime. Adreseele de inceput ale listelor din colectie sunt reunite intr-un vector de pointeri.

#define M 20 // nr. maxim de multimi in colectie

typedef struct sn nod;

typedef struct ds; // tipul 'disjoint sets'

// initializare colectie c de n multimi

void initDS ( ds & c, int n)

}

// cautare intr-o lista inlantuita

int inSet (int x, nod* p)

// gaseste multimea care-l contine pe x

int findDS (ds c, int x)

// reuniune multimi ce contin pe x si pe y

void unifDS (ds & c, int x, int y)

Vectorul de pointeri la liste este implementarea in limbajul C a unei colectii de liste, fiind folosit si in alte structuri sau tipuri abstracte de date, cum este structura de tabel "hash" utilizata pentru dictionare. De asemenea, este una din implementarile tipului abstract "graf", unde fiecare lista k este lista varfurilor vecine varfului k (numita si lista de adiacente).

5 Liste inlantuite ordonate

Listele inlantuite ordonate se folosesc in aplicatiile care fac multe operatii de adaugare si/sau stergere la/din lista si care necesita mentinerea permanenta a ordinii in lista. Pentru liste adaugarea cu pastrarea ordinii este mai eficienta decat pentru vectori, dar reordonarea unei liste inlantuite este o operatie ineficienta.

In comparatie cu inserarea intr-un vector ordonat, inserarea intr-o lista este mai rapida si mai simpla deoarece nu necesita mutarea unor elemente in memorie. Pe de alta parte, cautarea unei valori intr-o lista inlantuita ordonata nu poate fi asa eficienta ca si cautarea intr-un vector ordonat (cautarea binara nu se poate aplica si la liste).

Crearea si afisarea unei liste inlantuite ordonate poate fi considerata si ca o metoda de ordonare a unei colectii de date.

Operatia de inserare a unei valori la o lista ordonata este precedata de o cautare a locului unde se face inserarea, adica de gasirea nodului de care se va lega noul element. Mai exact, se cauta primul nod cu valoare mai mare decat valoarea care se adauga. Cautarea foloseste o functie de comparare care depinde de tipul datelor memorate si de criteriul de ordonare al elementelor.

Dupa cautare pot apare 3 situatii:

- Noul element se insereaza inaintea primului nod din lista;

- Noul element se adauga dupa ultimul element din lista;

- Noul element se intercaleaza intre doua noduri existente.

Prima situatie necesita modificarea capului de lista si de aceea este tratata separat.

Pentru inserarea valorii 40 intr-o lista cu nodurile 30,50,70 se cauta prima valoare mai mare ca 40 si se insereaza 40 inaintea nodului cu 50. Operatia presupune modificarea adresei de legatura a nodului precedent (cu valoarea 30), deci trebuie sa dispunem si de adresa lui. In exemplul urmator se foloseste o variabila pointer q pentru a retine mereu adresa nodului anterior nodului p, unde p este nodul a carui valoare se compara cu valoarea de adaugat (deci avem mereu : q leg == p).

       

  q p

Adaugarea unui nod la o lista ordonata necesita:

- crearea unui nod nou: alocare de memorie si completare camp de date;

- cautarea pozitiei din lista unde trebuie legat noul nod;

- legarea efectiva prin modificarea a doi pointeri: adresa de legatura a nodului precedent si legatura noului nod (cu exceptia adaugarii inaintea primului nod).

// insertie in lista ordonata

void insL (List & lst, T x) else

n leg=p; q leg=n; // n se introduce intre q si p

}

}

Cautarea nodului inaintea caruia trebuie introdus x se poate face si asa:

p=lst;

while ( p leg !=NULL && x > p leg val)

p=p leg;

n leg=p leg; p leg=n;

Sunt posibile si alte variante de inserare intr-o lista inlantuita ordonata, care sa nu foloseasca variabila q. O solutie este ca noul element sa se adauge dupa cel de la adresa p si apoi sa se schimbe intre ele datele din nodurile p si n :

void insL (List & lst, T x)

else

}

Stergerea unui element cu valoare data dintr-o lista incepe cu cautarea elementului in lista, urmata de modificarea adresei de legatura 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 realizeaza prin urmatoarele operatii:

q leg = p leg; // succesorul lui p devine succesorul lui q

free(p);

q p

Daca se sterge chiar primul nod, atunci trebuie modificata si adresa de inceput a listei (primita ca argument de functia respectiva).

Urmeaza o functie de eliminare a unui element cu valoare data dintr-o lista.

void delL (List & lst, T x)

if (p != NULL)

}

Inserarea si stergerea intr-o lista ordonata se pot exprima si recursiv, intr-o forma mai compacta. Exemplu:

// inserare in lista ordonata (T este un tip numeric)

void insL (List & lst, T x)

}

6 Variante de liste inlantuite

Variantele de liste intalnite in literatura si in aplicatii pot fi grupate in:

- Liste cu structura diferita fata de o lista simpla deschisa: liste circulare, liste cu element santinela, liste dublu inlantuite, etc.

- Liste generice, independente de tipul datelor memorate, avand in loc de date pointeri de tip 'void *' , care vor contine adresele datelor reunite in lista.

- Liste cu auto-organizare, in care fiecare element accesat este mutat la inceputul listei. In felul acesta elementele folosite cel mai frecvent se vor afla la inceputul listei si vor avea un timp de regasire mai mic.

- Liste cu acces mai rapid si/sau cu consum mai mic de memorie.

Intr-o lista cu santinela operatiile de adaugare si de stergere sunt mai simple, deoarece lista nu este niciodata vida si adresa de inceput nu se mai modifica dupa initializarea listei cu elementul santinela (fara date). Exemple de functii:

// initializare lista cu santinela

void initL (List & lst)

// afisare lista cu santinela

void printL ( List lst)

}

// inserare in lista ordonata cu santinela

void insL (List lst, int x)

nou leg=p; q leg=nou; // nou intre q si p

}

// stergere din lista ordonata

void delL (List lst, int x)

if (p)

}

Listele circulare permit accesul la orice element din lista pornind din pozitia curenta, fara a fi necesara o parcurgere de la inceputul listei. Intr-o lista circulara definita prin adresa elementului curent, nici nu este important care este primul sau ultimul element din lista.

O lista circulara este o implementare eficienta pentru o coada (de lungime variabila), deoarece ultimul element precede primul element din lista si deci este posibil accesul rapid atat la inceputul cat si la sfarsitul cozii indiferent de lungimea ei.

Definitia unui nod de lista circulara este aceeasi ca la o lista deschisa:

typedef struct nod Nod, *List;

Exemplu de operatii cu o lista circulara cu element sentinela:

// initializare lista circulara cu sentinela

void initL (List & lst)

// adaugare la sfarsit de lista

void addL (List & lst, T x)

// afisare lista

void printL (List lst, void (* print)(T))

}

7 Liste dublu inlantuite

Intr-o lista liniara dublu inlantuita fiecare element contine doua adrese de legatura: una catre elementul urmator si alta catre elementul precedent. Aceasta structura permite accesul mai rapid la elementul precedent celui curent si parcurgerea listei in sens invers.

Pentru acces rapid la ambele capete ale listei se poate defini tipul 'DList' si ca o structura cu doi pointeri: adresa primului element si adresa ultimului element; acest tip de lista se numeste uneori 'deque' ('double-ended queue') si este folosita pentru acces pe la ambele capete ale listei.

ultim

d

c

b

a

prim

next

prev

Exemplu de definire nod de lista dublu inlantuita:

typedef

struct nod Nod, * DList;

O alta varianta de lista dublu-inlantuita este o lista circulara cu element santinela. La crearea listei se creeaza elementul santinela. Exemplu de initializare:

void initDL (DList & lst)

In functiile care urmeaza nu se transmite adresa de inceput a listei la operatiile de inserare si de stergere, dar se specifica adresa elementului sters sau fata de care se adauga un nou element. Exemple de realizare a unor operatii cu liste dublu-inlantuite:

void initDL (List & lst)

// adauga nou dupa pozitia pos

void addDL (Nod* nou, Nod* pos)

// insertie nou inainte de pozitia pos

void insDL ( Nod* nou, Nod * pos)

// stergere element din pozitia pos

void delDL (Nod* pos)

}

// cauta pozitia unei valori in lista

Nod* pos (DList lst, T x)

// creare si afisare lista dublu-inlantuita

void main ()

printDL ( lst);

// sterge valori din lista

for (x=1;x<10;x++)

Functiile anterioare folosesc un cursor extern listei si pot fi folosite pentru a realiza orice operatii cu o lista: insertie in orice pozitie, stergere din orice pozitie s.a.

De cele mai multe ori nu se justifica un pointer suplimentar catre elementul precedent deoarece pozitionarea pe un element din lista se face de obicei printr-o cautare, iar la cautare se poate retine adresa elementului precedent celui gasit:

Nod * p,*prev;

prev = p = lst; // sau p=lst->next ptr liste cu santinela

while ( p != NULL && x != p val)

// prev este adresa nodului precedent nodului p

8 Aplicatie: Alocator de memorie

Cunoasterea modului de lucru al functiilor standard "malloc" si "free" este utila atat pentru o programare mai eficienta (in C si C++ sarcina alocarii si eliberarii de memorie cade in totalitate in sarcina programatorilor de aplicatii) cat si ca exemplu de situatie in care o lista inlantuita este cea mai buna solutie a unei probleme.

Memoria disponibila pentru alocare dinamica este numita traditional "Heap", desi nu are structura unui arbore binar partial ordonat.

Fiecare apel al functiei "malloc" este o cerere pentru un bloc de memorie (contiguu) de dimensiune data din memoria Heap. Fiecare apel al functiei "free" declara disponibil (liber) un bloc de la o adresa data (alocat anterior prin functia "malloc". Succesiunea de apeluri ale acestor functii este imprevizibila si poate proveni din programe (procese) diferite; din acest motiv, memoria Heap contine in general o alternanta de blocuri libere si alocate, de diferite lungimi.

Pentru gestiunea spatiului liber este necesar ca toate blocurile libere sa fie reunite intr-o structura, care sa permita cautarea unui bloc liber de dimensiune data. Trebuie adaugat ca numarul de blocuri libere (si ocupate) poate varia in limite foarte largi (fara limite, de fapt), iar dimensiunile blocurilor pot fi foarte diferite.

Reunirea unor blocuri de memorie neadiacente intr-o singura structura (colectie) se poate face numai in doua moduri:

- Un vector de pointeri catre aceste blocuri (de dimensiune foarte variabila si imposibil de anticipat);

- O lista inlantuita sau un arbore care sa contina in noduri pointeri catre blocurile libere.

Solutia vectorului iese imediat din discutie din cauza ca si vectorul ar trebui (re)alocat dinamic.

Din cauza numarului mare de blocuri este de dorit ca sa se utilizeze cat mai putini pointeri pentru fiecare bloc, ceea ce elimina solutia cu un arbore de pointeri, desi ar exista argumente pentru un arbore binar de cautare.

La cerintele expuse pana acum mai trebuie adaugate inca doua, care pot influenta solutia aleasa:

- La cautarea unui bloc liber de dimensiune data putem folosi doi algoritmi: "first fit" care spune ca se cauta primul bloc suficient de mare din lista de blocuri libere, sau "best fit" care spune ca se cauta blocul cu dimensiunea cea mai apropiata de cea care a fost ceruta. Algoritmul "best fit" ar putea fi eficient intr-o structura de arbore binar de cautare ordonat dupa dimensiunile blocurilor.

- La eliberarea unui bloc trebuie verificat daca nu cumva exista un alt bloc liber adiacent in memorie cu acesta, pentru a reuni cele doua blocuri libere in unul singur, mai mare. Pentru a verifica rapid aceste conditii lista de blocuri trebuie ordonata crescator dupa adresele blocurilor libere si, aparent, ar fi necesara o lista dublu-inlantuita de pointeri la blocuri (pentru acces rapid la ambele blocuri vecine din lista: din stanga si din dreapta).

Luand in considerare toate aceste cerinte, solutia preferata in practica este o lista simplu inlantuita de blocuri libere, ordonata dupa adresele blocurilor si utilizarea unui algoritm "first fit".

Fiecare bloc este o structura formata dintr-un antet de bloc ("Header") si blocul folosit efectiv pentru date de catre programul care l-a solicitat. Antetul de bloc este redus la informatiile strict necesare: dimensiunea blocului si adresa blocului urmator din lista spatiului liber.

p1 p2

Am notat cu p1 adresa unui bloc obtinuta de functia "malloc" si cu p2 adresa furnizata de "malloc" ca rezultat, pentru a fi folosita de aplicatii pentru memorarea de date. Daca p1 si p2 sunt pointeri de tip Header* atunci p2=p1+1 (adresele difera prin dimensiunea unei unitati de tip "Header").

typedef struct hdr Header;

Dimensiunile blocurilor de memorie alocate sunt de obicei un multiplu al dimensiunii antetului de bloc, indiferent de numarul octetilor solicitati. Deci, pentru intregi si pointeri de 4 octeti (32 de biti), partea alocata pentru date este intotdeauna un multiplu de 8 octeti. In plus, ar trebui ca adresa de inceput a spatiului liber sa fie un multiplu de 8 octeti, astfel ca orice valoare de tip int sau long dintr-un bloc sa fie citita sau scrisa printr-un singur acces la memorie.

Faptul ca orice bloc alocat are cel putin 8+8 octeti este important de retinut pentru aprecierea memoriei ocupate de structuri alocate dinamic si in alegerea unei solutii eficiente.

Initial lista de blocuri libere contine un singur bloc a carui dimensiune este egala cu marimea memoriei rezervate pentru alocare dinamica (de fapt, este posibil ca si memoria "heap" sa creasca dinamic, prin apeluri la sistemul de operare). Alocarea unui bloc (ca urmare a unui apel "malloc") se poate face fie la sfarsitul zonei "heap", fie la inceputul zonei "heap". Ultima solutie este preferabila pentru ca asigura adrese crescatoare la apeluri succesive ale functiei "malloc".

Fie 'n' numarul de octeti necesari (dupa rotunjire la multiplu de 8 si adaugarea celor 8 octeti pentru antetul de bloc) si 'p' adresa primului bloc liber suficient de mare (cu dimensiune np>= n). Daca blocul liber are exact 'n' octeti atunci el este scos din lista blocurilor libere; daca este mai mare atunci se creeaza un bloc de n octeti ce va fi folosit de aplicatie si un bloc liber de dimensiunea ramasa (m=np-n) :

prev next

np octeti liberi

np ..

p

prev next

date m octeti liberi

n +++++++ m ..

rezultat malloc

Daca se fac numai alocari de memorie (fara eliberari) atunci va fi mereu un singur bloc liber, de dimensiune tot mai mica si cu adresa tot mai mare. Dupa un numar mai mare de alocari si eliberari ale unor blocuri de lungimi diferite se poate ajunge ca in zona "heap" sa alterneze blocuri ocupate si blocuri libere (pentru blocurile ocupate nu se foloseste campul "ptr", de inlantuire, ci doar campul "size" din antet).

Aspectul zonei "heap" dupa secventa: p1=malloc(n1), p2=malloc(n2), p3=malloc(n3), free(p2) :

n1 ++++ n2 . n3 ++++++++ 0 n .

p1 p2 p3

La eliberarea unui bloc cu adresa data (un apel la functia "free") se introduce acest bloc in lista de blocuri libere, intr-o pozitie determinata de adresa sa (astfel ca lista sa fie mereu ordonata dupa adrese). Dupa aceasta se verifica blocul imediat precedent (de la stanga sa) si apoi blocul imediat urmator (de la dreapta sa), pentru a vedea daca nu sunt blocuri libere adiacente pentru a fi comasate intr-un singur bloc mai mare.

Urmeaza o varianta de implementare pentru alocatorul de memorie:

#define MSIZE 4096 // dimensiune (initiala) Heap

#define HS 8 // dimensiune antet = sizeof(Header)

Header* freep; // adresa primului bloc liber (var. externa)

// initializari

void xinit (void)

// alocare memorie

void * xalloc ( int n )

return (void*) (p+1); // adresa date din bloc alocat

}

else

return NULL; // nu s-a gasit nici un bloc cu min. nu unitati

}

Functia urmatoare returneaza blocul eliberat in lista de blocuri libere si apoi face comasarea blocurilor libere vecine:

void xfree (void * ap)

}

else

bp ptr=prev ptr; // blocul bp se leaga dupa blocul prev

prev ptr=bp;

if ( bp ptr && (bp+bp size == bp ptr))

if ( prev+prev size == bp)

}

}

9 Liste cu salturi ("Skip List")

Dezavantajul principal al listelor inlantuite este timpul de cautare a unei valori date, prin acces secvential; acest timp este proportional cu lungimea listei. De aceea s-a propus o solutie de reducere a acestui timp prin utilizarea de pointeri suplimentari in anumite elemente ale listei. Listele denumite "skip list" sunt liste ordonate cu timp de cautare comparabil cu alte structuri de cautare (arbori binari si tabele de dispersie). Timpul mediu de cautare este de ordinul O(lg n), dar cazul cel mai defavorabil este de ordinul O(n) (spre deosebire de arbori binari echilibrati unde este tot O(lg n).

O lista skip poate fi privita ca fiind formata din mai multe liste simple.

Adresele de legatura intre elemente sunt situate pe cateva niveluri: pe nivelul 0 este legatura la elementul imediat urmator din lista , pe nivelul 1 este o legatura la un element aflat la o distanta d1, pe nivelul 2 este o legatura la un element aflat la o distanta d2>d1 s.a.m.d. Adresele de pe nivelurile 1,2,3 si urmatoarele permit "salturi" in lista pentru a ajunge mai repede la elementul cautat.

Cautarea incepe pe nivelul maxim si se opreste la un element cu valoare mai mica decat cel cautat, dupa care continua pe nivelul imediat inferior s.a.md. Pentru exemplul din desen, cautarea valorii 800 incepe pe nivelul 2, "sare" direct si se opreste la elementul cu valoarea 500; se trece apoi pe nivelul 1 si se sare la elementul cu valoarea 700, dupa care se trece pe nivelul 0 si se cauta secvential intre 700 si 900.

Exemplu de definire a unei liste cu salturi (circulara si cu santinela) :

#define MAXLEVEL 10 // limita sup. ptr nr maxim de pointeri pe nod

typedef struct Node Node;

#define NIL list.hdr // conditie de terminare lista

typedef struct SList;

// initializare lista

void initL(SList& list)

// cauta in lista list o valoare data x

Node *findL(SList list, int x)

Initial fiecare nod are un singur pointer, pe nivelul 0. Nivelul listei (numar maxim de pointeri pe nod) poate creste la adaugarea de noduri si poate scadea la eliminarea de noduri din lista. Pentru a stabili numarul de pointeri la un nod nou (in functia de adaugare) se foloseste un generator de numere aleatoare in intervalul [0,1]: daca iese 0 nu se adauga alti pointeri la nod, daca iese 1 atunci se adauga un nou pointer si se repeta generarea unui nou numar aleator, pana cand iese un 0. In plus, mai punem si conditia ca nivelul sa nu creasca cu mai mult de 1 la o adaugare de element.

Probabilitatea ca un nod sa aiba un pointer pe nivelul 1 este , probabilitatea sa aiba un pointer pe nivelul 2 este s.a.md.

Pointerii pe nivelurile 1,2 etc. impart lista in subliste de dimensiuni apropiate, cu posibilitatea de a sari peste orice sublista pentru a ajunge la elementul cautat.

Functia de insertie in lista va realiza urmatoarele operatii:

insL (list, x)

cauta pozitia de pe nivelul 0 unde trebuie inserat x

determina nivelul noului nod (probabilistic)

daca e nevoie se creste nivel maxim pe lista

creare nod nou cu completare legaturi la nodul urmator de pe fiecare nivel

Exemplu de codificare a functiei de insertie intr-o lista skip:

Node *insL(SList& list, int x)

p = p leg[0];

if (p != NIL && p val== x) return p;

// determina nivel ptr noul nod

for (newLevel = 0; random(2) && newLevel < MAXLEVEL; newLevel++);

if (newLevel > list.level)

// creare nod nou

p = (Node*) malloc(sizeof(Node) + newLevel*sizeof(Node *)) ;

p val = x;

// stabilire legaturi nod p pe fiecare nivel

for (i = 0; i <= newLevel; i++)

return(p);

}

Afisarea unei liste skip se face folosind numai pointerii de pe nivelul 0, la fel ca afisarea unei liste simplu inlantuite.

S-au propus si alte variante de liste skip fata de cea prezentata:

- In locul unui vector de pointeri la fiecare nod, o lista inlantuita de pointeri;

- O solutie determinista pentru crearea de pointeri auxiliari pe alte niveluri decat nivelul 0, pe baza distantei dintre elemente succesive pe acel nivel.

10 Combinatii de liste si vectori

Reducerea memoriei ocupate si a timpului de cautare intr-o lista se poate face daca in loc sa memoram un singur element de date intr-un nod de lista vom memora un vector de elemente. Putem deosebi doua situatii:

- Vectorii din fiecare nod al listei au acelasi numar de elemente ("unrolled lists"), numar corelat cu dimensiunea memoriilor cache;

- Vectorii din nodurile listei au dimensiuni in progresie geometrica, pornind de la ultimul catre primul ("VLists").

Economia de memorie se obtine prin reducerea numarului de pointeri care trebuie memorati. O lista de n date, grupate in vectori de cate m in fiecare nod necesita numai n/m pointeri, in loc de n pointeri ca intr-o lista inlantuita cu cate un element de date in fiecare nod. Numarul de pointeri este chiar mai mic intr-o lista "VList", unde sunt necesare numai log (n) noduri.

Castigul de timp rezulta atat din accesul mai rapid dupa indice (pozitie), cat si din localizarea referintelor intr-un vector (folosita de memorii "cache"). Din valoarea indicelui se poate calcula numarul nodului in care se afla elementul dorit si pozitia elementului in vectorul din acel nod.

La cautarea intr-o lista ordonata cu vectori de m elemente in noduri numarul de comparatii necesar pentru localizarea elementului din pozitia k este k/m in loc de k .

Exemple de operatii cu o lista cu noduri de aceeasi dimensiune:

#define M 4 // nr maxim de elem pe nod (ales mic ptr teste)

typedef struct nod unod;

// initializare lista

void initL (unod * & lst)

// adaugare la sfarsit de lista

void addL (unod * lst, int x)

}

// acces pozitional, prin indice

int get (unod* lst, int k)

Numarul de noduri dintr-o astfel de lista creste cand se umple vectorul din nodul la care se adauga, la adaugarea unui nou element la lista. Initial se porneste cu un singur nod, de dimensiune data (la "UList") sau de dimensiune 1 (la "VList").

La eliminarea de elemente din lista este posibil ca numarul de noduri sa scada, atunci cand vectorul dintr-un nod este ocupat mai putin de jumatate.

Pentru listele cu noduri de dimensiune m, daca numarul de elemente dintr-un nod scade sub m/2, se aduc elemente din nodurile vecine; daca numarul de elemente din doua noduri vecine este sub m atunci se reunesc cele doua noduri intr-un singur nod. Altfel spus, numarul de elemente dintr-un nod este cuprins intre m/2 si m, ca si in cazul arborilor B.

O lista VList favorizeaza operatia de adaugare la inceput de lista. Exemplu de evolutie a unei liste VList la adaugarea succesiva a valorilor 1,2,3,4,5,6,7,8: