Capitolul 8



Yüklə 0,55 Mb.
səhifə4/4
tarix07.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


Introdu numele urmatorului copil sau scrie STOP

Dina


Introdu numele urmatorului copil sau scrie STOP

Corina


Introdu numele urmatorului copil sau scrie STOP

Mihai


Introdu numele urmatorului copil sau scrie STOP

Ion


Introdu numele urmatorului copil sau scrie STOP

Stefan


Introdu numele urmatorului copil sau scrie STOP

STOP


Continutil stivei

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

Obiectul va fi restituit in ordinea:

Stefan->Ion->Mihai->Corina->Dina->Ana->


§5. Coada


În coadă toate intrările se fac la un capăt şi toate ieşirile se fac la celălalt capăt. Coada se poate implementa dinamic cu mare uşurinţă. Astfel va fi implementată ca o listă liniară simplu înlănţuită (sau, pentru a uşura anumite operaţii, chiar dublu înlănţuită). O variabilă de tip referinţă va reţine o adresă de început a cozii, iar alta de acelaşi tip va reţine adresa de sfîrşit.



Exemplul 1: Se dă numarul natural n. Să se afiseze în ordine crescătoare primele n numere naturale, a căror descompunere în factori primi conţine doar factori din mulţimea {7,11,13}.

Rezolvare:

Construim trei cozi: C7, C11,C13, care vor conţine numere neafişate cu proprietaea menţionată şi care se vor completa după regula de ma jos. Evident, dacă un număr t satisface proprietatea menţionată, atunci numerele 7t, 11t, 13t de asemenea satisfac această proprietate. Procedăm astfel:



      1. fie că ultimul număr afişat cu proprietatea menţionată este este t (evident primul număr este 1);

      2. în coada C7 (respectiv C11,C13) plasăm numărul 7t (respectiv 11t,13t);

      3. pentru a afişa următorul număr, alegem intre vîrfurile cozilor numărul cel mai mic. Acest număr x va fi afişat şi va fi scos din coada în care a fost găsit. Considerîn t=x, se trece din nou la pasul 1.

program coada;

uses crt;

type legatura=^Comp;

Comp=record

numar:longint;

next:legatura

end;


var p7begin,p7End:legatura; {virful si sfirsitul cozii C7}

p13begin,p13End:legatura; {virful su sfirsitul cozii C13}

p11begin,p11End:legatura; {virful si sfirsitul cozii C11}

n1,n2,n3,x,k:longint;

n,contor:integer;

procedure Creeaza_coada(var pBegin,pEnd:legatura;n:longint);

begin

new(pBegin);



pBegin^.next:=NIL;

pbegin^.numar:=n;

pEnd:=pBegin;

end;


procedure Adauga_coada(var pEnd:legatura;n:longint);

var temp:legatura;

begin

new(temp);



temp^.next:=NIL;

pEnd^.next:=temp;

pEnd:=temp;

pEnd^.numar:=n;

end;

Procedure Citeste_virful(pBegin:legatura;var n:longint);



begin

n:=pBegin^.numar;

end;

procedure Scoate_virful(var pBegin:legatura);



var temp:legatura;

begin


temp:=pBegin; pBegin:=pBegin^.next; dispose(temp);

end;


Function min(a,b,c:longint):longint;

var m:longint;

begin

m:=a;


if b

if c

min:=m;

end;


Procedure Scrie_adauga(t:longint);

begin


inc(contor);

if contor mod 10=0 then writeln(t) else write(t,' ');

if t>1 then begin {pentru t=1, C7,C13,C11 deja au 7,13,11}

Adauga_coada(p7End,7*t);

Adauga_coada(p13End,13*t);

Adauga_coada(p11End,11*t);

end;

end;


BEGIN

clrscr;


write('Introdu n=');readln(n);

Creeaza_coada(p7Begin,p7End,7);

Creeaza_coada(p13Begin,p13End,13);

Creeaza_coada(p11Begin,p11End,11);

Scrie_adauga(1);

k:=1;


while k<>n do begin

Citeste_virful(p7begin,n1);

Citeste_virful(p13begin,n2);

Citeste_virful(p11begin,n3);

x:=min(n1,n2,n3);

scrie_adauga(x); k:=k+1;

if n1=x then Scoate_virful(p7begin);

if n2=x then Scoate_virful(p13begin);

if n3=x then Scoate_virful(p11begin);

end;


readkey;END.

Introdu n=30

1 7 11 13 49 77 91 121 143 169

343 539 637 847 1001 1183 1331 1573 1859 2197

