Liste circulare

Liste circulare

Definitie:

Listele circulare simplu inlantuite sunt liste liniare simplu inlantuite cu deosebirea ca nu exista ultimul element, adica pointerul de legatura din ultimul element al listei liniare nu are valoarea NIL, ci indica spre primul element.

Ca si listele liniare, listele circulare pot pot sa fie simplu inlantuite sau dublu inlantuite. Vom considera in continuare fiecare din cele doua cazuri in parte.

Structura unui element al unei liste circulare fiind aceeasi cu a unuia dintr-o lista liniara, putem reprezenta o lista circulara grafic astfel:

Exista pointerul notat tot p0 care indica spre primul element al listei circulare, acesta fiind elementul de intrare in lista. Considerand p0 ca un element al listei, de o structura speciala, se obtine reprezentarea grafica urmatoare a unei liste circulare simplu inlantuita (p0 se numeste capul listei).

In afara de capul listei celelalte elemente au structura:

typedef struct clista

pclista;

unde:

key -reprezinta campul cheii de identificare al elementului

next - este pointerul spre urmatorul element al listei, iar capul listei este p0:*clista.

In mod analog se definesc listele circulare dublu inlantuite.

Grafic avem:

Se pastreaza pointerul 'pp' care memoreaza adresa primului element al listei, el constituind astfel purtatorul de intrare in lista.

Un element dintr-o lista circulara dublu inlantuita are aceeasi structura ca si unul dintr-o lista liniara dublu inlantuita.

typedef struct clistad

pclistad;

in care campurile au aceeasi semnificatie.

Parcurgerea listelor circulare

Ca si in cazul listelor liniare, parcurgerea listei poate fi o traversare sau o cautare a unui anumit element. Toti algoritmii urmatori presupun ca listele nu sunt vide (trebuie facuta in prealabil o testare a acestora ).

a)Traversarea listelor circulare

Traversarea listelor presupune parcurgerea tuturor elementelor de la primul element (capul listei) pana se revine inapoi la acesta. O lista circulara simplu inlantuita se poate traversa in ambele sensuri, trebuind precizat sensul de traversare.

Traversarea unei liste simplu inlantuite

p=p0;

while (p->next!=p0) p=p->next;

Traversarea unei liste dublu inlantuite spre dreapta

p=pp;

while (p->right!=pp) p=p->right;

Analog se face si traversarea spre stanga.

b) Cautarea unui element intr-o lista circulara

Cautarea se face dupa cheia de identificare a unui element si algoritmii sunt similari cu cei de la listele liniare. Ca si traversarea, cautarea unui element se poate face intr-un sens la listele simple inlantuite si in doua sensuri la listele dublu inlantuite.

Cautarea unui element cu cheia x intr-o lista circulara simplu inlantuita;

p=p0;

while (p->key!=x || p->next!=p0) p=p->next;

if (p->key==x) ..

Cautarea unui element intr-o lista circulara dublu inlantuita :

p=pp;

while (p->key<=x || p->right!=pp) p=p->right;

if (p->key==x)

c) Eliminarea unui element dintr-o lista circulara

Prezinta interes doar eliminarea elementului care se afla imediat dupa punctul de intrare in lista (pointerul p0 sau pp). Celelalte cazuri sunt identice cazurilor de la listele liniare.

Cazul listelor simplu inlantuite

Trebuie cautat deci ultimul articol (inscrisul celui dinainte de p0) si modificat campul "next" al acestuia, precum si modificarea valorii lui p0.

Presupunem ca s-a facut cautarea si p indica spre ultimul element. Atunci trebuie executate instructiunile:

p0=p0->next;

p->next=p0;

Cazul listelor dublu inlantuite

In acest caz nu mai este nevoie sa se caute ultimul element el se gaseste usor cu pointerul 'left' al capului listei.

pp->left->right=pp->right;

pp->right->left=pp->left;

pp=pp->right;

Observatie:

In cazul listelor cu un singur element, actiunile de mai sus nu au sens. Intr-adevar grafic o lista circulara cu un singur element se poate reprezenta:

In acest caz, eliminarea unicului element, duce la o lista vida. Deci, in acest caz vom avea:

p0:=NIL;(pentru listele simplu inlantuite)

