Metode evoluate de programare Limbajele c şi C++

6.8. Stiva

Prin stivă (stack în engleză) înţelegem o mulţime ordonată de elemente la care accesul se realizează conform principiului ultimul venit primul servit. În engleză stiva se mai numeşte şi listă LIFO (Last In First Out).

O modalitate simplă de a implementa o stivă este păstrarea elementelor ei într-un tablou unidimensional. În acest tablou se vor păstra elementele stivei unul după altul. De asemenea, ele se pot scoate din tablou în ordinea inversă păstrării lor. La un moment dat se poate scoate ultimul element pus pe stivă şi numai acesta.

Despre ultimul element pus în stivă se spune că este vârful stivei, iar despre primul element că este baza stivei.

Accesul este permis doar la vârful stivei:

1. 
   un element se poate pune pe stivă numai după elementul aflat în vârful stivei şi după această operaţie el ajunge vârful stivei;
   
2. 
   se poate scoate de pe stivă numai elementul aflat în vârful stivei şi după această operaţie în vârful stivei rămâne elementul care a fost pus pe stivă înaintea lui.
   

Vom numi stack tablou de tip int afectat stivei şi next variabila care indică prima poziţie liberă din stivă. Deci stack[0] este baza stivei iar stack[n] va fi vârful stivei. Vom defini mai multe funcţii asociate tabloului stack:
- push funcţia care pune un element în stivă;

- pop funcţia care scoate un element din stivă;

- clear funcţia de iniţializare a stivei; după apelul ei stiva devine vidă;

#define MAX 1000

static int stack[1000];

static next = 0; // indicele pentru baza stivei

void push(int x) // pune pe stiva valoarea lui x

{ if (next < MAX)

stack [next++]=x;

else

printf (“stiva este depasita\n”);

}

int pop() // scoate elementul din varful stivei si returneaza valoarea lui

{ if (next >0)

return stack [--next];

else { printf (“stiva este vida\n”);

return 0;

}

}
void clear(void) // videaza stiva

{ next=0;

}

7. Recursivitate

Spunem că o funcţie C este recursivă dacă ea se autoapelează înainte de a se reveni din ea. Funcţia se poate reapela fie direct, fie indirect (prin intermediul altor funcţii).

La fiecare apel al unei funcţii, parametrii şi variabilele locale se alocă pe stivă într-o zonă independentă. De asemenea, orice apel recursiv al unei funcţii va conduce la o revenire din funcţie la instrucţiunea următoare apelului respectiv. La revenirea dintr-o funcţie se realizează curăţarea stivei, adică zona de pe stivă afectată la apel parametrilor şi variabilelor automatice se eliberează.

Un exemplu simplu de funcţie apelata recursiv este funcţia de calcul al factorialului. Putem defini recursiv funcţia factorial astfel:

factorial(n)= 1, dacă n=0

factorial(n)=n*factorial(n-1), dacă n>0

În limbajul C avem :
double factorial (int)

{ if (n= = 0) return 1.0;

else return n*factorial(n-1);

}
Observaţii:

1^o. În general, o funcţie recursivă se poate realiza şi nerecursiv, adică fără să se autoapeleze.

2^o. De obicei, recursivitatea nu conduce nici la economie de memorie şi nici la execuţia mai rapidă a programelor. Ea permite însă o descriere mai compactă şi mai clară a funcţiilor. Acest lucru rezultă şi din exemplul de mai sus de calcul al factorialului.

3^o. În general, funcţiile recursive sunt de preferat pentru procese care se definesc recursiv. Există şi excepţii. De exemplu algoritmul de generare a permutărilor de n obiecte poate fi descris recursiv astfel: având în memorie toate cele (n-1)! permutări, atunci permutările de n obiecte se generează înserând pe n în toate poziţiile posibile ale fiecărei permutări de n-1 obiecte. Dar ne aducem aminte că 10!=3628800 şi capacitatea stivei se depăşeşte repede.
Exemple:

1. 
   Programul determină recursiv cmmdc (algoritmul lui Euclid) a două numere întregi (de tip long):
   

cmmdc (a,b) = b, dacă a%b =0 (restul împărţirii lui a la b e zero)

cmmdc (a,b) = cmmdc (b,a%b), în caz contrar.

#include

#include

long cmmdc(long a, long b)

{ if (!(a % b)) return b;

else return cmmdc(b, a % b);

}
void main(void)

