Liste

1. Notiuni generale despre liste. Liste simplu inlantuite.

2. Functii pentru crearea si gestionarea unei liste simplu inlantuite.

2.1 Crearea unei liste simplu inlantuite

2.2 Accesul la un nod al unei liste simplu inlantuite

2.3 Inserarea unui nod intr-o lista simplu inlantuita inaintea primului ei nod

2.4 Inserarea unui nod intr-o lista simplu inlantuita inaintea unui nod precizat print-o cheie.

2.5 Inserarea unui nod intr-o lista simplu inlantuita dupa un nod precizat printr-o cheie.

2.6 Stergerea primului nod al unei liste simplu inlantuite

2.7 Stergerea unui nod precizat printr-o cheie, dintr-o lista simplu inlantuita

2.8 Stergerea ultimului nod dintr-o lista simplu inlantuita

2.9 Stergerea unei liste simplu inlantuite.

1. Notiuni generale despre liste. Liste simplu inlantuite

Toate structurile ordonate de date se pot implementa in doua maduri generale:

Prin alocare inlantuita

Prin alocare secventiala

Alocarea secventiala presupune ca elemntele structurii de date se afla in locatii succesive de memorie(se vor implementa ca tablouri).Structurarea acestora realizindu-se prin tablouri suplimentare de indici.

Alocarea inlantuita permite ca elementele structurii de date sa se afle in locatii de memorie oarecare.Structurarea acestora realizindu-se prin includerea in elementul de baza al structurii a unor cimpuri de legatura(care contin adresele altor elemente ale structurii de date).

Lista inlantuita= o multime dinamica de structuri recursive de acelasi tip pentru care sint definite una sau mai multe relatii de ordine cu ajutorul unor pointeri din compunerea structurilor respective.

Structura recursiva=este acea structura care contine o variabila de tip pointer de tipul structurii respective.

Exemplu:

struct data

//structura contine un pointer care va pointa catre un element de tipul data.

Elementele unei liste se numesc noduri.

Daca intre nodurile unei liste exista o singura relatie de ordine atunci lista se numeste simplu inlantuita.

- poate fi parcursa de la primul catre ultimul element(intr-un singur sens).

- parcurgerea in ambele sensuri nu se poate face direct, dar se poate realiza prin folosirea unei structuri aditionale de tip stiva.(varianta care nu este recomandata).

O lista se numeste dublu inlantuita daca intre nodurile ei sint definite doua relatii de ordine.

- acest tip de structura de date va fi ales atunci cind sint necesare parcurgeri frecvente in ambele sensuri ale listei, din puncte oarecare si operatii frecvente de inserare si stergere.

- o lista dublu inlantuita se identifica prin pointeri catre primul si ultimul element.(de obicei acesti doi pointeri se memoreaza intr-un header al listei(cap de lista) cimpul left al headerului va indica ultimul element din lista, iar cimpul right va indica primul element din lista). Cimpul right al ultimului element si cimpul left al primului element vor indica headerul.

Pe linga cele doua tipuri de liste amintite mai sus mai intilnim si liste circulare alocate inlantuit printr-o singura relatie de ordine.

- in acest caz cimpul next al ultimului element indica primul element al listei(nu mai este NULL).

- avantajul este ca se pot face parcurgeri circulare , avind un element al listei putem avea acces si la elementele aflate inaintea lui.

Avantajele alocarii secventiale fata de cea inlantuita:

Gestionarea optima a memoriei heap.(ea va contine in fiecare moment al executiei programului numai elementele necesare).

Operatii cum ar fi stergerea sau inserarea unor elemente in structura respectiva de date pe pozitii specificate printr-o cheie se efectueaza mai rapid.

Dezavantaje ale alocarii secventiale:

Operatia de ordonare a elementelor este foarte costisitoare si dificil de realizat

In cazul listelor simplu inlantuite la care ne referim in acest capitol faptul ca acestea nu pot fi parcurse decit intr-un singur sens constituie un dezavantaj (pentru un element dat nu pot avea acces la elementele aflate inaintea lui ).