2401 3773 4459 5929 7007 8281 9317 11011 13013 14641

§6. Structuri arborescente


Vom defini arborii binari ca un set finit T de unul sau mai multe noduri, astfel încît:

  • Există un nod cu destinaţie specială numită tulpina (rădăcina) arborelui;

  • Celelalte noduri sunt repartizate în două seturi disjuncte şi fiecare din aceste seturi este la rîndul lui un arbore.

Observaţie:

  • Cei doi arbori subordonaţi tulpinei poartă denumirea de subarbore stîng şi subarbore drept;

  • Definiţia este recursivă, acest lucru fiind de mare folos;

  • Pentru tulpină se mai foloseşte şi termenul de vîrf;

  • Dacă un nod nu subordonează arbori, atunci el se numeşte nod terminal, în caz contrar se numeşte nod neterminal.

Ne propunem să construim un program care generează în memorie un arbore binar. Pentru aceasta, fiecare nod va fi o înregistrare care conţine trei cîmpuri: informaţia utilă, adresa subarborelui stîng şi adresa subarborelui drept. Modul recursiv de definire a arborilor binari ne conduce la ideea de a folosi o funcţie recursivă şi chiar de a utiliza metoda Divide et Impera conform acestei metode se procedează astfel:

  • Se citeşte informaţia utilă pentru un nod;

  • Se alocă spaţiu în memorie pentru aceasta;

  • Se completează informaţia utilă;

  • Se costruieşte subarborele stîng;

  • Se costruieşte subarborele drept.

Exact în acest mod procedează funcţia arb de tip referinţă. Aici, este de remarcat modalitatea de trecere la construcţia subarborilor stîng şi drept. Atunci cînd trebuie completate cîmpurile de adresă, acestea primesc ca valoare tocmai valoarea funcţiei, ceea ce duce autoapelarea ei. Semnalizarea faptului că nu avem subarbore stîng sau drept se face completînd 0 pentru informaţia utilă.

Se folosesc trei metode de parcurgere a arborilor.



  • Stînga, vîrf, dreapta sau inordine, în care se parcurg mai întîi subarborele stîng, rădăcina şi apoi subarborele drept;

  • Vîrf, stînga, dreapta sau preordine, în care se parcurg mai întîi rădăcina, subarborele stîng şi apoi subarborele drept;

  • Stînga, dreapta, vîrf sau postordine, în care se parcurg mai întîi subarborele stîng, subarborele drept şi apoi rădăcina.

Fie arborele de mai jos:

Datele se introduc astfel:

1240050800360079001000.

Parcurgerea în inordine înseamnă:

4 2 5 8 1 6 3 9 7 10.

Parcurgerea în preordine înseamnă:

1 2 4 5 8 3 6 7 9 10.

Parcurgerea în postordine înseamnă:

4 8 5 2 6 9 10 7 3 1.

Parcurgerile arborului binar sunt realizate de procedurile: svd ( stînga, vîrf, dreapta), vsd (vîrf, stînga, dreapta), sdv (stînga, dreapta, vîrf). În comentariul pe care îl facem acestor proceduri ne mărginim să precizăm că sunt realizate utilizînd tehnica Divide et Impera.

Program arbori;

Uses crt;

type ref=^inr;

inr=record

st,dr:ref;

nr:integer

end;

var c:ref;



Function arb:ref;

var n:integer;

c:ref;

begin


read(n);

if n<>0


then

begin


new(c);

arb:=c;


arb^.nr:=n;

arb^.st:=arb;

arb^.dr:=arb

end


else arb:=nil

end;


Procedure svd (c:ref);

begin


if c<>nil

then


begin

svd(c^.st);

write(c^.nr,’ ‘);

svd(c^.dr)

end

end;


Procedure vsd (c:ref);

begin


if c<>nil

then


begin

write(c^.nr,’ ‘);

vsd(c^.st);

vsd(c^.dr)

end

end;


Procedure sdv (c:ref);

begin


if c<>nil

then


begin

svd(c^.st);

svd(c^.dr);

write(c^.nr,’ ‘)

end

end;


Begin

Clrscr;


Writeln(‘Introdu arborele’);

c:=arb;


writeln;

writeln(‘Parcurg stinga virf dreapta’);

svd(c);writeln;

writeln(‘Parcurg virf stinga dreapta’);

vsd(c);writeln;

writeln(‘Parcurg stinga dreapta virf’);

sdv(c);readkey;

end.
Introdu arborele:

