|
|
|
ALGORITMI PENTRU PRELUCRAREA LISTELOR DUBLU INLANTUITE
In cazul listelor dublu inlantuite, informatia de legatura trebuie sa contina si adresa succesorului nodului (pointerul *ant catre tipul nod):
struct nod
; // informatia pentru legatura
nod *prim, *ultim, *p; // pointeri pentru exploatarea listei
Fata de algoritmii corespunzatori de la listele simplu inlantuite, in cazul de fata trebuie intretinuta si adresa de legatura cu predecesorul nodului.
I. Crearea listei
Algoritmul de creare a unei liste (adaugarea primului nod la lista)
Se foloseste functia procedurala adaug_prim(), al carei parametru prim, de tip nod, se transmite prin referinta (sunt parametri de iesire).
void adaug_prim (nod *&prim)
II. Dupa ultimul nod
Se foloseste functia procedurala adaug_ultim(), al carei parametru ultim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void adauga_ultim (nod *&ultim)
2. In interiorul listei
2.a. In interiorul listei – dupa nodul cu adresa q.
Nodul p care se adauga se insereaza intre nodul q si succesorul lui q (nodul q→urm).
Astfel, nodul p va avea ca predecesor nodul q (va fi succesorul lui q), iar ca succesor nodul q→urm (va fi predecesorul lui q→urm)
Se foloseste functia procedurala adaug_dupa(), ai carei parametri de tip nod, se transmit astfel:
- q (adresa nodului dupa care se face inserarea) se transmite prin valoare (este parametru de intrare);
- ultim (adresa ultimului nod) se transmite prin referinta (este parametru de intrare-iesire).
void adauga_dupa (nod *q, nod *&ultim)
;
2.b. In interiorul listei – inainte de nodul cu adresa q.
Nodul p care se adauga se insereaza intre succesorul lui q (nodul q→urm) si nodul q.
Astfel, nodul p va avea ca predecesor nodul q→urm (va fi succesorul lui q→urm), iar ca succesor nodul q, (va fi predecesorul lui q).
Se foloseste functia procedurala adaug_in_fata(), al carei parametru q, de tip nod, se transmite prin valoare (este parametru de intrare);
void adauga_in_fata (nod *q)
void parcurge_inapoi (nod *ultim)
IV. Eliminarea unui nod din lista
1. Eliminarea primului nod
Se foloseste functia procedurala elimina_prim(), al carei parametru prim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void elimina_prim (nod *&prim)
2. Eliminarea ultimului nod
Se foloseste functia procedurala elimina_ultim(), al carei parametru ultim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void elimina_ultim (nod *&ultim)
3. Eliminarea unui nod din interiorul listei
Trebuie eliminat nodul p, deci predecesorul lui p (p→ant) trebuie legat de succesorul sau (p→urm). Astfel, nodul p→ant va avea ca succesor p nodul p→urm, iar nodul p→urm va avea ca predecesor nodul p→ant.
Se foloseste functia procedurala elimina(), al carei parametru p, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void elimina (nod *p, nod *&ultim)