Liste simplu inlantuite

- intre nodurile unei liste simplu inlantuite este definita o singura relatie de ordonare.(fiecare nod contine un pointer care are ca valoare adresa urmatorului element din lista).

- intr-o lista simplu inlantuita exista un singur nod care nu mai are succesor(reprezsinta nodul de sfirsit de lista)si un singur nod care nu are precedent(reprezinta capatul listei=primul nod din lista).

- lista vida se reprezinta prin pointerul NULL, iar o lista nevida se reprezinta printr-un pointer la primul element.

2. Functii pentru crearea si gestionarea unei liste simplu inlantuita.

2.1 Crearea unei liste simplu inlantuite

Presupunem ca s-a definit un tip de data , numit DATA, care va fi continut intr-un element al listei.

DATA poate fi un tip simplu de date, un tablou o structura, etc.

Fie:

typedef int DATA;

typedef struct elem

ELEMENT, *LINK;

Tipul ELEMENT corespunde unui element al listei, iar tipul LINK unui pointer la un element al listei.

a)Pentru a putea crea o lista o prima operatie care trebuie efectuata este crearea unui element al listei. Aceasta operatie este realizata print-o functie pe care o numim ElemNou.

-functia primeste ca parametri datele(informatiile) pentru initializarea cimpului data din structura si un pointer la tipul structurii respective cu a carei valoare va fi initializat pointerul next al elemntului nou creat.(daca elemntul nou creat va fi ultimul element in lista valoarea acestui pointer va fi NULL, altfel va avea ca valoare adresa elemntului care va urma dupa elemntul nou creat).

Functia returneaza adresa elementului nou creat.

LINK ElemNou(DATA x,LINK p)

t->data=x;

t->next=p;

return t;

b) In aceasi idee (pentru crearea listei) este nevoie de un pointer numit p_cap -pointer care va avea intotdeauna ca valoare adresa primului element din lista si un pointer p_ultim care va contine adresa ultimului element adaugat in lista(ultimul element din lista va avea intotdeauna pointerul next initilizat cu NULL).Daca lista nu este creata(nu exista) acestia sint initializati cu NULL.

Exemplu:

Fie functia principala a programului:

void main()

else

//acesti pasi se repeta atita timp cit este necesar (se creaza lista cu un numar //de elemente dorit de utilizator )

//pentru a se implementa acest lucru este nevoie de un ciclu while.

Crearea unei liste simplu inlantuite pe pasi:

1. Se initializeaza pointerii p_cap si p_ultim cu valoarea NULL, deoarece lista la inceput este vida.(in functia main)

Obs: Cei doi pointeri este recomandat sa se declare global.

2. Se initializeaza datele elementului care doresc sa-l adaug in lista.(in functia main).

3. Se verifica daca este primul element al listei.

4. Se rezerva zona de memorie in HEAP pentru nodul curent(in functia ElemNou)

5. Se initializeaza cimpul de date al nodului curent cu datele preluate la punctul 2.( t->data=x; in functia ElemNou)

6. Se atribuie pointerului next adesa transmisa functiei ElemNou ce reprezinta adresa elemntului care va urma sau NULL daca este ultimul elemet in lista.( t->next=p; ).

7. Se reinitializeaza p_ultim cu adresa returnata de functia ElemNou (adresa elementului care este adaugat in lista) sau p_cap daca este primul element al listei. ( p_ultim->next=ElemNou(data,NULL); sau p_cap=ElemNou(data,NULL); )

8. Se reinitializeaza p_ultim cu adresa ultimului element din lista.(     p_ultim=p_ultim->next;)sau cu adresa retinuta de p_cap daca este primul element din lista (p_ultim=p_cap;).

9. Procesul se reia de la punctul 2 pentru a adauga un nou nod la lista.

2.2 Accesul la un nod din lista

Pentru a putea acesa un nod al unei liste este nevoie de un pointerul care sa contina adresa primului element al listei si un element de identificare al nodului pe care doresc sa il accesez( fie numarul de ordine al nodului fie dupa o data componenta a nodului respectiv ).

