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.
|
