Capitolul 8

Yüklə 0,55 Mb.

səhifə	4/4
tarix	07.09.2018
ölçüsü	0,55 Mb.
	#79713

1 2 3 4

§4. Stiva

O stivă poate fi definită şi ca o listă liniară simplu înlănţuită în care toate intrările şi ieşirile se fac la un singur capăt al ei.

În acest caz, elementul de pe nivelul k al stivei va reţine adresa elementului de pe nivelul k-1.

Deşi stiva poate fi prezentată ca fiind o listă liniară dublu înlănţuită. Motivul? Prezentînd stiva ca o listă dublu înlănţuită, avem avantajul că o putem folosi în mai multe aplicaţii (de exemplu, pentru backtracking, unde pentru a valida un element era necesară comparaţia sa cu cele aflate în stivă pe nivelele inferioare). Desigur, chiar folosind pentru stivă actuala definiţie putem realiza toate aplicaţiile, însă mai greu (recursiv, cu pierdere de timp). Chiar modul de lucru standart cu stiva internă a calculatorului permite accesul la elemente ale stivei care nu se află pe ultimul nivel.

În continuare voi implementa stiva tot ca listă liniară dublu înlănţuită.

Fiecare înregistrare corespunzătoare stivei conţine trei informaţii: adresa înainte (a elementului următor), adresa înapoi şi informaţia utilă care diferă de la caz la caz.

Pentru a lucra cu o astfel de stivă sunt suficiente două proceduri: adaug şi scot, cu rolul de a adăuga şi, respectiv, de a scoate o informaţie din stivă. Modul de alcătuire al acestora îl putem analiza din programul următor:

Program stiva;

type ref=^inr;

inr=record

nr:integer;

adrurm,adrinap:ref

end;

var v:ref;

procedure adaug (var v:ref);

var c:ref;

n:integer;

begin

write(‘n=’);readln (n);

new(c);

c^.nr:=n;

c^.adrurm:=nil;

c^.adrinap:=v;

if v<>nil then v^.adrurm:=c;

v:=c

end;
procedure scot (var v:ref);

var c:ref;

begin

if v=nil

then

writeln(’Stiva este vida’)

else

begin

writeln(v^.nr);

c:=v;

v:=v^.adrinap;

dispose(c)

end

end;
begin

adaug(v); adaug(v);

scot(v);scot(v);scot(v)

end.
Spre deosebire de simularea stivei prin intermediul vectorilor, aici avem avantajul că stiva nu este limitată la cele n componente alocate vectorului. Principalul dezavantaj al acestui mod de simulare a stivei este faptul că pe lîngă informaţia utilă se reţin informaţii de adresă, fapt care duce la consum de memorie.

Exemplul 1: Un copil a împrumutat un obiect de la alt copil, acesta din urmă – altuia ş.a.m.d. Să se afişeze ordinea în care fiecare copil trebuie să returneze cartea, astfel încît ea să ajungă la proprietar, dacă se ştie că fiecare este obligat să înapoieze cartea celui de la care a împrumutat-o.

Rezolvare:

Program stiva;

uses crt;

type nume=string[20];

legatura=^persoana;

persoana=record

name:nume;

next:legatura;

end;

var primul:legatura;

s:nume;

Procedure Creeaza_stiva(var primul:legatura; s:nume);

begin

new(primul);

primul^.next:=nil;

primul^.name:=s;

end;
Procedure Insereaza_comp(var primul:legatura; var s:nume);

var temp:legatura;

begin

new(temp);

temp^.next:=primul;

primul:=temp;

primul^.name:=s;

end;

Procedure Scoate_virf(var primul:legatura; var s:nume);

{s este virful scos din coada}

var temp:legatura;

begin

temp:=primul;

s:=primul^.name;

primul:=primul^.next;

dispose(temp);

end;
Begin

clrscr;

writeln('Introdu numele proprietarului:');

readln(s);

Creeaza_stiva(primul,s);

repeat

writeln('Introdu numele urmatorului copil sau scrie STOP');

readln(s);

Insereaza_comp(primul,s);

until s='STOP';

writeln('Continutil stivei');

writeln('------------------------');

writeln('Obiectul va fi restituit in ordinea:');

Scoate_virf(primul,s);

repeat

Scoate_virf(primul,s);

write(s,'->');

until primul=nil;

{ write(#8,#8,#8,#8,' ');}

readkey;

End.
Introdu numele proprietarului:

Ana