pp:=NIL;(pentru listele dublu inlantuite)

d) Inserarea unui element intr-o lista circulara

Si in acest caz trebuie sa deosebim o lista vida (fara nici un element) sau una nevida. Consideram de data aceasta mai intai cazul listelor vide, cand p0 (sau pp la listele duble) au valoarea NIL. Inserarea unui element intr-o lista vida inseamna crearea unui element (cu informatia aferenta) si legarea lui de el insusi.

Grafic, lista trebuie sa arate astfel:

Trebuie deci executate actiunile (pentru cele doua cazuri):

p0=(pclistad *)malloc(sizeof(pclistad));

p=p0;

p->next=p0;

Respectiv:

pp=(pclistad *)malloc(sizeof(pclistad));

p=pp;

p->right=pp;

p->left=pp;

In continuare presupunem ca lista este creata si inserarea unui nou element in lista (inserarea elementelor in cazul ca sunt mai mult decat doua, intre primul element si ultimul element nu intereseaza acum) este identica cu cea de la listele liniare. Prezinta interes inserarea unui element inainte sau dupa pointerul de intrare in lista (p0 sau pp).

Cazul listelor simplu inlantuite

In ambele cazuri este necesara cautarea ultimului element si pentru modificare presupunem in continuare ca p indica spre ultimul element.

Atunci inserarea dupa pointerul p0 se poate reprezenta grafic astfel:

Am notat cu 'p1' pointerul ce indica adresa din memorie a elementului ce se introduce. In acest caz trebuie executate actiunile:

Inserare inainte de pointerul p0.

p1=(pclistad *)malloc(sizeof(pclistad));

p->next=p1;

p1->next=p0->next;

p0=p1;

Algoritmic:

p1=(pclistad *)malloc(sizeof(pclistad));

p->next=p1;

p1->next=p0;

Se observa ca in acest caz nu se mai modifica valoarea lui p0. Din acest motiv, ultimul caz de inserare este mai simplu si mai avantajos.

Cazul listelor dublu inlantuite

Nici in acest caz nu este nevoie de cautarea ultimului element.

Inserarea dupa pointerul pp:

p1=(pclistad *)malloc(sizeof(pclistad));

p1->right=pp;

p1->left=pp->left;

pp->left->right=p1;

pp->left=p1;

pp=p1;

Inserarea inainte de pointerul 'pp' :

p1=(pclistad *)malloc(sizeof(pclistad));

p1->right=pp;

p1->left=pp->left;

pp->left->right=p1;

pp->left=p1;

Nici in acest caz nu a mai fost nevoie de modificarea valorii lui pp.

Crearea listelor circulare

Prima etapa in crearea listelor circulare, fie ca este simpla sau dublu inlantuita, consta in crearea listei vide.

A doua etapa consta in crearea listei cu un singur element, asa cum a fost descris anterior.

In a treia etapa, se insereaza cat timp se doreste un element nou in lista (de preferinta inaintea pointerului cap de lista), tot dupa modul descris inainte.

Observatie:

In cazul listelor simplu inlantuite, operatiile de stergere si inserare de elemente presupun in prealabil detectarea elementului dinaintea capului listei (numit impropriu ultimul element).

Aceste operatii se pot reduce eliminandu-se cautarea ultimului element, daca intrarea in lista se face prin ultimul element.

In acest fel, eliminarea, respectiv inserarea elementului ce urmeaza dupa pointerul 'p0' se poate face astfel:

p0->next=p0->next->next;

p1=(pclistad *)malloc(sizeof(pclistad));

p1->next=p0->next;

p0->next=p1;

Probleme rezolvate

Sa se scrie un program care formand liste circulare simplu inlantuite realizeaza adunarea a doua polinoame.

Consideram un polinom de trei variabile:

P(x, y, z) =

unde am notat cu pi coeficientii urmatoarelor monoame de forma:

Pentru fiecare termen al polinomului consideram un element cu structura:

-coef-coeficientul monomului

-a,b,c-puterile la care se afla variabilele x,y,z

-un camp de semn care este pozitiv tot timpul in afara de un mod special corespunzator sfarsitului unui polinom (cand este -)

-un pointer spre urmatorul element din lista.

