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: 

 

 

 

 

 

 

 

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.