Liste Dublu Inlantuite

 

Listele dublu inlantuite sunt structuri de date dinamice omogene. Ele au aceleasi caracteristici de baza ca si listele simplu inlantuite. Diferenta fata de acestea consta in faptul ca, pentru fiecare nod, se retine si adresa elementului anterior, ceea ce permite traversarea listei in ambele directii.

 

Lista dublu inlantuita poate fi reprezentata grafic astfel:

 

1. Structura listei

 

Structura folosita este similara cu cea de la liste simple.

 

Pentru a asigura un grad mai mare de generalitate listei a fost creat un alias pentru datele utile (in cazul nostru un intreg):

 

// Datele asociate unui

// element dintr-o lista

typedef int Date;

 

In cazul in care se doreste memorarea unui alt tip de date, trebuie schimbata doar declaratia aliasului Date.

 

Pentru memorarea listei se foloseste o structura autoreferita. Acesta structura va avea forma:

 

// Structura unui element

// dintr-o lista dublu inlantuita

struct Element

{

††††† // datele efective memorate

††††† Date valoare;

††††† // legatura catre nodul urmator

††††† Element* urmator, * anterior;

};

 

In cazul in care elemenul este ultimul din lista, pointerul urmator va avea valoarea NULL. Pentru primul element, pointerul anterior va avea valoarea NULL.

 

Declararea listei se face sub forma:

// declarare lista vida

Element* cap = NULL;

 

In cazul in care se doreste crearea unei liste circulare, pointerul urmator al ultimului element va referi primul element al listei, iar pointerul anterior al primului element va referi ultimul element.

2. Operatii cu liste duble

Principalele operatii cu liste sunt:

Parcurgere si afisare lista

Lista este parcursa pornind de la pointerul spre primul element si avansand folosind pointerii din structura pana la sfarsitul listei (pointer NULL).

 

// Parcurgere si afisare lista dubla

void Afisare(Element* cap)

{

††††† // cat timp mai avem elemente

††††† // in lista

††††† while (cap != NULL)

††††† {

††††††††††† // afiseaza elementul curent

††††††††††† cout << cap->valoare << endl;

 

††††††††††† // avanseaza la elementul urmator

††††††††††† cap = cap->urmator;

††††† }

}

 

Pentru parcurgerea inversa a listei se va porni cu un pointer catre ultimul element al listei, iar avansarea se va face folosind secventa cap = cap->anterior; .

 

Inserare element

Inserarea unui element se poate face la inceputul sau la sfarsitul listei.

a) Inserare la inceput

Acesta este cazul cel mai simplu: trebuie doar alocat elementul, legat de primul element din lista si repozitionarea capului listei:

 

// Inserare element la inceputul unei

// liste dublu inlantuite

void InserareInceput(Element* &cap, Date val)

{

††††† // Alocare nod si initializare valoare

††††† Element *elem = new Element;

††††† elem->valoare = val;

††††† elem->anterior = NULL;

†††††

††††† // legare nod in lista

††††† elem->urmator = cap;

††††† if (cap != NULL)

††††††††††† cap->anterior = elem;

†††††

††††† // mutarea capului listei

††††† cap = elem;

}

 

b) Inserare la sfarsitul listei

 

In acest caz trebuie intai parcursa lista si dupa aceea adaugat elementul si legat de restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

 

// Inserare element la sfarsitul unei

// liste dublu inlantuite

void InserareSfarsit(Element* &cap, Date val)

{

††††† // Alocare si initializare nod

††††† Element *elem = new Element;

††††† elem->valoare = val;

††††† elem->urmator = NULL;

††††† elem->anterior = NULL;

 

††††† // daca avem lista vida

††††† if (cap == NULL)

††††††††††† // doar modificam capul listei

††††††††††† cap = elem;

††††† else

††††† {

††††††††††† // parcurgem lista pana la ultimul nod

††††††††††† Element *nod = cap;

††††††††††† while (nod->urmator != NULL)

††††††††††††††††† nod = nod->urmator;

 

††††††††††† // adaugam elementul nou in lista††††††††

††††††††††† nod->urmator = elem;

††††††††††† elem->anterior = nod;

††††† }††††

}

 

c) inserare dupa un element dat

 

void InserareInterior(Element* &cap, Element* p, Date val)

{

††††† // Alocare si initializare nod

††††† Element *elem = new Element;

††††† elem->valoare = val;

††††† elem->urmator = NULL;

††††† elem->anterior = NULL;

 

††† // lista vida

††††† if (cap == NULL)

††††† {

††††† ††††† cap = elem;

††††††††††† return;

††††† }

 

††††† // inserare la inceputul listei

††††† if (cap == p)

††††† {

††††††††††† elem->urmator = cap;

††††††††††† cap->anterior = elem;

††††††††††† cap = elem;

††††††††††† return;

††††† }

 

††††† // inserare in interior

††††† elem->urmator = p->urmator;

††††† elem->anterior = p;

††††† p->urmator->anterior = elem;

††††† p->urmator = elem;

†††††

}

