ALGORITMI PENTRU PRELUCRAREA COZILOR

CONTINUT

NOTIUNI INTRODUCTIVE

METODE DE IMPLEMENTARE

DECLARAREA UNEI COZI

PRELUCRAREA COZII

- Testare

- Initializarea

- Adaugarea unui nod

- Eliminarea unui nod

NOTIUNI INTRODUCTIVE

Def: Coada reprezinta o lista restrictiva in care operatiile de introducere se fac pe la o extremitate iar extragerile pe la cealalta extremitate.

Cele doua extremitati se numesc varf (nodul prim) si baza (nodul ultim).

Este o structura de tip FIFO (First In First Out), astfel:

- adaugarea de noduri se realizeaza prin nodul ultim

- extragerea unui nod este permisa numai prin extremitatea prim.

METODE DE IMPLEMENTARE

Implementarea cozii se poate face:

- cu alocare inlantuita: la fel ca a unei liste liniare cu

deosebirea ca pentru adaugarea unui nod se poate

folosi numai algoritmul pentru adaugarea dupa ultimul

nod iar pentru extragere doar algoritmul pentru

eliminarea primului nod.

- cu alocare secventiala: este un mecanism mult mai

simplu de prelucrare.

In continuare se va utiliza alocarea secventiala pentru

implementarea cozii.

DECLARAREA UNEI COZIPentru implementare se vor folosi urmatoarele date si structuri de date:

const unsigned NMAX=100;

typedef <tip_data> nod;

nod coada[NMAX+1], val;

unsigned prim,ultim;

unde: tip_data – orice tip al limbajului

prim, ultim – cele doua extremitati

val – valoarea introdusa in nod

Prelucarea unei cozi se realizeaza de la nodul prim spre

nodul ultim.

Accesul la nodul prim se face cu coada[prim].

ExempluOperatii de adaugare si extragere intr-o coada:

a

a b

a b c

c

b c

a b c

Adaugare: Extragere

Obs: in urma operatiilor de adaugare si extragere vor rezulta spatii neocupate in coada => coada va ajunge la capatul spatiului alocatSolutia:implementare ca o lista circulara.

PRELUCRAREA COZIIPentru implementare se va folosi o variabila suplimentara k care va numara nodurile cozii.

1.Testarea cozii

a.coada vida:

int este_vida ()

{return k==0;}

unde este_vida e o functie cu valoarea 1 daca coada e vida si 0 in caz contrar.

b.coada plina:

int este_plina ()

{return k == NMAX;}

unde este_plina e o functie cu valoarea 1 daca coada e plina si 0 in caz contrar.

2.Initializarea cozii:

In aceasta secventa se creeaza coada vida:

void init (unsigned &prim, unsigned &ultim)

{prim=ultim = NULL;

k=0:}

PRELUCRAREA COZII3.Adaugarea unui nod:

void adaugare(unsigned &ultim, nod val)

{ if (! este_plina())

{ if (ultim == NMAX)

ultim = 1;

else ultim ++;

coada [ultim] = val;

k ++;}}

4.Eliminarea unui nod:

void eliminare( unsigned &prim)

{ if(! este_vida())

{ val = coada [prim];

if (prim==NMAX) prim=1;

else prim++;

k--;}

sfarsit!!!