Liste inlantuite - Inserarea unui nod intr-o lista simplu inlantuita circulara

Liste inlantuite

Intalnim si utilizam liste in fiecare zi: la scoala, profesorul are cate o lista cu elevii fiecarei clase - catalogul; la restaurant gasim o lista cu produsele oferite si preturile lor - meniul; la o firma de calculatoare vom primi o lista de componente si preturi - oferta s.a.m.d. Prin urmare, utilizam liste ori de cate ori este necesar sa organizam intr-o forma secventiala un ansamblu de informatii.

Lista este o structura de date abstracta constituita dintr-o succesiune de elemente. Fiecare element din lista are un succesor si un predecesor.

Observatii

1. Niciunul dintre nodurile unei liste circulare nu contine valoarea NULL in partea de legatura. Operatiile elementare asupra listelor simplu inlantuite circulare vor fi implementate tinand cont de aceasta observatie.
2. Pentru a identifica o lista simplu inlantuita circulara putem retine adresa oricarui element din lista.

Inserarea unui nod intr-o lista simplu inlantuita circulara

Pentru inserare vom implementa o functie numita Insert cu 3 parametri:

1. Prim - pointer care contine adresa primului nod din lista in care se face inserarea; acest parametru va fi transmis prin referinta, deoarece in urma inserarii inceputul listei se poate modifica;
2. p - pointer care contine adresa nodului din lista dupa care se face inserarea;
3. x - informatia nodului care urmeaza sa fie inserat in lista.

Vom aloca dinamic memorie pentru un nou nod, a carui adresa o vom retine in variabila pointer q. In zona de informatii vom memora valoarea x (q->inf=x

La inserare aar doua cazuri distincte. Daca Prim==NULL (lista este vida) noul nod inserat va fi singurul element din lista (deci in partea de legatura von retine adresa sa); daca Prim!=NULL inserarea se face in interiorul listei.

void Insert(Lista & Prim, Lista p, int x)

else

}

Stergerea unui nod dintr-o lista simplu inlantuita circulara

Pentru stergere vom implementa o functie denumita Delete cu doi parametri:

1. Prim - pointer care contine adresa primului nod al listei din care se face stergerea; acest parametru va fi transmis prin referinta, deoarece in urma stergerii, inceputul listei se poate modifica;
2. p - pointer care contine adresa nodului din lista care preceda nodul ce urmeaza a fi sters (se transmite adresa nodului precedent si nu adresa nodului de sters pentru a putea restaura corect legaturile in lista).

Si la stergere apar doua cazuri distincte. Daca p->urm==Prim va fi sters primul nod din lista, deci valoarea parametrului Prim va fi actualizata (va primi adresa urmatorului nod din lista sau NULL daca lista era formata dintr-un singur nod); daca p-<urm!=Prim va fi sters un nod oarecare din interiorul listei.

void Delete(Lista & Prim , Lista p)

delete q;

}

Parcurgerea unei liste simplu inlantuite circulare

Pentru a parcurge o lista simplu inlantuita circulara, vom utiliza un pointer p, caruia ii vom atribui initial adresa primului element din lista. La fiecare pas, se viziteaza nodul curent, apoi se trece la nodul urmator (p=p->urm), pana cand se revine la nodul de plecare. Functia urmatoare realizeaza parcurgerea unei liste simplu inlantuite circulare cu afisarea informatiilor din noduri:

void Afisare(Lista Prim)

while (p!=Prim);

cout<<endl;

}