Structura de date de tip coada

 

Aceasta structura de date este un caz particular de lista care functioneaza pe principiul FIFO (first in first out, primul intrat este primul servit). Prin urmare principalele prelucrari care se refera la aceasta structura de date vor fi:

 

-         creare coada

-         listare coada (parcurgere)

-         adaugare la sfarsir

-         stergere prim element

-         prelucrare prim element

 

 

Specific acestei structuri de date este faptul ca adaugarea se va face intotdeauna la ultim in timp ce prelucrarea (stergerea) se va face la celalat capat. Pentru a prelucra o coada vor fi necesari doi pointeri: unul il vom numi varful cozii (primul nod creat) in timp ce la capatul opus ne vom referi la ultimul element.

 

Functia pune( ) , creaza coada cand aceasta este vida sau adauga un nou element la sfarsit in caz contrar.

Functia scoate( ), elimina elementul din varful cozii.

 

Fie o coada care retine 4 numere intregi: 10,20,30,40

 

 

 


In urma adaugarii valorii 50 , prin apelul functiei pune( ) se va obtine:

 

Text Box: 50

 

 

 

 

 

 


In urma eliminarii primului element,10, retinut de varful cozii, prin apelul functiei scoate se va obtine:

 

 

 

 

 

 

 


In continuare se prezinta o solutie pentru implementarea functiilor anterioare. Coada prelucreaza numere intregi.

 

 

#include<iostream.h>

#include<conio.h>

 

struct nod{int info;

nod *next;};

 

 

void pune(nod* &v,nod* &sf,int x)

{nod *c;

if(!v)

{v=new nod;

v->info=x;

v->next=0;

sf=v;}

else

{c=new nod;

sf->next=c;

c->info=x;

sf=c;

sf->next=0;}

}

 

void afisare(nod *v)

{nod *c;

c=v;

while(c)

{cout<<c->info<<" ";

c=c->next;}

}

 

void scoate(nod* &v)

{nod* c;

if(!v)

cout<<"coada este vida si nu mai ai ce elimina!!!";

else

{c=v;

v=v->next;

delete c;}

}

 

 

void main()

{int n,a;

nod *varf=0,*ultim=0;//varful si ultimul element al cozii

 

cout<<"numarul initial de noduri ";

cin>>n;

for(int i=1;i<=n;i++)

{cout<<"valoarea de adaugat in coada ";

cin>>a;

pune(varf,ultim,a);

}

cout<<endl;

afisare(varf);

int nre,nra;

cout<<endl<<"cate adaugari ?";

cin>>nra;

for(i=1;i<=nra;i++)

{cout<<"valoarea de adaugat ";

cin>>a;

pune(varf,ultim,a);}

cout<<endl<<"dupa adaugare"<<endl;

n=n+nra;

cout<<"coada are "<<n<<" elemente"<<endl;

afisare(varf);

cout<<endl<<"cate eliminari ?";

cin>>nre;

for(i=1;i<=nre;i++)

scoate(varf);

cout<<endl<<"dupa eliminare"<<endl;

n=n-nre;

cout<<"coada are "<<n<<" elemente"<<endl;

afisare(varf);

//prelucrez varful cozii: de exemplu se poate dubla continutul:

varf->info=2*varf->info;

cout<<endl<<"dupa dublarea valorii varfului "<<endl;

afisare(varf);

getch();

}

 

Se observa ca in main se realizeaza prelucrarea (modificarea) informatiei primului nod.

 

Exercitiu propus:

1) Sa se prelucreze datele celor n angajati ai unei firme (nume, profesia, salariu). Datele se citesc din fisier si sunt inregistrate in ordinea angajarii (pentru fiecare persoana datele sunt scrise pe o linie).

a)      Sa se afiseze datele dupa ce acestea au fost memorate intr-o structura de tip date.

b)      Cel mai vechi angajat se pensioneaza. Sa se afiseze si sa modifice datele din structura si apoi din fisier

c)      Cel mai vechi angajat primeste o prima de 2000 000 de lei. . Sa se afiseze si sa modifice datele din structura si apoi din fisier

2) Sa se memoreze n numere intrefi intr-o structura de tip coada . Sa se stearga elementele neprime din varful cozii pana se intalneste un numar prim.

 

3) La o intrare intr-o sala de spectacole sunt 2 randuri de persoane pastrate in doua structuri de tip coada. Pentru ca exista doar un singur angajat care verifica biletele, pe poarta poate sa intre la un moment dat o singura persoana. Stiind ca angajatul este corect si permite sa intre alternativ cate o persoana din fiecare rand, se cere sa se afiseze ordinea de intrare a persoanelor in sala de spectacol.

 

4) La un cabinet stomatologic sunt asezate n persoane la rand dintre care m urgente. Asistenta duce lista pacientilor medicului de serviciu astfel incat acesta va trebui sa rezolve mai intai urgentele.