{ long x,y;

clrscr();

cout << "dati un numar natural=";

cin >> x;

cout << "dati alt numar natural=";

cin >> y;

cout << "cmmdc(" << x << "," << y << ")=" << cmmdc (x,y);

}
Am folosit funcţiile de intrare / ieşire cin şi cout, imediat se observă modul lor de utilizare.

1. 
   Programul determină recursiv suma unor elemente de tablou unidimensional
   

a[1]+a[2]+ . . . + a[n]

#include

#define MAX 100

int a[MAX];

// suma(n)= 0, daca n=0

// suma(n)=suma(n-1) + a[n] daca n>0

int suma(int n)

{ if (!n) return 0;

else return a[n]+suma(n-1);

}
void main(void)

{int n,i;

cout << "dati n= ";

cin >> n;

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

{ cout << "a[" << i << "]= ";

cin >> a[i];

}

cout << "suma numerelor este " << suma(n);

}

1. 
   Programul determină recursiv termenul al n-lea din şirul lui Fibonacci definit după cum urmează:
   

fibonacci[0]=0

fibonacci[1]=1

fibonacci[n]=fibonacci[n-1]+fibonacci[n-2], dacă n>1

#include
long fibonacci (long n)

{if (!n) return 0;

else if (n==1) return 1;

else return fibonacci(n-1) + fibonacci(n-2);

}
void main (void)

{ long n;

cout << "dati n = ";

cin >> n;

cout << "fibo(" << n << ") =" << fibonacci (n);

}

1. 
   Programul determina maximul dintr-un vector de numere astfel:
   

M(n)= a[1], dacă n=1

M(n)= max { M(n-1), a[n] }, dacă n>1
#include

#define MAX(x,y) (x > y ? x : y)

int a[100];
int M(int n)

{ if (n= =1) return a[1];

else return MAX (M(n-1), a[n]);

}
void main(void)

{int n,i;

cout << "dati n=";

cin >> n;

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

{ cout << "a[" << i << "]= ";

cin >> a[i];

}

cout << "maximul este " << M(n);

}
5) Programul afisează un şir de caractere în mod recursiv, caracter cu caracter, considerând că şirul de caractere este format din primul caracter(capul) + restul şirului de caractere (coada).
#include

#include

#define max 100

char sir [max];

int n;
void afis (int m)

{ if (m = = n+1) return;

else { cout << sir[m];

afis(m+1);

}

}
void main (void)

{int i;

do { cout << "\ndati lungimea sirului =";

cin >> n;

}

while ( (n< 0) || (n > max));

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

{ cout << "sir[" << i << "]=";

cin >> sir[i];

}

afis(1);

getch();

}
6) Programul ce urmează e oarecum asemănător cu exemplul anterior doar că afişează şirul de caractere de la sfârşit spre început.

#include

#include

#define max 100

char sir [max];

void afis (int m)

{ if (m==0) return;

else { cout << sir[m];

afis(m-1);

}

}
void main (void)

{int n,i;

do {cout << "\ndati lungimea sirului ="), cin >> n;}

while ( (n< 0) || (n > max));

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

{ cout << "sir[" << i << "]=";

cin >> sir[i];

}

afis(n);

getch();

}
7) Programul sortează prin metoda quicksort un vector de numere întregi:

#define dim 50

#include

#include

int x[dim+1],i,n;

void tipsir ()

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

{ printf("%3d",x[i]);

if (!(i % 20)) printf ("\n");

}

}
void quik(int st, int dr)

{int i,j,y;

i=st; j=dr; y=x[i];

do { while ((x[j] >= y) && (i

x[i]=x[j];

while ((x[i] <= y) && (i

x[j]=x[i];

}

while (i != j);

x[i]=y;

if (st < i-1) quik(st,i-1);

if (i+1 < dr) quik(i+1,dr);

x[j]=x[i];

}

void citire (void)

{ int cod = 0;

n = dim+1;

while ( n <= 0 || n > dim || ! cod )

{ printf ("\ndati dim. sir:");

cod=scanf ("%d",&n);

}

i = 1;

while (i<=n)

{ printf ("x[%2d]=",i);

scanf ("%d", &x[i]);

i++;

}

}
void main(void)

{ clrscr();

citire();

clrscr();

printf ("\n\nsir initial\n");

tipsir();

quik(1,n);

printf ("\n\nsir sortat\n");

tipsir();

getche();

}