LISTE CIRCULARE SIMPLU INLANTUITE

LISTE CIRCULARE SIMPLU ÎNLĂNŢUITE

Continutul lucrarii

În lucrare sunt prezentate principalele operatii asupra listelor circulare simplu înlantuite: crearea, inserarea unui nod, stergerea unui nod si stergerea listei.

Consideratii teoretice

Lista circulara simplu înl 858i84i 9;ntuita este lista simplu înlantuita a carei ultim element este legat de primul element; adica ultim -> urm = prim.

În cadrul listei circulare simplu înlantuite 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 înlantuita, 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 înlantuite

Initial lista este vida:

ptr_nod = 0;

Introducerea în lista a câte unui nod se va face astfel:

/* crearea nodului */

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

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

citire date în nod la adresa p;

if (ptr_nod = = 0)

else

Accesul la un nod

Nodurile pot fi accesate secvential plecând de la nodul de pointer ptr_nod:

p=ptr_nod;

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

do

while (p! = ptr_nod);

sau cautând un nod de cheie data key; în 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 înaintea unui nod de cheie data;

inserarea dupa un nod de cheie data.

În ambele cazuri se cauta nodul de cheie data având adresa q; daca exista un astfel de nod ,se creeaza nodul de inserat de adresa p si se fac legaturile corespunzatoare.

a)      Inserarea înaintea 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 înlantuite 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

având 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 într-un cerc. Începând cu un anumit copil, se numara copiii în sensul acelor de ceasornic. Fiecare al n-lea copil iese din cerc .Câstiga ultimul copil ramas în joc.

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

a)      înregistrarile sunt preluate în ordinea producerii lor;

b)      daca bufferul nu contine înregistrari, consumatorul este întârziat pâna când producatorul depune o înregistrare;

c)      daca bufferul este plin, producatorul este întârziat pâna când consumatorul a preluat o înregistrare.