Liste circulare simplu înlănțuite

O lista circulara simplu inlantuita este o lista in care ultimul element contine campul ce adreseaza elementul urmator, adresa primului element.

Crearea unei liste circulare se realizeaza in mod asemanator cu o lista liniara simplu inlantuita, cu deosebirea ca ultimul element adaugat in lista nu va mai avea in campul de adresa valoarea NIL, ci adresa primului element adaugat.

1. 2. Crearea unei liste circulare cu numar cunoscut de elemente Vom crea mai intai primul element al listei. Folosind un ciclu for vor fi adaugate la sfarsitul listei celelalte elemente. In final campul de adresa al ultimului element adaugat va contine adresa primului element.

Vom utiliza pointerii: pr contine adresa primului element adaugat in lista; ul contine adresa ultimului element adaugat in lista; p contine adresa elementului ce se adauga.

Procedure creare (var p: lista); Var p, ul: lista; i: integer; begin new (pr); readln (pr^. inf); ul: =pr; for i: = 1 to n-1 do begin new (p); readln (p^. inf); ul^. adr: =p; ul: =p; end; ul^. adr: pr; end; 1. 3. Afisarea elementelor unei liste circulare Parcurgem nodurile listei cu ajutorul unui pointer care plecand de la un element al listei, va referi pe rand fiecare nod al listei, pana cand va adresa nodul de pornire.

Parcurgerea folosind un ciclu while Procedure parc1 (pr: lista); var p: lista; begin p: =pr; while (p^. adrpr) do begin write (p^. inf, ); p: = p^. adr; end; write (p^. inf); end; Parcurgerea folosind un ciclu repeat Procedure parc2 (pr: lista); var p: lista; begin p: =pr; repeat write (p^. inf, ); p: =p^. adr; until p=pr; end; 1. 4. Adaugarea unui element intr-o lista circulara Sa se scrie un subprogram ce realizeaza inserarea unui nod dupa elementul de cheie k dintr-o lista circulara.

Observam ca intr-o lista circulara putem accesa toate elementele listei pornind din orice nod al acesteia. Avand in vedere acest lucru, pentru a evita tratarea cazului particular de inserare inainte primului element, vom parcurge lista prin intermediul lui pr, salvand adresa primului element intr-o variabila p.

Procedure adaug (var pr: lista; k: integer); var p: lista; begin p: =pr: repeat if pr^. inf=k then begin new (q); readln (q^. inf); q^adr: = pr^. adr; pr: =p; end; else pr: =pr^. adr; until (pr=p); end; 1. 5. Eliminarea elementelor dintr-o lista circulara Sa se scrie un subprogram ce realizeaza eliminarea elementelor de cheie para dintr-o lista circulara.

In situatia in care toate elementele sunt pare lista devine vida. Punem in evidenta acest lucru prin pr: =nil. Parcurgem lista prin pr, pozitionandu-ne pe elementul anterior care trebuie sters.

Procedure elimin (var pr: lista); var p, q: lista; begin p: =pr; while pr^. adrp do if pr^. adr^. inf mod 2 = 0 then begin {se elimina pr^. adr} q: =pr^. adr; pr^. adr: =q^. adr; dispose (q); end else ...