Liste circulare simplu inlantuite

LISTE CIRCULARE SIMPLU INLANTUITE

Continutul lucrarii

In lucrare sunt prezentate principalele operatii asupra listelor circulare simplu inlantuite: crearea, inserarea unui nod, stergerea unui nod  si stergerea listei.

Consideratii teoretice

Lista circulara simplu inlantuita este lista simplu inlantuita a carei ultim element este legat de primul element; adica ultim -> urm = prim.

In cadrul listei circulare simplu inlantuite nu exista capete. Pentru gestionarea ei se va folosi un pointer ptr_nod, care adreseaza un nod oarecare al listei, mai precis ultimul introdus(fig.2.1.).

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 tip_nod TIP_NOD;

Crearea listei circulare simplu inlantuite

Initial lista este vida:

ptr_nod = 0;

Introducerea in lista a cate unui nod se va face astfel:

/* crearea  nodului */

n = sizeof(TIP_NOD);                /* dimensiunea nodului */

p = (TIP_NOD *)malloc(n);       /* rezervarea memorie in heap */

citire date in nod la adresa p;

if (ptr_nod = = 0)

else

Accesul la un nod

Nodurile pot fi accesate secvential plecand de la nodul de pointer ptr_nod:

p=ptr_nod;

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

do

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

while (p! = ptr_nod);

sau cautand un nod de cheie data key; in acest caz o functie care va returna pointerul la nodul gasit va contine urmatoarea secventa de program:

p = ptr_nod;

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

do

p = p -> urm;

while (p! = ptr_nod);

return 0;

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 (adresa sa va fi q):

TIP_NOD *p,*q,*q1;

q = ptr_nod;

do

while (q! = ptr_nod);

se insereaza nodul de adresa p;

if (q -> cheie == key)

b)     Inserarea dupa un nod de cheie data

se cauta nodul de cheie data:

TIP_NOD *p,*q;

q = ptr_nod;

do

while(q!=ptr_nod);

se insereaza nodul de adresa p :

if (q -> cheie == key)

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, cu mentiunea ca daca  se sterge nodul de pointer ptr_nod, atunci ptr_nod va pointa spre nodul precedent q1:

if (q-> cheie == key)

elib_nod(q);

Stergerea listei

Stergerea listei circulare simplu inlantuite se va face astfel:

p = ptr_nod;

do

while (p! = ptr_nod);

ptr_nod = 0;

Mersul lucrarii

Sa se defineasca si sa se implementeze functiile pentru structura de date:

struct LISTA_CIRC

avand modelul din fig. 3.1.

De la tastatura se citeste numarul n si numele a n copii. Sa se simuleze urmatorul joc: cei n copii stau intr-un cerc. Incepand cu un anumit copil, se numara copiii in sensul acelor de ceasornic. Fiecare al n-lea copil iese din cerc .Castiga ultimul copil ramas in joc.

Sa se implementeze un buffer circular, care contine inregistrari cu datele unui student si asupra caruia actioneaza principiul de sincronizare producator-consumator, care consta in urmatoarele:

a)     inregistrarile sunt preluate in ordinea producerii lor;

b)     daca bufferul nu contine inregistrari, consumatorul este intarziat pana cand producatorul depune o inregistrare;

c)      daca bufferul este plin, producatorul este intarziat pana cand consumatorul a preluat o inregistrare.