Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


LISTE CIRCULARE. STIVE. COZI

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
FUNCTII SI STRUCTURA PROGRAMULUI
Operatii cu liste
Cuvinte distincte din text si nr.lor de aparitii
OPERATORI DE PRELUCRARE LA NIVEL DE BIT
Declaratii
Controlling the Supports: ArtSupportCall, ArtSupportChangeState
Siruri de caractere
Programare orientata pe obiect
Tablouri de pointeri, pointeri pe pointeri
Algoritmi Recursivi

TERMENI importanti pentru acest document

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



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1557
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2022 . All rights reserved

Distribuie URL

Adauga cod HTML in site