stiva

stiva

Stiva este o structură de date în care pot fi adăugate sau şterse elemente doar în vârf.

Elementele vor fi de tip structură, cu informaţia utilă (conţinutul efectiv al elementului - inf) și informaţia de legătură (un pointer ce conţine adresa elementului precedent din stivă – leg).

Este necesar şi suficient să fie reţinută adresa elementului din vârful stivei într- un pointer, vf (TNOD *vf), celelalte elemente putând fi accesate cu ajutorul informaţiei de legătură de care dispune fiecare element al stivei.

Elementul introdus primul în stivă se afla la bazastivei și are informația de legătură NULL.

Inițializarea stivei presupune atribuirea valorii NULL variabilei vf.

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

void init( TNOD* vf) { vf=NULL; }

ADĂUGAREA UNUI ELEMENT ÎN STIVĂ

Se alocă memorie pentru noul element.

Se iniţializează zona de informaţie propriu-zisă (utilă) a noului nod.

Putem observa că acest algoritm este corect şi dacă stiva era vidă înainte de adăugare(vf=NULL).

Se iniţializează informaţia de legătură cu adresa elementului care a fost anterior în vârful stivei, adresă păstrată în variabila vf.

Se actualizează variabila vf cu adresa noului element alocat.

p=new TNOD

p->inf=x

p->leg=vf

vf=p

void adaug(tip x,TNOD *&vf) { TNOD *p; p=new TNOD; p->inf=x; p->leg=vf; vf=p; }

ȘTERGEREA UNUI ELEMENT DIN STIVĂ

Această operaţie se poate realiza numai dacă stiva este nevidă şi în caz afirmativ se va şterge elementul din vârful stivei.

Într-un pointer de lucru notat p, se reţine adresa elementului din vârful stivei.

Verificarea dacă stiva este vidă.

Adresa elementului următor celui din vârful stivei devine adresa noului vârf al stivei.

Se eliberează memoria ocupată de elementul care a fost anterior în vârful stivei.

p=vf

int stvida( TNOD *vf) { return vf==NULL; }

vf=vf->leg

delete p

int stvida( TNOD *vf) { return vf==NULL; } void extragere( TNOD *&vf) { TNOD *p; if(!stvida(vf)) { p=vf; vf=vf->leg; delete p; } }

APLICAȚII

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

2. Creați o funcție care afișează conținutul unei stive.

5. Creați o funcție prin care se construiește o stivă 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 stivă.

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

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

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

void adaug(int x,TNOD *&vf) { TNOD *p; p=new TNOD; p->inf=x; p->leg=vf; vf=p; } void creare(TNOD *&vf) { int x; cout<<"dati informatia utila:"; cin>>x; while (x!=0) {adaug(x,vf); cout<<"dati informatia utila:"; cin>>x;}}

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

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