O lista circulara este o lista in reprezentare inlantuita care are proprietatea ca ultimul nod pointeaza la primul nod al listei in loc sa aiba drept componenta pointerul NULL.
HEAD
info info link info link
...
Operatiile
cu o lista circulara se descriu 
astfel:
accesarea/ modificarea unui element ce contine o valoare data k, k de tip T, se face la fel ca in cazul listei liniare, algoritm descris in capitolul 1.
inserarea unui nou nod
o la inceputul listei (sau la sfarsitul listei, este acelasi lucru):
Algoritm: Folosim variabilele info_nou ce contine valoarea informatiei nodului ce trebuie introdus in lista, p pointer la un nod si iter care initial pointeaza la primul nod al listei si va parcurge lista pana cand acesta va pointa la ultimul nod din lista.
Aloca memorie pentru un nod nou. Returneaza p, un pointer la noul nod.
if p NULL then
p -> link = HEAD
p -> info = info_nou
iter = HEAD
while (iter -> link != HEAD)
iter = iter -> link
endwhile
iter -> link =p
HEAD = p
else OVERFLOW
endif
HEAD
...
info_nou 
p
o dupa un nod dat: se face la fel ca in cazul listei liniare, algoritm descris in capitolul 1.
eliminarea unui nod dat din lista:
o eliminarea primului nod
Algoritm: Folosim variabila iter care initial pointeaza la primul nod al listei si va parcurge lista pana cand acesta va pointa la ultimul nod din lista.
elem_sters = HEAD -> info
iter = HEAD
while (iter -> link != HEAD)
iter = iter -> link
endwhile
iter -> link = HEAD -> link
HEAD = HEAD -> link
HEAD
info info link info link
...
Algoritm: Folosim variabila iter care initial pointeaza la primul nod al listei si va parcurge lista pana cand acesta va pointa la penultimul nod din lista.
iter = HEAD
while (iter NULL and iter -> link HEAD and (iter -> link) ->link HEAD)
iter = iter -> link
endwhile
if iter = NULL then UNDERFLOW
else if iter -> link = HEAD then elem_sters = iter ->info
else elem_sters = (iter - >link) ->info
iter -> link = HEAD
endif
endif
HEAD iter
info link info info link
....
o eliminarea altui nod din lista se face la fel ca in cazul listei liniare, algoritm
descris in capitolul 1.
Scrieti
un program care implementeaza algoritmii de mai sus.
|