1 2 4 0 0 5 0 8 0 0 3 6 0 0 7 9 0 0 10 0 0

Parcurgere stinga virf dreapta

4 2 5 8 1 6 3 9 7 10

Parcurgere virf stinga dreapta

1 2 4 5 8 3 6 7 9 10

Parcurgere stinga dreapta virf

4 8 5 2 6 9 10 7 3 1
Vom defini arbori oarecare după D.E. Knuth. Se numeşte arbore oarecare un set finit T de unul sau mai multe noduri astfel încît:


  • există un nod cu destinaţie specială numit tulpina arborelui;

  • celelalte noduri sunt repartizate în m≥0 seturi disjuncte T1,T2, ..., Tm unde fiecare din aceste seturi la rîndul său este un arbore.

Am folosit această definiţie recursivă întrucît ne este de mare folos în scrierea programului care creează un arbore oarecare.

În programul care urmează construim un arbore oarecare în care fiecărui nod i se subordonează cel mult trei subarbori.

Pentru un nod se completează informaţia utilă (un număr întreg) precum şi un vector de adrese ale subarborilor subordonaţi nodului respectiv. Am utilizat tehnica Divide et Impera atît la creare cît şi la parcurgere.

Fie arborele oarecare din figura de mai jos:



Pentru a crea acest arbore vom introduce informaţiile în ordinea următoare:

1 2 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0.

Vom prezenta două dintre cele mai uzuale metode de parcurgere a arborilor oarecare:

1) Parcurgerea în adîncime (realizată de procedura padinc), în care se viziteză întîi tulpina, apoi subarborii de la stînga la dreapta (pentru arborele din figura de mai sus avem: 1 2 3 4 5 6);

program arbg;

type ref=^inr;

vectad=array [1..3] of ref;

inr=record

nr:integer;

a:vectad

end;


var c:ref;

Function arb:ref;

var c:ref;

n,i:integer;

begin

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



if n<>0

then


begin

new(c);


arb:=c;

arb^.nr:=n;

for i:=1 to 3 do arb^.a[i]:=arb

end


else arb:=nil

end;


Procedure padinc (c:ref);

var i:integer;

begin

if c<>nil then



begin

writeln(c^.nr);

for i:=1 to 3 do padinc(c^.a[i])

end


end;
begin

c:=arb;


padinc(c)

end.



  1. Parcurgerea în lăţime.

În acest caz, fiecare element al listei liniare care constituie coada va fi o înregistrare care cuprinde în general două cîmpuri: adresa înapoi şi informaţia utilă. Dacă variabilele de tip referinţă b şi v vor reţine adresa utimului element introdus în coadă şi adresa elementului care poate fi scos din coadă.

Lucrul cu coada se poate face utilizînd trei proceduri:



    1. crearea cozii;

    2. adăugarea la coadă;

    3. scoaterea (prelucrarea) din coadă.

Crearea cozii

Această operaţie este realizată de procedura ccoada. Crearea cozii constă în:



  • alocarea spaţiului pentru o înregistrare;

  • completarea informaţiei utile;

  • completarea informaţiei înapoi prin nil.

Adăugarea la coadă

Operaţia de adăugare la coadă este realizată de procedura adcoada. Parametrii ei sunt: t (informaţia utilă) şi b (adresa ultimului element introdus în coadă). Pentru aceasta se realizează următoarele operaţii:



  • alocarea spaţiului pentru noua înregistrare;

  • completarea informaţiei utile;

  • completarea cîmpului de adresă înapoi a înregistrării de la b cu adresa noii înregistrări;

  • b va lua valoarea adresei noii înregistrări.

Scoaterea din coadă

Această operaţie este realizată de procedura scoada. În acest sens se realizează operaţiile:



  • se reţine adresa elementului care urmează a fi scos din coadă;

  • se şterge înregistrarea acestui element;

  • v va lua valoarea adresei înregistrării plasate înaintea celei şterse.

O aplicaţie foarte importantă a structurii de coadă este parcurgerea în lăţime a arborilor oarecare.

Pentru arborele din figura de mai sus, ordinea de parcurgere a vîrfurilor este următoarea: 1 2 5 6 3 4.

În exemplul care urmează, această parcurgere este realizată de procedura tipari. Ideea de lucru este următoarea:


  • se porneşte cu o coadă care conţine numai rădăcinile arborelui;

  • pentru fiecare element din vîrful cozii procedăm astfel:

  • îl listăm;

  • îi încărcăm toţi succesorii în coadă;

  • algoritmul se încheie cînd coada este vidă.

program arbg;

