luni, 28 aprilie 2014
vineri, 25 aprilie 2014
Cazuri particulare de liste
Stiva este o listă liniară care funcţionează după principiul ultimul
intrat este primul ieşit(LIFO).
Operaţiile ce se pot efectua asupra unei stive sunt:
-adăugarea unui element în vârful stivei
-extragerea unui element din stivă
Operaţiile ce se efectuează asupra unei stive se realizează
numai la vârful stivei, prin urmare este suficient să memorăm indicele nodului din vârful stivei într-o variabilă vf. Dacă vf este-1,atunci vom spune că stiva este vidă.
Coada este o listă liniară ce funcţionează după principiul primul intrat este primul ieşit(FIFO).
Operaţiile ce se pot efectua asupra unei cozi sunt:
-adăugarea unui element la sfârşitul cozii
-extragerea unui element din coadă
Pentru gestionarea unei liste liniare de tip coadă avem nevoie de două variabile:prim şi ultim
. Dacă prim>ultim atunci coada este vidă.
Implementarea listelor liniare
Considerăm informaţia utilă din cadrul unui nod ca fiind un număr întreg.
struct nod
{ int inf;
int urm;
};
Vom memora nodurile listei în tabloul unidimensional numit lista.
Vectorul caracteristic pentru gestionarea spaţiului liber îl numim s.
Pentru a memora indicele primului nod al listei vom utiliza variabila prim.
Dacă lista este vidă (nu conţine nici un nod), variabila prim este-1
Liste liniare
O listă colecţie de elemente de acelaşi tip aflate într-o relaţie de ordine: x1,x2, ... xn.
Caracteristica principală a listelor liniare în opoziţie cu
tablourile unidimensionale, este aceea că numărul de elemente nu este cunoscut de la început.Deşi există posibilitatea implementării listelor cu ajutorul tablourilor unidimensionale, se utilizează mai puţin acest mod de reprezentare. În practică, listele se implementează utilizând alocarea dinamică a memoriei.
Operaţiile specifice prelucrării listelor:
-adăugarea unui element la sfârşitul listei
-inserarea unui element în listă
-accesul la un element al listei
-ştergerea unui element din listă
Pentru lista liniară vom reprezenta înlănţuirea elementelor listei memorate într-un tablou unidimensional cu reutilizarea spaţiului eliberat în urma operaţiilor de ştergere. În cadrul fiecăruielement al listei vom memora două categorii de informaţii: informaţia utilă pe care o conţine
elementul listei şi indicele de tablou corespunzător elementului următor din listă. Un element allistei astfel organizatse numeştenod.
În cadrul ultimului nod al listei, indicele care desemnează elementul următor are valoarea-1,marcând astfel sfârşitul listei. Pentru gestionarea unei astfel de liste este necesar sămemorămindicele primului nod din listă.Deoarece una dintre operaţiile posibile asupra unei liste liniare este ştergerea unui nod, pot rămâne zone de memorie neutilizate ale tablourilor. Astfel se impune gestionarea spaţiului liber al tabloului în scopul reutilizării lui.
Abonați-vă la:
Postări (Atom)