Campurile a,b,c fiind de numere intregi, vom considera un singur camp format din cifrele a,b,c.

De exemplu pentru monomul: vom avea coef=5, abc=+251; Pentru nodul special vom avea abc=-1

Rezulta structura:

typedef struct polinom

ppolinom;

Algoritmul de adunare al polinoamelor poate fi exprimat astfel:

Pas1. Initializare: se stabilesc punctele de intrare in lista polinoamelor de adunat (notate P si Q ).

Pas2. Se compara abc(p) cu abc(q). Daca abc(p)<abc(q) se merge la urmatorul element din q si se repeta secventa din 2. Daca abc(p)=abc(q) se trece la pasul 3. Daca abc(p)>abc(q) se trece la pasul 5.

Pas3. Se aduna coeficientii: coef(q)=coef(p)+coef(q). Daca abc(p)<0 algoritmul se termina. Daca coef(q)=0 se trece la pasul 4. In caz contrar avanseaza in listele q si p cu un element si se sare la pasul 2.

Pas4. Stergerea termenilor nuli. Se elimina elementul creat din lista q si se trece la pasul 2.

Pas5. Inserarea unui nou termen. Polinomul p contine un termen ce nu este prezent in q astfel el va fi inserat in polinomul q. Se trece elementul din p in q si se revine la pasul 2. Algoritmul va contine in lista q suma dintre polinoamele p si q.

#include <stdio.h>

#include <stdlib.h>

typedef struct polin

ppolin;

ppolin *p0, *q0, *p, *q, *q1, *q2;

int i, j, k, e;

char ch;

void main()

while (!(ch == 'n'));

q0 = (ppolin *)malloc(sizeof(ppolin));

q0->coef = 0;

q0->abc = -1;

q0->next = p0;

printf('introduceti pentru fiecare monom, coef si abc:n');

do while (!(ch == 'n'));

p = p0->next;

q = q0->next;

e = 0;

while (e == 0)

if (p->abc < q->abc)

else

if (p->abc == q->abc)

if (p->abc < 0) e = 1;

else

else

}

else

q = q->next;

printf('polinomul suma:coef-abc');

while (q->next->abc >= 0)

Observatie:

S-a folosit variabila 'e' pentru a determina sfarsitul algoritmului, care in prealabil a fost structurat.

Probleme propuse

1. Sa se creeze si apoi sa se inverseze o lista circulara dublu legata, plecand de la un vector de numere reale.

2. Aceeasi problema ca problema 4 din problemele propuse la lista liniara dublu legata, dar relativ la lista circulara (simpla si dublu legata).

3. Sa se transforme o lista circulara simplu legata intr-o lista liniara dublu legata.

4. Sa se transforme o lista liniara simplu legata intr-o lista circulara dublu legata;

5. Sa se transforme o lista circulara simplu legata intr-o lista circulara dublu legata.

6. Sa se creeze o lista circulara simplu legata si sa se inverseze elementele acesteia generind o alta lista circulara dublu legata. Sa se listeze apoi elementele celor doua liste.

7. Sa se creeze o lista circulara dublu legata si sa se inverseze elementele acesteia generind o alta lista circulara simplu legata si sa se listeze apoi elementele celor doua liste.

8. Sa se creeze o lista circulara simplu legata cu elemente numere intregi si sa se extraga apoi din aceasta lista elementele cu chei negative. Sa se listeze in final elementele celor doua liste.

9. Sa se scrie o procedura care elimina dintr-o lista circulara simplu legata elementele care se repeta, pastrindu-se ordinea relativa a elementelor.

10. Se considera o lista circulara simplu legata ale carei elemente sint distincte doua cite doua. Sa se construiasca o lista circulara simplu legata ale carei elemente sint la rindul lor liste circulare simplu legate ale caror elemente formeaza submultimi ale multimii elementelor listei initiale.

11. O modalitate de reprezentare a unei familii de multimi o constituie utilizarea unei liste circulare simplu legate ale carei elemente sint liste liniare simplu legate, fiecare reprezentind una dintre multimile familiei de multimi respective. Sa se reprezinte o familie de multimi in acest mod.

12. Sa se scrie o procedura care determina numarul de noduri ale unei liste circulara simplu legate.