Exemplu o functie care cauta o data anume in cimpurile de date ale nodurilor din lista:

LINK CautaElem(LINK t,DATA x)

- functia primeste ca parametri adresa de inceput a listei si data pe care doresc sa o caut in lista

- conditia din instructiunea while este adevarata atita timp cit nu se ajunge la sfirsitul listei sau nu se gaseste data cautata.

- se parcurge lista nod cu nod pina cind se gaseste data cautata si atunci se returneaza adresa nodului care o contine sau pina la sfirsitul listei caz in care functia returneaza NULL.

Similar se construieste o functie de acees la un nod al listei dupa numarul de ordine al nodului.

2.3 Inserarea unui nod intr-o lista simplu inlantuita inaintea primului ei nod

exemplu: functia InsertPrim

LINK InsertPrim(LINK t,DATA x)

-functia primeste ca parametru adresa de inceput a listei si datele pe care le va contine elementul respectiv din lista.

-declar un nou pointer pe care il initializez cu adresa returnata de functia ElemNou (cea care creaza practic elementul de lista si returneaza adresa acestuia)

-initializez pointerul next al acestui element cu adresa inceputului de lista.

-returnez adresa acestui element si trebuie reinitializat in main pointerul p_cap cu aceasta adresa(moment in care acesta devine primul element al listei).

2.4 Inserarea unui nod inaintea unui nod din lista precizat print-o cheie(pozitia inainte de care vreau sa inserez).

LINK InsertElemI(LINK t,DATA x,int pozitie)

- functia primeste ca parametri: adresa de inceput a listei, datele pe care le va contine elementul inserat in lista si inaintea careia vreau sa inserez.

-declar un pointer local pe care il voi initializa cu adresa de inceput a listei

- se verifica adresa de inceput a listei (daca este NULL inseamna ca lista nu exista si se va crea incepind cu acest element) sau daca pozitia pe care vreau sa inserez este chiar prima pozitie (atunci adresa acestui element va fi si cea de inceput a listei).

- daca lista a fost creata si elementul se insereaza pe alta pozitie valida decit prima in lista se parcurge lista pina la pozitia in care se va face inserarea elementului.

- se apeleaza functia InsertPrim cu adresa elemntului inaintea caruia se face inserarea si datele pe care le va contine nodul respectiv.

- se reinitializeaza adresa continuta de elementul dupa care se face inserarea cu adresa returnata de functia InsertPrim(adica adresa elementului nou adaugat in lista)

2.5 Inserarea unui nod in lista dupa un nod precizat print-o cheie.

- functia de inserare dupa un nod precizat este identica aproape cu cea anterioara, diferenta este la momentul in care se face decrementarea variabilei pozitie, si la conditia din paranteza lui if.(de completat).

LINK InsertElemD(LINK t,DATA x,int pozitie)

2.6 Stergerea primului nod al listei

- se transmite adresa de inceput a listei care se verifica sa nu fie NULL caz in care lista nu exista.

- se verifica apoi daca pozitia de pe care sterg este egala cu zero(corespunzatoare primului element din lista) se retine adresa elemntului imediat urator din lista in pointerul p ,se sterge primul element si se returneaza adresa elementului retinuta in p care va deveni adresa primului element din lista.

- daca pozitia este diferita de zero se apeleaza functia StergElemN(sterge un element de pe o pozite n din lista).

LINK StergElemPrim(LINK t,int pozitie)

if(pozitie==0)

else

2.7 Stergerea unui nod precizat printr-o cheie, din lista

-parametrii primiti de functie este adresa de inceput a listei si pozitia de pe care vreau sa sterg

-se verifica daca elementul de sters este pe prima pozitie in lista si se apeleaza functia StergElemPrim

-daca este alt element al listei se parcurge lista pina la pozitia respectiva si se intra intr-un ciclu for (for(p=t;--pozitie&&p->next!=NULL;p=p->next) ), apoi se verifica daca este ultimul element din lista sau indicele introdus de utilizator este mai mare decit numarul elementelor existente in momentul respectiv si se apeleaza functia (StergElemUltim(t)).

