|
|
|
ALGORITMI PENTRU PRELUCRAREA COZILOR
Extremitatile: cap si baza;
Accesul (adaugarea, extragerea si consultarea) - de tip FIFO:
- adaugarea: prin nodul baza;
- extragerea si consultarea: numai prin cap:
Implementarea stivelor implementarea listelor liniare, dar:
- primul nod al cozii va fi indicat de pointerul cap catre tipul nod;
- ultimul nod al cozii va fi indicat de pointerul baza catre tipul nod;
- adaugarea unui nod folosind algoritmul de adaugare dupa ultimul nod (III. 2);
- extragerea unui nod folosind algoritmul de eliminare a primului nod (VII. 1);
Observatie - prelucrarea unei cozi se face de la cap spre baza;
- se prelucreaza totdeauna nodul din capul cozii.
- accesul la informatie se face cu cap→info.
Coada vida - nu contine nici un nod;
- adresa nodului cap este NULL (cap=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 *cap)
Prelucrari:
- initializarea cozii;
- adaugarea unui nod in coada;
- extragerea unui nod din coada;
- consultarea nodului din capul cozii.
1. Initializarea cozii
Se creeaza coada care contine un singur nod. Nodurile cap si baza vor avea aceeasi adresa.
Se foloseste functia procedurala init(), ai carei parametri cap si baza se transmite prin referinta (sunt parametri de iesire).
void init (nod *&cap, nod *&baza)
2. Adaugarea unui nod in coada
Nodul se adauga la coada ca succesor al nodului baza.
Algoritmul este:
P1. Se cere alocarea de memorie pentru nodul p.
P2. Se scrie informatia in nodul p.
P3. Nodul p se leaga de nodul baza.
P4. Nodul p adaugat devine nod baza.
Se foloseste functia procedurala adauga(), al carei parametru baza, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void adauga (nod *&baza)
3. Prelucrarea cozii
Se consulta informatia din fiecare nod al cozii.
Deoarece nu se poate consulta decat informatia din capul cozii, pentru a ajunge la un nod trebuie extrase toate nodurile de pana la el.
Se foloseste functia procedurala prelucrare(), al carei parametru cap, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void prelucrare (nod *&cap)
