|
|
|
ALGORITMI PENTRU PRELUCRAREA STIVELOR
Extremitatile: varf si baza;
Accesul (adaugarea, extragerea si consultarea) - de tip LIFO - numai prin varf, de unde:
- la adaugarea unui nod varful stivei urca;
- la extragerea unui nod varful stivei coboara.
Implementarea stivelor implementarea listelor liniare, dar:
- varful stivei va fi indicat de pointerul varf catre tipul nod;
- adaugarea unui nod folosind algoritmul de adaugare in fata primului nod (IV. 1);
- extragerea unui nod folosind algoritmul de eliminare a primului nod (VII. 1);
Observatie - prelucrarea unei stive se face de la varf spre baza;
- se prelucreaza totdeauna nodul din varful stivei.
- accesul la informatie se face cu varf→info.
Stiva vida - nu contine nici un nod;
- adresa nodului varf este NULL (varf=NULL);
- se poate obtine: - la initializare;
- dupa extragerea ultimului nod.
Testarea unei stive „este vida, sau nu?” se face utilizand functia operand este_vida() care returneaza:
- 1, daca stiva este vida;
- 0, daca stiva nu este vida.
void este_vida (nod *varf)
Prelucrari:
- initializarea stivei;
- adaugarea unui nod in stiva;
- extragerea unui nod din stiva;
- consultarea nodului din varful stivei.
1. Initializarea stivei
Se creeaza stiva vida. Nodul varf nu exista si pointerul varf are valoarea NULL.
Se foloseste functia procedurala init(), al carei parametru varf se transmite prin referinta (este parametru de intrare-iesire).
void init (nod *&varf)
2. Extragerea unui nod din stiva
Dintr-o stiva se pot extrage noduri numai daca stiva nu este vida.
Nu se poate extrage decat nodul din varful stivei.
Dupa extragerea nodului: - succesorul nodului extras devine varful stivei;
- spatiul eliberat de nodul din varf se elibereaza.
Algoritmul este:
P1. Se salveaza adresa nodului varf in pointerul p.
P2. Succesorul nodului varf devine nodul varf.
P3. Se cere eliberarea zonei de memorie de la adresa memorata in pointerul p.
Se foloseste functia procedurala extrage(), al carei parametru varf, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void extrage (nod *&varf)
3. Prelucrarea stivei
Deoarece nu se pot extrage noduri decat nodul din varful stivei, pentru consultarea informatiei continuta intr-un nod ce nu se afla in varful acesteia, se vor extrage toate nodurile „de deasupra” nodului cautat. Acestea vor fi adaugate ulterior in stiva.
Se foloseste functia procedurala prelucrare(), al carei parametru varf, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void prelucrare (nod *&varf)
