COADA

COADA

Coada este o structură de date în care operaţia de inserare a unui element se realizează la un capăt, în timp ce operaţia de extragere a unui element se realizează la celălalt capăt. Singurul element din coadă la care avem acces direct este cel de la început.

În cazul implementării dinamice, un element al cozii conţine două tipuri de informaţii: informaţia utilă (inf) şi informaţia de legătură (leg) - care este de fapt un pointer ce conţine adresa următorului element din coadă.

Inițializarea cozii presupune atribuirea valorii NULL variabilelor prim și ultim.

Sunt necesare două variabile de tip referinţă care să indice primul element din coadă (prim) şi ultimul element din coadă (ultim).

Ultimul element al cozii nu mai are succesor, deci informaţia sa de legătură are valoarea NULL.

typedef struct tnod { tip inf; struct tnod *leg; } TNOD;

void Coada_vida (TNOD *prim, TNOD *ultim) { prim=ultim=NULL; }

TNOD *prim,*ultim;

ADĂUGAREA UNUI ELEMENT ÎN COADĂ

În cazul când coada este vidă, atunci la inserarea unei valori se creează de fapt primul element al cozii. În acest caz, prim şi ultim indică acelaşi element (au aceeaşi valoare).

Dacă mai sunt elemente în coadă, se alocă memorie pentru noul element și se introduce informația utilă.

Se modifică valoarea pointerului ultim, dându-i ca valoare adresa noului element introdus.

Informaţia de legatură a elementului creat se completează cu NULL (adăugarea se face la sfârșitul cozii).

Se reiniţializează informaţia de legatură a elementului indicat de ultim cu adresa noului element.

p=new TNOD; p->inf=x;

ultim=p;

p->leg=NULL;

ultim->leg=p;

prim=ultim=new TNOD; prim->inf=x; prim->leg=NULL;

void adaug(tip x, TNOD *&prim, TNOD *&ultim) { TNOD *p; if (prim==NULL) { prim=ultim=new TNOD; prim->inf=x; prim->leg=NULL; } else { p=new TNOD; p->inf=x; p->leg=NULL; ultim->leg=p; ultim=p; } }

EXTRAGEREA UNUI ELEMENT DIN COADĂ

Operaţia de extragere se poate face doar asupra primului element din coadă. Bineînţeles, putem extrage un element numaidintr-o coadă care nu este vidă.

Se reţine într-un pointer de lucru adresa primului element (pointerul de lucru p).

Verificarea dacă este coadă vidă.

Se actualizează valoarea pointerului prim cu adresa următorului element din coadă.

Se eliberează zona de memorie ce fusese alocată iniţial primului element din coadă (acum indicat de pointerul p).

p=prim;

int cvida (TNOD *prim) { return (prim==NULL); }

prim=prim->leg;

delete p;

int cvida (TNOD *prim) { return (prim==NULL); } void extrag(TNOD *&prim) { TNOD *p; if(!cvida(prim)) { p=prim; prim=prim->leg; delete p; } }

APLICAȚII

1. Creați o funcție care afișează conținutul unei cozi.

2. Creați o funcție care numără câte elemente sunt într-o coadă.

5. Creați o funcție prin care se construiește o coadă cu numere introduse de la tastatură, până la introducerea numărului 0.

3. Creați o funcție care șterge toate elementele dintr-o coadă.

4. Creați o funcție care afișează valoarea maximă dintr-o coadă.

int afisare(TNOD *prim) { if(prim==NULL) cout<<"coada vida!"; else { p=prim; while (p!=NULL) { cout<<p->inf<<" ";p=p->leg; } cout<<endl;} return 0; }

int contor(TNOD *prim) { int m=0; TNOD* p; p=prim; while (p!=NULL) { m++; p=p->leg; } return m; }

void creare(TNOD *&prim, TNOD *&ultim) { cout<<"dati info utila:"; cin>>x; while (x!=0) {if (prim==NULL) { prim=ultim=new TNOD; prim->inf=x; prim->leg=NULL; } else { p=new TNOD; p->inf=x; p->leg=NULL; ultim->leg=p; ultim=p; } cout<<"dati info utila:"; cin>>x;}}

int sterge_coada(TNOD *&prim ) { TNOD* p =prim; while(p!=NULL) { p=prim->leg; delete(prim); prim=p; } return 0; }

int maxim(TNOD *prim) { int max=prim->inf; p=prim; while(p!=NULL) { if(p->inf>max) max=p->inf; p=p->leg; } return max; }