Cautare element

Cautarea unui element dintr-o lista presupune parcurgerea listei pentru identificarea nodului in functie de un criteriu. Cele mai uzuale criterii sunt cele legate de pozitia in cadrul listei si de informatiile utile continute de nod. Rezultatul operatiei este adresa primului element gasit sau NULL.

 

a) Cautarea dupa pozitie

 

Se avanseaza pointerul cu numarul de pozitii specificat:

 

// Cautare element dupa pozitie

Element* CautarePozitie(Element* cap, int pozitie)

{

††††† int i = 0;// pozitia curenta

†††††

††††† // parcurge lista pana la

††††† // pozitia ceruta sau pana la

††††† // sfarsitul listei

††††† while (cap != NULL && i < pozitie)

††††† {

††††††††††† cap = cap->urmator;

††††††††††† i++;

††††† }

 

††††† // daca lista contine elementul

††††† if (i == pozitie)

††††††††††† return cap;

††††† else

††††††††††† return NULL;

}

 

b) Cautarea dupa valoare

 

Se parcurge lista pana la epuizarea acesteia sau identificarea elementului:

 

// Cautare element dupa valoare

Element* CautareValoare(Element* cap, Date val)

{

††††† // parcurge lista pana la gasirea

††††† // elementului sau epuizarea listei

††††† while (cap != NULL && cap->valoare != val)

††††††††††† cap = cap->urmator;

 

††††† return cap;

}

 

Stergere element

 

a) Stergerea unui element din interiorul listei (diferit de capul listei)

 

// sterge un element din interiorul listei

// primind ca parametru adresa elementului

void StergereElementInterior(Element* elem)

{

††††† // scurcircuitam elementul

††††† elem->anterior->urmator = elem->urmator;

††††† elem->urmator->anterior = elem->anterior;

†††††

††††† // si il stergem

††††† delete elem;†††††

}

 

b) Stergerea unui element de pe o anumita pozitie

 

Daca elementul este primul din lista, atunci se modifica capul listei, altfel se cauta elementul si se sterge folosind functia definita anterior:

 

void StergerePozitie(Element* &cap, int pozitie)

{

††††† // daca lista e vida nu facem nimic

††††† if (cap == NULL)

††††††††††† return;

 

††††† // daca este primul element, atunci

††††† // il stergem si mutam capul

††††† if (pozitie == 0)

††††† {

††††††††††† Element* deSters = cap;

††††††††††† cap = cap->urmator;

††††††††††† cap->anterior = NULL;

††††††††††† delete deSters;

††††††††††† return;

††††† }

 

††††† // daca este in interor, atunci folosim

††††† // functia de stergere

††††† Element* elem = CautarePozitie(cap, pozitie);

††††† StergereElementInterior(elem);†††††

}

 

c) stergerea dupa o valoare

 

Se cauta elementul si se foloseste functia de stergere element:

 

void StergereValoare(Element* &cap, Date val)

{

††††† // daca lista e vida nu facem nimic

††††† if (cap == NULL)

††††††††††† return;

 

††††† // daca este primul element, atunci

††††† // il stergem si mutam capul

††††† if (cap->valoare == val)

††††† {

††††††††††† Element* deSters = cap;

††††††††††† cap = cap->urmator;

††††††††††† cap->anterior = NULL;

 

††††††††††† delete deSters;

††††††††††† return;

††††† }

 

††††† // cautam elementul

††††† Element* elem = CautareValoare(cap, val);

 

††††† // daca a fost gasit, atunci il stergem

††††† if (elem->urmator != NULL)

††††††††††† StergereElementInterior(elem);

}

3. Probleme

1. Definiţi conceptul de listă dublu circulară şi enumeraţi proprietăţile.

2. Scrieţi funcţia pentru conversia unei liste duble Ón listă simplă.

3. Sa se scrie functia pentru adunarea a doua matrice rare memorate ca liste duble.

4. Fiind dată o listă dublă rezultată din adunarea a două matrice rare scrieţi funcţia pentru normalizare.

5. Sa se scrie o functie recursive care afiseaza elementele unei liste duble in ambele sensuri in functie de optiune.

6. Scrieti functia nerecursiva care efectueaza copierea unei liste, cu eliminarea elementelor ce au ca informatie utila o valoare mai mica decat un nivel specificat de parametru.

7. Scrieti si apelati functia care concateneaza o lista dubla cu o copie a sa.

8. Scrieţi funcţia pentru numărarea elementelor din n liste duble, Ón mod separat.

9. Sa se scrie functia pentru concatenarea a n liste dublu inlantuite.