LISTE CIRCULARE SIMPLU INLANTUITE

LISTE CIRCULARE SIMPLU INLANTUITE

Continutul lucrarii

Ilustrarea principalelor tehnici de implementare a structurii de date.

Consideratii teoretice

Fie o lista simplu inlantuita ca in figura de mai jos:

Daca in lista de mai sus pointerul ultimului element va indica primul element, se va obtine o lista circulara simplu inlantuita. (ultim -> urm = prim).

Intr-o lista circulara toate nodurile sunt echivalnte, fiecare nod are un urmator si fiecae nod este urmatorul altui nod. Intr-o lista circulara nu exista capete. Pentru a gestiona o lista circulara se va folosi un pointer ptr_nod, acesta indicand un nod oarecare al listei.

Ca si la lista simplu inlantuita, principalele operatii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

stergerea unui nod,

stergerea listei.

Structura unui nod este urmatoarea:

typedef struct nod NOD;

Crearea listei circulare simplu inlantuite

Initial lista este vida:

ptr_nod = 0;

Introducerea in lista a unui nod se va face dupa nodul curent (ptr_nod) astfel:

a)                                               Daca ptr_nod este zero , insemna ca lista este vida si nodul ce va trebui introdus este singurul nod din lista

b)                                               Daca ptr_nod nu este zero, lista contine lemente si introducerea noului nod se va realiza dupa nodul curent (ptr_nod)

/* crearea nodului */

p = (NOD *)malloc(sizeof(NOD));/* rezervarea memorie */

p->info=KEY;

//citire date in nod la adresa p;

if (ptr_nod = = 0)

else

Accesul la un nod

Nodurile se acceseaza secvential pornind de la nodul curent (ptr_nod).

p=ptr_nod;

if(p! = 0) /* lista nu este vida */

do

while (p! = ptr_nod);

Inserarea unui nod

Se pun urmatoarele probleme:

inserarea inaintea unui nod de cheie data;

inserarea dupa un nod de cheie data.

In ambele cazuri se cauta nodul de cheie data avand adresa q; daca exista un astfel de nod ,se creeaza nodul de inserat de adresa p si se fac legaturile corespunzatoare.

a)      Inserarea inaintea unui nod de cheie data

se cauta nodul de cheie data, tinandu-se minte nodul anterior

daca nodul a fost gasit atunci se realizeaza inserarea, nodul anterior va pointa catre noul nod (p), iar nodul p va pointa catre nodul de cheie data (q)

b)      Inserarea dupa un nod de cheie data

se cauta nodul de cheie data:

daca nodul s-a gasit, se insereaza noul nod:

p->urm=q->urm;

q->urm=p;

Stergerea unui nod de cheie data

Stergerea unui nod de cheie data key se va face astfel:

se cauta nodul de cheie data:

q = ptr_nod;

do

while (q! = ptr_nod);

se sterge nodul

if (q-> info == key)

free(q);

Stergerea listei

Stergerea listei circulare simplu inlantuite se va face astfel:

p = ptr_nod;

do

while (p! = ptr_nod);

ptr_nod = 0;