uses crt;

type ref=^inr;

vectad=array [1..3]of ref;

inr=record

nr:integer;

a:vectad

end;


refl=^inr1;

inr1=record

inreg:inr;

inapoi:ref1

end;

var c:ref;



b,v:ref1;

Function arb:ref;

var c:ref;

n,i:integer;

begin

write(‘n=’);



readln(n);

if n<>0


then

begin


new(c);

arb:=c;


arb^.nr:=n;

for i:=1 to 3 do arb^.a[i]:=arb

end

else arb:=nil



end;

Procedure ccoada;

var d:ref1;

i:integer;

begin

new(d);


d^.inreg:=c^;

d^.inapoi:=nil;

b:=d;

v:=d


end;

Procedure adcoada (t:inr; var b:ref1);

var d:ref1;

begin


new(d);

d^.inapoi:=nil;

d^.inreg:=t;

b^.inapoi:=d;

b:=d

end;


Procedure scoada (var v:ref1);

var d:ref1;

begin

d:=v;


dispose(v);

v:=d^.inapoi

end;

Procedure tipari (var b,v:ref1);



var d:ref;

t:inr;


i:integer;

begin


while v<>nil do

begin


writeln(v^.inreg.nr);

for i:=1 to 3 do begin

d:=v^.inreg.a[i];

if d<>nil

then

begin


t:=d^;

adcoada (t,b)

end

end;


scoada(v)

end


end;

Begin


Clrscr;

c:=arb;


ccoada;

tipari(b,v);

readkey;

end.
n=1 2 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0

1 2 5 6 3 4

Concluzii

Folosind datele cu structură implicită (statică), putem rezolva reprezentativ o clasă limitată de probleme. În multe cazuri relaţiile dintre componente nu numai că se modifică dinamic, dar în acelaşi timp, pot deveni deosebit de complexe. Prin urmare, este necesară folosirea unor structuri de date în care relaţiile dintre componente să fie reprezentate şi prelucrate în mod explicit (dinamic).

La alocarea dinamică a memoriei volumul necesar de memorie se reduce considerabil.

După timpul de execuţie, vom da preferinţă algoritmilor unde s-a folosit alocarea dinamică a memoriei.

Un lucru ce trebuie menţionat este şi acela că, în mediul de programare Turbo Pascal pentru alocarea dinamică a memoriei sunt rezervaţi 256Ko, adică de 4 ori mai mult decît în cazul static (64Ko). Dimensiunile Heap-ului pot fi modificate cu ajutorul direcvtivelor de compilare sau a comenzilor mediului de programare.

Un dezavantaj ar fi, că textul programelor este destul de mare.



Bibliografie





  1. Andrei Braicov, Tubo Pascal. Culegere de probleme, Chişinău, Prit

  2. Anatasiu A., Cu ce se înscrie un algoritm? Simplu, Editura Agni, Bucureşti,1993.

  3. Anatasiu A., Probleme de Informatică, Editura Petrion, Bucureşti, 1995.

  4. Bălănescu T.,Gavrilă S., Georgescu H., Gheorghe M., Sofonea L., Văduva I., Programare în lumbajul Pascal şi Turbo Pascal, Editura Tehnică, Bucureşti, 1992.

  5. Dogaru o., Petcu D., Petrov Gh., Turbo Pascal, Editura de Vest Timişoara, 1994.

  6. Ivaşc C., Prună M., Bazele informaticii (Graful şi elemente de combinatorică), Editura Petrion, Bucureşti 1995.

  7. Livovschi Georgescu H., Analiza şi sinteza algoritmilor, Bucuruşti 1986.

  8. Mitranu V., Provocarea algoritmilor, Editura Agni, Bucureşti,1994.

  9. Niculescu R.,Albeanu G.,Domocos V., Culegere de probleme Turbo Pascal. Editura Tempus 1993.

  10. Popovici C., State L., Georgescu H., Bazele informaticii- vol.1, Tipografia Univers, Bucureşti 1990.

  11. Rancea D.,Limbajul Turbo Pascal, Editura Libris, Cluj 1994.

  12. Tomescu I., Bazele informaticii. Manual pentru clasa X-XI, Editura Didactică şi Pedagogică, Bucureşti, 1994.

  13. Tomescu I., Probleme de combinatorică şi teoria grafelor, Editura Didactică şi Pedagogică, Bucureşti, 1981.

  14. Tudor S., Manual de informatică pentru clasa a XI-a. Editura Teora, Bucureşti, 1995.





Yüklə 0,55 Mb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin