| CATEGORII DOCUMENTE |
Liste circulare. Stive. Cozi
Lista circulara este o lista (simplu sau dublu) inlantuita cu proprietatea ca toate nodurile sunt echivalente, respectiv, nu exista noduri speciale care nu contin adresa nodurilor succesoare sau predecesoare. Aceste noduri speciale - denumite capetele listei au fost utilizate in gestionarea listelor simplu si dublu inlantuite. O lista circulara va fi gestionata prin alte mecanisme decat cele bazate pe mentinerea adreselor speciale prim si ultim.
LISTA SIMPLU INLANTUITA CIRCULARA
Intr-o lista circulara simplu inlantuita toate nodurile contin adresa urmatorului nod. Structura nodului este similara celei prezentate la capitolul dedicat listelor simplu inlantuite:
typedef struct nod
Tnod;
Organizarea unei liste circulare cu noduri de acest tip este sugerata de figura alaturata.
Orice lista simplu inlantuita gestionata prin pointer-ii prim si ultim se poate transforma in lista circulara printr-o operatie elementara de asignare:
ultim->urm=prim
Prin operatia anterioara s-a stabilit faptul ca ultimul nod al listei initiale va contine adresa primului nod al listei, ceea ce conduce la o structura de lista circulara a carei gestionare poate fi efectuata prin adresa pointer-ului prim, insa fara ca acesta sa semnifice adresa unui capat al listei, ci doar adresa unui nod oarecare.
Spre deosebire de listele simplu inlantuite la care este suficienta cunoasterea adresei primului nod si, eventual, pentru simplificarea prelucrarilor, si a adresei ultimului nod, intr-o lista circulara, cunoasterea adresei oricarui nod din compunerea listei este suficienta pentru a putea gestiona aceasta structura. Astfel, gestionarea unei liste circulare se face prin unui pointer care refera oricare nod al listei:
Tnod *pLC; //pointer la lista circulara
Operatiile posibile cu listele circulare sunt aceleasi ca cele specifice listelor simplu inlantuite:
parcurgere
creare
distrugere (stergere)
adaugare nou element
stergere element
Crearea listei circulare simplu inlantuite
Crearea listei vide se realizeaza prin initializarea pointer-ului pLC cu valoarea Null:
pLC=0;
Crearea unei liste circulare care contine cel putin un element presupune o operatie repetitiva de adaugare a unui nou nod. Pentru nodul care se adauga se va aloca memorie in prealabil si se acesta va incarca cu informatii. Functia incarca_nod prezentata in capitolele precedente poate fi utilizata in acest sens.
Adaugarea nodului nou se poate efectua in doua maniere:
adaugarea inaintea nodului referit de pLC
adaugarea dupa nodul referit de pLC
Adaugarea unui nou nod inaintea nodului pLC necesita un efort computational suplimentar prin parcurgerea listei circulare. Aceasta parcurgere este necesara pentru a determina adresa nodului precedent al nodului pLC in vederea refacerii legaturilor si asigurarii consistentei listei.
Acest aspect a fost evidentiat in cazul listelor simplu inlantuite, pentru care operatiile de inserare inaintea unui nod oarecare, respectiv, inserare dupa un nod oarecare difera semnificativ prin necesitatea parcurgerii complete a listei in primul caz.
Functia urmatoare adauga noi noduri la lista circulara gestionata prin pLC in varianta 2.
void creare_LCSI()
else
printf('nIntroduceti? (1/0)');scanf('%d',&rasp);
Parcurgerea listei circulare simplu inlantuite
Parcurgerea listei circulare se va face prin urmarirea legaturilor (adreselor) continute de noduri, in aceiasi maniera ca la listele simplu inlantuite, printr-un pointer auxiliar. Specificul listelor circulare implica o alta conditie de oprire a traversarii listelor. Daca pentru listele gestionate prin prim si ultim aceasta conditie era evidenta (pointer-ul auxiliar prin care se parcurge lista a ajuns la ultim), in cazul listelor circulare conditia se refera la revenirea in punctul de plecare. Initial, pointer-ul contine adresa cunoscuta a unui nod oarecare: pLC. Nodurile urmatoare se parcurg cat timp pointer-ul auxiliar nu va avea aceiasi adresa de inceput: pLC (nu a revenit la pozitia initiala):
p=pLC;
do
while (p!=pLC);
Functia urmatoare afiseaza cheile nodurilor unei liste circulare:
void Tiparire()
while (p!=pLC);
Operatia de cautare a unui nod specificat prin valoarea cheii presupune parcurgerea listei circulare si verificarea daca nodurile contin pentru campul cheie valoarea data. Functia prin care se realizeaza aceasta operatie va returna adresa nodului gasit sau 0 in caz de insucces:
tnod* cauta(int valoare)
while (p!=pLC);
return 0; //s-a incheiat cautarea si nodul nu s-a gasit
Inserarea nodurilor intr-o lista circulara simplu inlantuita
Inserarea inaintea unui nod specificat prin valoarea cheii
Inserarea dupa un nod specificat prin valoarea cheii
1. Inserarea unui nou nod inaintea unui nod specificat prin valoarea cheii presupune parcurgerea urmatoarelor etape:
cautarea nodului de cheie data
inserarea propriu-zisa daca etapa anterioara s-a incheiat cu succes
Observatie: In etapa de cautare a nodului de cheie data se va retine adresa nodului precedent a nodului curent, pentru a face posibila refacerea legaturilor in faza de inserare. In caz contrar ar fi necesara o reparcurgere a listei circulare pentru a determina precedentul nodului inaintea caruia va fi inserat noul nod.
Cunoscand adresa nodului de cheie data si adresa precedentului sau, inserarea propriu-zisa a unui nou nod se reduce la: alocarea memoriei, incarcarea nodului nou cu informatie si refacerea legaturilor intr-o maniera similara celei prezentate in operatia omonima pentru liste simplu inlantuite:
void inserareInainte(int valoare)
while(p!=pLC);
if (p->cheie!=valoare) //cautarea s-a incheiat cu Insucces
return;
if (p->cheie==valoare) //cautarea s-a incheiat cu Succes
Observatii
- nodul referit de pLC este ultimul nod verificat in etapa de cautare
instructiunea decizionala if (p->cheie==valoare) . este redundanta, dat fiind faptul ca o conditie precedenta verificat situatia opusa si provoaca revenirea din functie. Din motive de lizibilitate si nu de optimizare a codului am convenit sa furnizam o varianta explicita a functiei pentru o urmarire usoara a etapelor descrise.
2. Inserarea unui nod nou dupa un nod precizat de cheie presupune:
- cautarea nodului de cheie data
- inserarea propriu-zisa
Daca prima etapa s-a incheiat cu succes, se cunoaste adresa nodului de cheie data p, dar si adresa urmatorului nod (datorita legaturii urm) p->urm. Nodul nou va fi inserat intre cele doua noduri de adrese cunoscute. Nu mai este necesara determinare altei adrese decat cea a nodului cautat dupa valoarea cheii.
Functia urmatoare este o posibila implementare a operatiei discutate:
void inserareDupa(int valoare)
while(p!=pLC);
if (p->cheie!=valoare) //cautarea s-a incheiat cu Insucces
return;
//daca s-a ajuns in acest punct, cautarea s-a incheiat cu //Succes
//etapa de inserare
nou=incarca_nod(); //alocare memorie si incarcare nou
nou->urm=p->urm;
p->urm=nou;
Observatie: nodul referit de pLC este primul nod verificat in etapa de cautare.
Stergerea unui nod precizat de valoarea cheii
Operatia de stergere a nodului precizat printr-o cheie presupune:
cautarea nodului si retinerea adresei precedentului sau ()
stergerea nodului: refacerea legaturilor si eliberarea memoriei
Cazurile particulare ale operatiei se trateaza diferit:
a. lista este vida inainte stergerii
b. lista devine vida dupa stergere
c. nodul de sters este chiar pLC
Convenim ca in cazul particular c. (nodul ce se va sterge este chiar nodul referit de pointer-ul pLC si lista nu devine vida), pLC va referi nodul precedent celui sters.
O functie C care descrie operatia de stergere este urmatoarea:
void steregereNod(int valoare)
while(p!=pLC);
if (p->cheie!=valoare) return; //nu s-a gasit nodul
//nodul gasit este referit de p, urmeaza etapa de stergere
if (p->urm==p) //lista are un singur nod - nodul care se va sterge (b.)
else
else //cazul general
//sfarsit functie steregereNod
Observatie: in situatia in care informatia din noduri contine adrese alocate dinamic (prin apelul functiei malloc), eliberarea memoriei alocate unui nod p trebuie sa tina cont si de acest aspect, fapt pentru care, apelul functiei free(p) nu este suficient. Din aceste considerente, o functie speciala de eliberare a memoriei alocate unui nod poate fi conceputa. Spre exemplu:
typedef struct nod
Persoana;
Alocarea memoriei pentru un nod de tipul Persoana (Persoana *p) necesita un apel malloc pentru campul nume. Eliberarea memoriei alocate nodului p se va executa corect prin functia urmatoare:
void eliberare_nod(Persoana *p)
Stergerea liste circulare simplu inlantuite
Operatia de distrugere a unei liste circulare se realizeaza prin stergerea tuturor nodurilor sale si nu prin distrugerea adresei speciale pLC prin care se gestioneaza lista.
Daca nu este deja vida, lista se parcurge si noduri precedente nodului curent se sterg pana cand lista devine vida. O functie de stergere a listei circulare gestionate prin pLC este urmatoarea:
void stergere()
while(p!=pLC)
pLC=0; //marcare lista vida
Observatie: primul nod eliberat este cel referit de pLC, fapt pentru care cand conditia p==pLC devine adevarata se indica revenirea in punctul de plecare a pointer-ului p ceea ce semnifica faptul ca toate nodurile au fost sterse (inclusiv nodul referit de pointer-ul special pLC) si lista este vida.
LISTA DUBLU INLANTUITA CIRCULARA
Lista circulara dublu inlantuita este gestionata printr-un pointer la un nod oarecare. Structura nodului este cea prezentata la listele dublu inlantuite si contine: zona de informatii, adresa precedentului si adresa nodului urmator.
Operatiile specifice: creare, inserare nod, stergere nod, stergere lista, parcurgere, cautare, sunt similare operatiilor descrise cu liste circulare simplu inlantuite. Diferentele semnificative apar la procedurile de inserare inaintea unui nod precizat si stergerea unui nod oarecare, care se simplifica prin existenta unei legaturi spre nodurile precedente.
Transformarea unei liste dublu inlantuite in lista circulara se realizeaza prin legarea capetelor prim si ultim, in ambele sensuri:
ultim->urm=prim;
prim->prec=ultim;
STIVE. COZI.
Stiva reprezinta un caz special de lista liniara in care intrarile si iesirile se fac la un singur capat al ei. Organizarea structurilor de date de tip stiva se poate face in doua maniere:
secvential - elementele stivei sunt memorate la adrese consecutive
inlantuit - elementele stivei nu ocupa adrese consecutive, fiecare element contine o legatura spre urmatorul element.
Prin organizarea secventiala nu se poate face economie de memorie, fapt pentru care in general se practica organizarea inlantuita cu alocare dinamica a stivelor.
Structura de stiva se remarca prin operatiile specifice: push si pop, corespunzatoare adaugarii unui element, respectiv, stergerii unui element in/din varful stivei. Principiul de functionare al stivei este cel cunoscut sub denumirea de LIFO (Last In First Out - ultimul intrat, primul iesit).
|
I Structura de date STIVA cu alocare statica |
II. Structura de date STIVA cu alocare dinamica |
Practic, stiva este o lista simplu inlantuita pentru care operatiile specifice se limiteaza la urmatoarele:
creare stiva vida
adaugare element (push)
stergere element (pop)
sterge lista (clear)
accesare - fara eliminare - a elementului din varful stivei
In plus fata de operatiile enumerate anterior sunt posibile implementate operatii de verificare:
verifica daca stiva este plina
verifica daca stiva este goala
Gestionarea stivei se face in mod similar listei inlantuite prin capetele prim si ultim. La nivel abstract, o stiva are o baza a sa si un varf, ceea ce convine unei asocieri a nodurilor referite de prim si ultimi cu cele doua elemente specifice:
baza stivei corespunde nodului prim si varful stivei corespunde nodului ultim
In aceasta abordare, operatiile push si pop se traduc prin operatiile de:
adaugare a unui nou nod dupa ultim (adaugare in varful stivei)
stergere ultim (stergere din varful stivei)
Privitor la eficienta operatiilor descrise intr-un capitol anterior, ne reamintim ca operatia de adaugare a unui nou element dupa cel referit de pointer-ul ultim necesita o parcurgere prealabila a listei. In schimb, adaugarea unui nou nod inaintea celui referit de prim este mai putin costisitoare. Din aceste considerente, se practica o inversare a rolurilor celor doua capete ale stivei, pentru a obtine operatii mai eficiente:
baza stivei corespunde nodului ultim si varful stivei corespunde nodului prim
Astfel, operatiile push si pop se vor traduce prin:
adaugare a unui nou nod inainte de prim (adaugare in varful stivei)
stergere prim (stergere din varful stivei)
Coada este un alt caz special de lista inlantuita bazat pe principiul FIFO (First In First Out - primul intrat, primul iesit). Acest principiu arata ca primul element introdus in lista este si primul care va fi sters. O structura de acest gen are doua capete, denumite sugestiv: cap si coada.
Operatiile primare cu cozi sunt:
creare stiva vida
adaugare element in coada
stergere element din cap
sterge lista (clear)
Spre deosebire de stiva, adaugarea si stergerea unui element se executa in capetele diferite ale cozii.
Ca si in cazul stivelor, organizarea unei cozi poate fi facuta in mod secvential (static) - prin intermediul tablourilor unidimensionale sau dinamic - prin liste simplu inlantuite. Cea de-a doua varianta este de preferat din ratiuni economice.
Coada este astfel o lista inlantuita ale carei capete referite prin prim si ultim semnifica capul si coada structurii, ceea ce permite organizarea in doua maniere:
prim refera capul listei si ultim refera coada listei
ultim refera capul listei si prim refera coada listei
Conform celor doua abordari enumerate anterior, operatiile de adaugare si scoatere elemente in/din lista FIFO se traduc prin:
adaugare dupa nodul ultim si stergere nod prim
adaugare inainte de prim si stergere nod ultim
Constatam ca spre deosebire de stive, ambele abordari sunt eficiente, astfel incat alegerea oricarei variante este posibila. Printr-o conventie, adaugarea unui nod se face dupa ultimul nod (coada) al listei, iar scoaterea din lista a unui nod este implementata prin stergerea nodului prim (cap).
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2125
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