LINK StergElemN(LINK t,int pozitie)

else

}

return t;

}

else

2.8 Stergerea ultimului nod din lista

primeste ca parametru numai adresa de inceput a listei.

-pentru a sterge ultimul element este nevoie de o pozitionare pe ultimul element din lista, dar inainte de a sterge elementul trebuie sa pastrez intr-o variabila pointer adresa penultimului element al listei al carui pointer catre next trebuie reinitializat cu NULL deoarece adresa pe care o contine nu mai este valida fiind adresa elementului care tocmai a fost sters.

LINK StergElemUltim(LINK t)

delete p;

q->next=NULL;

return t;

2.9 Stergerea intregii liste.

-functia parcurge si sterge element cu element de la primul pina la ultimul

LINK StergLista(LINK t)

return NULL;

Programul complet

#include<stdio.h>

#include<stdlib.h>

#include<iostream.h>

typedef int DATA;

//se defineste structura elem

typedef struct elem

ELEMENT,*LINK;

//ELEMENT -(sinonim) reprezinta un element de tipul structurii elem

//LINK - reprezinta un pointer la un element de tipul structurii elem

LINK StergElemPrim(LINK t,int pozitie);

LINK ElemNou(DATA x,LINK p)

t->data=x;

t->next=p;

return t;

void AfisList(LINK p)

LINK InsertPrim(LINK t,DATA x)

//daca pozitie este egala cu zero se insereaza pe prima pozitie in lista

//daca pozitie este 1 se insereaza intre primul si urmatorul element in lista

//daca pozitie este un numar mai mare decit numarul elemntelor existente in lista la

//un momentdat se va insera pe ultima pozitie

LINK InsertElemI(LINK t,DATA x,int pozitie)

else

//daca pozitie este mai mare decit numarul elementelor din lista

//elementul se va insera dupa ultimul element din lista

LINK InsertElemD(LINK t,DATA x,int pozitie)

else

//functia elibereaza memoria heap ocupata de lementele listei

//primeste ca parametru adresa de inceput a listei

LINK StergLista(LINK t)

return NULL;

LINK StergElemUltim(LINK t)

delete p;

q->next=NULL;

return t;

//functia sterge un element din lista inainte de pozitie

LINK StergElemN(LINK t,int pozitie)

else

}

return t;

}

else

LINK StergElemPrim(LINK t,int pozitie)

if(pozitie==0)

else

void main()

else

cout<<'adaugati un nou element in lista'<<endl;

cin>>r;

}

AfisList(p_cap);

//testarea functiei de inserare a unui element dupa un element dat printr-o cheie

int poz=0;

cout<<'introduceti pozitia dupa care se va insera un elmentn';

cin>>poz;

cout<<'initializati cimpul data al elemntului inserat cu un intreg'<<endl;

cin>>data;

p_cap=InsertElemD(p_cap,data,poz);

AfisList(p_cap);

//testarea functiei de inserare a unui element inaintea unui element dat printr-o cheie

cout<<'introduceti pozitia inainte de care se va insera un elmentn';

cin>>poz;

cout<<'initializati cimpul data al elemntului inserat cu un intreg'<<endl;

cin>>data;

p_cap=InsertElemI(p_cap,data,poz);

AfisList(p_cap);

//de testat inserarea unui element pe prima pozitie

cout<<'elemntul urmator se va insera pe prima pozitien';

cin>>poz;

cout<<'initializati cimpul data al elemntului inserat cu un intreg'<<endl;

cin>>data;

p_cap=InsertPrim(p_cap,data);

AfisList(p_cap);

cout<<'introduceti pozitia de la care sterg un elementn';

cin>>poz;

p_cap=StergElemN(p_cap,poz);

AfisList(p_cap);

cout<<'se sterge intreaga lista; se elibereaza memoria heapn';

p_cap=StergLista(p_cap);

AfisList(p_cap);