Capitolul 8

§4. Stiva alocată static

Stiva aeste acea formă de organizare a datelor cu proprietatea că operaţiile de introducere şi scoatere a datelor se fac în vîrful ei.

Pentru a înţelege modul de lucru cu stiva, ne imaginăm un umăr n de farfurii identice, aşezate una peste alta (o “stivă” de farfurii). Adăugarea unei farfurii se face, cu uşurinţă, numai în vîrful stivei. Dacă toate cele n farfurii sunt aşezate una peste alta, spunem că stiva este plină. După ce am scos toate farfuriile din stivă, spunem că aceasta este vidă.

Stivele se pot simula utilizînd vectori.

Observaţii:

• 
  în mod practic, la scoaterea unei variabile din stivă, scade cu 1 valoarea variabilei ce indică vîrful stivei, iar atunci cînd scriem ceva în stivă, o eventuală valoare reziduală se pierde;
  
• 
  pe un anumit nuvel se reţine, de regulă, o singură informaţie, însă este posibil să avem mai multe informaţii;
  
• 
  teoria recursivităţii se bazează pe structura de tip stivă şi anume - stiva internă.
  

Principalul dezavantaj al unei astfel de implementări este dat de faptul că, deşi ca structură de date nu are limitat numărul nivelelor (putem folosi oricîte), practice, numărul acestora nu poate fi mai mare decît numărul componentelor vectorului.

Exemplul 1: Fie dată mulţimea A={1,2,... ,n}. Să se genereze toate permutările ce pot fi obţinute cu elemntele acestei mulţimi.

Rezolvare:

Pentru rezolvarea acestui exemplu vom implementa cu ajutorul unui vector o stivă cu 25 de nivele. În dependenţă de n, pe stivă se vor completa n nivele. Cînd stiva va fi plină, adică vor fi completate toate cele n nivele, şi vor fi juste condiţiile de validare se va afişa conţinutul stivei, aceasta fiind una din soluţiile problemei. Problema este rezolvată utilizînd tehnica backtracking recursiv. Pe lîngă stiva implementată static cu ajutorul unui vector, aici se utilizează şi stiva internă (procedura back este recursivă).

program backtraking_re;

uses crt;

type

vector =array [1..25]of integer;

var st:vector;

n:integer;

Procedure initial;

var i:integer;

begin

write('introduceti nr de elemente n=');

readln(n);

for i:=1 to 25 do

st[i]:=0;

end;

function valid(p:integer):boolean;

var ok:boolean;

i:integer;

begin

ok:=true;

for i:=1 to p-1 do

if st[p]=st[i] then ok:=false;

valid:=ok;

end;

procedure tipar(p:integer);

var i:integer;

begin

for i:=1 to p do

write (st[i]:4);

writeln;

end;

procedure back(p:integer);

var pval:integer;

begin

for pval:=1 to n do begin

st[p]:=pval;

if valid (p) then

if p=n then tipar (p) else

back(p+1); end; end;

begin clrscr;

initial;

back(1);

readkey;

end.
introduceti nr de elemente n=3

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Observaţie: Volumul de memorie alocat static pentru rezolvarea acestei probleme este: 25*2=50 octeţi pentru stivă.

n: 2 octeţi

În total sunt necesari 52 octeţi, indiferent de numărul de elemente ale mulţimii A, care nu trebuie să fie mai mare ca 25. (la estimarea volumului de memorie nu s-a ţinut cont de variabilele locale şi stiva internă)

Exemplul 2: Fie dată mulţimea A={1,2,... ,n}. Să se genereze toate submulţimile acestei mulţimi.

Rezolvare:

Pentru rezolvarea acestui exemplu, dinnou, vom implementa cu ajutorul unui vector o stivă cu 25 de nivele. Diferenţa faţă de exemplul precedent este acela, că aici numărul de nivele în stivă este tot timpul diferit (depinde de numărul de elemente din sublmulţime) dar nu este mai mare ca n.

Program submultimi;

uses crt;

type vector=array[0..25] of integer;

var st:vector; n:integer;

Procedure initial;

var i:integer;

begin

write('n=');

readln(n);

for i:=0 to 25 do st[i]:=0;

end;
Function valid (p:integer):boolean;

begin

valid:=true;

end;
Procedure tipar (p:integer);

var i:integer;

begin

for i:=1 to p do write(st[i]:4,' ');

writeln;

end;

Procedure back (p:integer);

var pval:integer;

begin

for pval:=st[p-1]+1 to n do

begin

st[p]:=pval;

if valid(p) then begin

tipar(p);

back(p+1);

end;

end;

end;

Begin

clrscr;

initial;

back(1);

readkey;

End.
Introdu numarul de elemente ale multimii, n=4

Multimea data:

1 2 3 4

----------------------------------

Submultimile acestei multimi:

----------------------------------

1

1 2

1 2 3

1 2 3 4

1 2 4

1 3

1 3 4

1 4

2

2 3

2 3 4

2 4

3

3 4

4

Observaţie: Volumul de memorie alocat static pentru rezolvarea acestei probleme este identic cu cel din exemplul precedent, adică 52 octeţi.

§5. Coada alocată static

Coada este acea structură de date în care toate înserările sunt făcute la unul din capetele cozii, iar toate ştergerile (în general, prelucrările) sunt făcute la celălalt capăt.

Este cu totul nerecomandabilă utilizarea vectorilor pentru simularea cozii (alocarea statică). Facem această precizare deoarece, în această situaţie are loc un fenomen de migraţie a datelor de la dreapta la stînga în cadrul vectorului.

Să presupunem că simulăm o coadă cu ajutorul unui vector cu zece componente, care reţin numere întregi. Presupunem de asemenea că niciodată în coadă nu vom mai avea mai mult de 4 elemente. Introducem în coadă numerele 1,2,3,4. pentru a avea unde să introducem şi altele completăm vectorul de la dreapta la stînga.

4

3

2

1

Dacă scoatem din coadă pe 1 şi introducem în coadă pe 5, coada va arăta astfel:

5

4

3

2

Scoatem din coadă pe 2 şi introducem pe 6:

6

5

4

3

Se observă acest fenomen de migraţie a datelor, de la dreapta spre stînga.

O altă soluţie ar fi ca, după fiecare stocare de date din coadă, să deplasăm întregul şir de date cărte dreapta, însă în acest caz se consumă mult timp.

O soluţie mai bună de implementare a cozii este să folosim un vector pe care îl privim ca fiind "circular" (facem convenţia ca după ultima componentă să urmeze prima). Adresa componentei de început a cozii va fi reţinută de o o variabilă, iar adresa componentei de sfîrşit va fi reţinută de o altă variabilă. Un astfel de procedeu poate fi folosit, dar nu este recomandabil atît timp cît există alocarea dinamică a memoriei.