13 tipul referinta( structuri de date dinamice )

104

13. Tipul referin••, structuri de date dinamice

( liste înl•n•uite •i arbori binari).

13.1. Tipul referin••.

Limbajul Pascal ofer• posibilitatea de a lucra atât cu variabile statice cât •i

cu variabile dinamice. Caracteristicile variabilelor statice sunt bine definite,

cunoscute •i fixe. Structura, tipul •i adresa de memorie nu se pot modifica în

timpul execu•iei. Aceste variabile sunt referite prin numele lor, fiec•rui nume

asociindu-i-se o adres• fizic• de memorie. Unei variabile statice i se poate

modifica doar valoarea, nu •i adresa (locul s•u) din memoria intern•.

Variabilele dinamice au un tip bine precizat înc• din faza de compilare

îns• ele pot fi alocate dinamic (pot lua fiin•• în faza de execu•ie a programului),

pot fi utilizate (referite) prin adresa lor din memoria intern• •i pot fi distruse

(dealocate) dac• nu mai sunt utile. Aceste variabile pot fi referite printr-o

variabil• de referin•• ce con•ine adresa variabilei dinamice. Variabila de referin••

poate face referiri numai la variabile dinamice de acela•i tip declarat, bine definit

•i fix. Aceast• legatur• (coresponden••) între variabila dinamic• •i tipul de date

referin•• permite cunoa•terea structurii variabilei dinamice.

Variabilele de tip referin•• vor con•ine în timpul execu•iei adrese de

memorie ale variabilelor dinamice referite. Datorit• acestui fapt, declararea

tipului referin•• poate fi f•cut• înaintea definirii tipului variabilei dinamice

referite.

Definirea unui tip referin•• •i a variabilelor de tip referin•• se face astfel:

Type Tip_Referin•• = ^ Tip_Var_Dinamic•;

Tip_Var_Dinamic• = ... { poate referi Tip_Referin•• }

Var Var_Ref1,Var_Ref2,... : Tip_Referin••; {Vor con•ine adrese}

105

Alocarea dinamic• (ocuparea zonei de memorie) pentru variabila dinamic•

se realizeaz• cu procedura :

New (Var_Ref)

care caut• în memoria intern• o zon• liber• pentru variabila dinamic• •i furnizeaz•

adresa acestei zone în variabila de tip referin•• (Var_Ref). Aceast• zon• este

alocat• variabilei dinamice, f•r• a fi ini•ializat•. Dimensiunea zonei alocate

variabilei dinamice este determinat• de tipul variabilei dinamice, a•a cum se poate

vedea în exemplul urm•tor :

Type Adresa=^Numar;

Numar = Record

Numar_Cifre : Byte;

Sir_Cifre : Array [1..100] of Byte

End;

Var n : Adresa;

Begin

New (n); { Se aloc• 101 octeti }

... {Prelucrare (n^) }

End.

Referirea unei variabile dinamice se face printr-o variabil• de tip referin••

(legat• de variabila dinamic•). Numele variabilei referin•• urmat de caracterul ^

reprezint• numele variabilei dinamice.

Eliberarea zonei de memorie ocupat• de o variabila dinamic• se va

executa cu instruc•iunea (apelul de procedur•) :

Dispose (Var_Ref)

care disponibilizeaz• zona de la adresa con•inut• în variabila Var_Ref.

Dac• o variabil• referin•• nu refer• nici o variabil• dinamic•, atunci

valoarea variabilei referin•• este Nil .

106

Variabilele referin•• se pot utiliza în instruc•iuni de atribuire prin care o

astfel de variabil• prime•te valoarea altei variabile de acela•i tip sau constanta Nil

•i, de asemenea, în expresii rela•ionale cu opera•orii "=" sau "<>".

Subliniem c• orice referire a variabilei dinamice P^ trebuie s• se fac• între

apelurile

NEW (P) •i DISPOSE (P).

În urm•torul program se adun• dou• numere ra•ionale citite de la tastatur•.

Program Rationale; {Programul Tipul referin••}

Type Q = ^Rational;

Rational = Record

Numarator ,

Numitor : Integer

End;

Var a,b,c : Q ;

Function Cmmdc (m,n:Integer) : Integer; {Gaseste c.m.m.d.c.}

Var Rest:Integer; {al numerelor m •i n}

Begin

While n<>0 Do Begin

Rest := m Mod n;

m := n; n := Rest

End {while};

Cmmdc := m

End; {Cmmdc}

Function Cmmmc (m,n:Integer) : Integer; {Calculeaza c.m.m.m.c.}

Begin {al numerelor m •i n nenule}

If m*n = 0 Then Writeln(’nr.nul’) Else

Cmmmc := m * n Div Cmmdc (m,n)

End; {Cmmmc}

107

Procedure Simplific (Var p:Q); {Simplifica nr.rational p }

Var Divizor_comun: Integer;

Begin

With p^ do Begin

Divizor_comun:=Cmmdc(Numarator,Numitor);

If Divizor_comun > 1 Then Begin

Numarator := Numarator Div Divizor_comun;

Numitor := Numitor Div Divizor_comun End {If}

End {With}

End; {Simplific}

Procedure Citeste (Var p:Q); {Citeste nr.rational in p}

Begin

Write (’ Numarator,numitor = ’); Readln (p^.Numarator, p^.Numitor);

Simplific (p)

End; {Citeste}

Procedure Aduna (a,b:Q; Var c:Q);

Var N_comun: Integer; { Numitorul comun }

Begin

N_comun := Cmmmc(a^.Numitor,b^.Numitor);

c^.Numarator := a^.Numarator * (N_comun Div a^.Numitor) +

b^.Numarator * (N_comun Div b^.Numitor);

c^.Numitor :=N_comun;

Simplific (c)

End; {Aduna}

Procedure Tipareste (p:Q); {Tipareste nr.rational p}

Begin With p^ do Write (Numarator,’/’,Numitor)

End;

Begin {Programul principal}

New (a); Citeste (a); New (b); Citeste (b);

New (c); Aduna (a,b,c);

Tipareste(a); Write(’ + ’); Tipareste(b); Write(’ = ’); Tipareste (c);

Dispose (a); Dispose (b); Dispose (c); Readln;

End.

108

Vom rezolva în continuare aceea•i problem• în alt• manier•, utilizând

func•ia Aduna pentru suma a dou• numere ra•ionale care va da ca rezultat adresa

num•rului ra•ional calculat.

Program Rationale; {Programul 2. Tipul referin••}

Type Q = ^Rational;

Rational = Record

Numarator, Numitor : Integer

End;

Var a, b : Q ;

Function Cmmdc (m,n:Integer) : Integer; {Gaseste c.m.m.d.c.}

Var Rest:Integer; {al numerelor m •i n}

Begin

While n<>0 do begin

Rest := m Mod n; m := n; n := Rest

End {while};

Cmmdc := m

End;

Function Cmmmc (m,n:Integer): Integer; {Calculeaza c.m.m.m.c.}

Begin {al numerelor m •i n nenule}

If m*n = 0 Then Writeln(’nr.nul’) Else

Cmmmc := m * n Div Cmmdc (m,n)

End;

Procedure Simplific (Var p:Q); { Simplifica nr.rational p }

Var Divizor_comun: Integer;

Begin

With p^ Do Begin

Divizor_comun:=Cmmdc(Numarator,Numitor);

If Divizor_comun > 1 Then Begin

Numarator := Numarator Div Divizor_comun;

Numitor := Numitor Div Divizor_comun End {If}

End {With}

End;

109

Procedure Citeste (Var p:Q); {Citeste nr.rational in p}

Begin

With p^ do Begin

Write(’ Numarator numitor = ’); Readln (Numarator, Numitor);

If Numitor=0 Then

Repeat

Write (’ Numitor = 0! dati altul’); Readln (Numitor);

Until Numitor <> 0;

End; {With}

Simplific (p)

End;

Function Aduna (a,b:Q) : Q;

Var Numit_comun: Integer; s:Q;

Begin

New (s);

Numit_comun := Cmmmc(a^.Numitor,b^.Numitor);

s^.Numarator:= a^.Numarator * (Numit_comun Div a^.Numitor)+

b^.Numarator * (Numit_comun Div b^.Numitor);

s^.Numitor :=Numit_comun;

Simplific (s);

Aduna:=s; Dispose(s)

End;

Procedure Tipareste (p:Q); {Tipareste nr.rational p}

Begin

With p^ Do Write (Numarator,’/’,Numitor)

End;

Begin

New (a); Citeste (a); New (b); Citeste (b);

Tipareste(a); Write(’+’); Tipareste(b); Write(’=’); Tipareste(Aduna(a,b));

Dispose(a); Dispose(b);

Readln;

End.

110

În limbajul Pascal se pot utiliza variabile nelegate de un anumit tip de baz•

(tipul variabilei dinamice) în scopul memor•rii valorilor unor variabile de tip

referin•• (memorare de adrese). Acest tip referin•• nelegat, este tipul Pointer.

Opera•iile ce se pot efectua cu astfel de variabile sunt de tip atribuire

astfel:

Var AdrP : Pointer;

Adr1 : Tip_Referin••1;

Adr2 : Tip_Referin••2;

Begin ...

AdrP:=Adr1;

Adr2:=AdrP;

...

End.

În exemplul anterior func•ia Aduna putea avea urm•torul antet:

Function Aduna (a,b:Q) : Pointer;

f•r• a fi necesare alte modific•ri în program.

În urm•torul exemplu ne propunem s• tip•rim în hexazecimal con•inutul

zonei de memorie pe care se reprezint• un num•r real.

Program Numar_Real; {Prgramul Pointeri}

Const Lung = 6;

Type Sir_Octeti = Array[1..Lung] of Byte;

Var Pointer_Real : ^Real;

Pointer_Byte : ^Sir_Octeti;

Pointer_Manevra : Pointer;

i : Integer;

Function Hexa (Cifra:Byte) : Char; {Tipareste o cifra}

Begin {hexazecimala}

If Cifra < 10 Then Hexa := Chr(Cifra+Ord(’0’))

Else Hexa := Chr(Cifra+Ord(’A’)-10)

111

End;

Procedure Print (Octet: Byte); {Tipareste continutul unui}

Begin {octet in hexazecimal}

Write (Hexa(Octet Div 16));

Write (Hexa(Octet Mod 16),’ ’)

End;


New ( Pointer_Real);

Write (’ Dati un numar real : ’);

Readln ( Pointer_Real^ );

Pointer_Manevra := Pointer_Real;

Pointer_Byte := Pointer_Manevra;

For i:=1 to Lung do Print (Pointer_Byte^[i]);

Dispose (Pointer_Real);

Readln;

End.

13.2. Liste înl•n•uite.

Prin list• se în•elege o colec•ie de elemente de acela•i tip

x1, x2, ... , xn,

în care x1 este primul element, xn este ultimul element •i pentru 1 < k < n

elementul xk are un unic succesor (pe xk+1) •i un unic predecesor (pe xk-1).

Se poate stabili o coresponden•• biunivoc• între elementele listei liniare •i

submul•imea numerelor naturale {1, 2, ..., n} astfel: primului element îi ata••m 1,

urm•torului 2 •i a•a mai departe, iar ultimului n. Num•rul natural asociat unui

112

element din list• se nume•te pozi•ia elementului respectiv. Vom spune c•

elementul de pe pozi•ia i precede elementul de pe pozi•ia j dac• i < j .

Rezult• c• pe o astfel de structur• de date putem defini urm•toarele func•ii:

Urm•torul, Precedentul •i Pozi•ia unui element, a•a cum se va vedea mai jos.

Asupra listelor liniare putem defini opera•ii care s• ne permit• ad•ugarea

unui element în lista, extragerea unui element (cu stergerea lui) din lista, cautarea

unui element cu o anumita proprietate •i crearea unei liste vide.

Specificarea acestor opera•ii se d• în continuare:

• Opera•ia CREARE(L) este:

L := lista vid• (f•r• nici un element);

• Opera•ia AD•UGARE (L,a) este: {în coada listei}

Dac• L la intrare con•ine elementele :

x1, x2, ... , xn,

dup• efectuarea opera•iei, lista L va con•ine elementele :

x1, x2, ... , xn, xn+1, unde xn+1 = a .

• Opera•ia C•UTARE (L,a,p) este:

Dac• L con•ine elementele :

x1, x2, ... , xn,

dup• efectuarea opera•iei, p prime•te o valoare între 1 •i n astfel ca xp = a, sau

valoarea n+1 în caz contrar.

• Opera•ia EXTRAGERE (L,p,a) este:

Daca L con•ine la intrare elementele :

x1, x2, ... , xn,

dup• efectuarea opera•iei a prime•te valoarea xp iar lista va avea elementele :

x1, x2, ... , xp-1, xp+1, ..., xn,

deci elementul xp a fost eliminat din list•.

113

Implementarea acestor opera•ii depinde de reprezentarea listei în memoria

calculatorului.

Reprezentarea unei liste liniare într-un program Pascal poate fi static• sau

dinamic•.

Reprezentarea static• a unei liste se realizeaz• printr-un vector X cu

componentele

x1, x2, ... , xn .

Spunem c• reprezentarea este static• întrucât alocarea memoriei necesare

vectorului X este f•cut• în timpul compil•rii. Deci locul în memorie al

elementelor listei nu se schimb• pe timpul executiei. Elementele listei se vor afla

în memorie în loca•ii consecutive cu o lungime maxim• (declarat•) care nu poate

fi dep••it• •i nici schimbat• în timpul executiei.

Spre deosebire de alocarea static•, reprezentarea dinamic• se realizeaz• cu

ajutorul tipului Pointer, alocarea memoriei f•cându-se în timpul execu•iei.

În locul listelor implementate static care ocup• o zon• fix• de memorie prin

loca•ii succesive, se poate utiliza o structur• mult mai flexibil• în care fiecare nod

este legat de nodul urm•tor al listei. Aceast• structur• o vom numi list•

înlan•uit• •i implementarea ei se poate realiza prin alocare dinamic• a memoriei.

Zona de memorie ocupat• de o astfel de list• cre•te sau scade dup• cum lista

con•ine mai multe sau mai pu•ine elemente, prin opera•ii de ad•ugare, respectiv

de •tergere.

O list• înl•n•uit• o vom reprezenta grafic astfel :

Un element din list• va con•ine pe lâng• informa•ia propriu-zis• •i adresa

(referin•a) urm•torului element din list• (marcat• în figura de mai sus prin s•ge•i).

Informa•ie Leg Informa•ie Leg Informa•ie Leg Informa•ie LegPrimul Ultimul

Nil

114

În acest fel având adresa primului element, vom putea accesa (reg•si) orice

element din lista înl•n•uit• prin parcurgarea secven•ial• a acesteia.

Ultimul element va con•ine o informa•ie (cod) de "santinel•" care va

marca sfâr•itul listei. Acest cod poate avea valoarea Nil ceea ce înseamn• c• acest

element nu mai este legat de un altul (nu exist• urm•torul element).

O astfel de list•, care con•ine în fiecare element adresa urm•torului

element poate fi parcurs• doar secven•ial începând de la primul element pân• la

ultimul, într-un singur sens. Aceast• structur• o vom numi list• simplu

înl•n•uit• .

Variabilele de tip referin•• dintr-un program Pascal care utilizeaz• o list•

simplu înl•n•uit• se pot declara astfel :

Type Tip_Info = ... ;

Adr = ^Tip_Elem;

Tip_Elem = Record

Informatie : Tip_Info;

Leg : Adr

End;

Var Primul, Element, Ultimul, Nou : Adr;

O list• simplu înl•n•uit•, în functie de disciplina de generare a ei (prin

ad•ugare element cu element) poate fi: lista înl•n•uit• înainte, lista înl•n•uit•

înapoi •i list• înl•n•uit• ordonat•.

Lista înl•n•uit• înainte este lista în care ad•ugarea se face în coada listei,

a•a cum se poate vedea în figura urm•toare:

Opera•ia scris• în Pascal este urm•toarea :

Procedure Adaug_in_coada (Nou:Adr; Var Primul,Ultimul:Adr);

Begin Nou^.Leg:=Nil;

If Primul=Nil Then Primul := Nou { Prima ad•ugare }

UltimulUltimulPrimul Nou

Informa•ie Leg Informa•ie Leg Informa•ie Leg Informa•ie Leg

Nil Nil

115

Else Ultimul^.Leg := Nou;

Ultimul:=Nou

End;

Lista înl•n•uit• înapoi este lista în care ad•ugarea se face în capul listei,

a•a cum se poate vedea în figura de mai jos:

Opera•ia scris• în Pascal este urm•toarea:

Procedure Adaug_in_cap (Nou:Adr; Var Primul:Adr);

Begin

Nou^.Leg := Primul;

Primul := Nou

End;

Lista înl•n•uit• ordonat• este lista în care ad•ugarea se face astfel încât

elementele listei s• fie într-o anumit• ordine (cresc•tor sau descresc•tor dup• o

anumit• cheie) a•a cum se poate vedea în urm•toarea figur• :

Dac• ORDINE este o func•ie boolean• care precizeaz• ordinea dorit•,

atunci procedura Pascal corespunz•toare este:

Procedure Adaug_ord (Nou:Adr; Var Primul:Adr);

Var Elem, Prec : Adr;

Begin Elem:=Primul;

While (Elem<>Nil) and not ORDINE(Elem, Nou) do Begin { Cauta locul }

Prec := Elem; Elem := Elem^.Leg End; { de inserare }

Nou^.Leg := Elem;

Nil

Primul Prec Elem

Informa•ie LegNou



Nil

PrimulNou Primul

116

If Elem=Primul

Then Primul:= Nou { Ad•ugare înaintea primului element }

Else Prec^.Leg := Nou;

End;

În exemplul urm•tor vom genera o list• prin ad•ugarea elementelor în

coada listei, în cap•tul listei sau în a•a fel încât lista sa fie ordonat• dup• un câmp

numit cheie. Disciplina de ad•ugare va fi aleas• de c•tre utilizator.

Program Liste_simplu_inlantuite; {Programul Liste}Type Tip_Cheie = Integer; Tip_Date = String[20]; Tip_Info = Record

Cheie : Tip_Cheie;Date : Tip_Date

End; Adr = ^Tip_Elem; Tip_Elem = Record

Inf : Tip_Info;Leg : Adr

End;

Var Lista : Adr; { Adresa primului element } Disc : Char; { Tipul adaugarii }

Procedure Citesc (Var Element:Adr);Begin New (Element); Write (’ ................... Cheie, Date : ’); With Element^, Inf do Readln (Cheie,Date)End;

Procedure Generare (Var Primul:Adr; Disc:Char);Var Nou,Ult : Adr; Rasp : Char;

Procedure Adaug_in_coada; Begin Nou^.Leg:=Nil; If Primul=Nil Then Primul := Nou Else Ult^.Leg := Nou; Ult:=Nou End;

117

Procedure Adaug_in_capat; Begin Nou^.Leg := Primul; Primul := Nou End;

Procedure Inserare_ord; Var Elem, Prec : Adr; Begin Elem:=Primul; While (Elem<>Nil) and (Elem^.Inf.Cheie < Nou^.Inf.Cheie) do Begin Prec := Elem; Elem := Elem^.Leg End;{While} Nou^.Leg := Elem; If Elem=Primul Then Primul := Nou

Else Prec^.Leg := Nou; End;

Begin {Generare} Primul:=Nil; Repeat Repeat Write (’Adaugati(D,N):’); Readln(Rasp); Rasp:=Upcase(Rasp); Until Rasp in [’D’,’N’]; If Rasp = ’D’ Then Begin Citesc (Nou); Case Disc of ’F’ : Adaug_in_coada;

’L’ : Adaug_in_capat;’O’ : Inserare_ord

End {Case} End {If} Until Rasp = ’N’End;

Procedure Parcurgere (Elem:Adr);Begin While Elem <> Nil Do With Elem^ Do Begin With Inf Do Writeln (Cheie:5,Date); Elem:=Leg End {With}End;

Begin Repeat Writeln (’ Ce disciplina doriti la ad•ugare ? ’); Writeln (’ F = in coada listei (FIFO) ’); Writeln (’ L = in capul listei (LIFO) ’); Writeln (’ O = lista ordonata ’); Write (’ Optiune : ’); Readln (Disc); Disc:=Upcase(Disc) Until Disc in [’F’,’L’,’O’];

118

Generare (Lista,Disc); { Creerea listei } For Disc:=’A’ to ’E’ do Writeln; Writeln(’Elementele listei sunt:’); Parcurgere (Lista); { Listarea listei } ReadlnEnd.

•tergerea unui element din list• se realizeaz• prin modificarea leg•turii

elementului precedent (dac• acesta exist•) urmat• de dealocarea zonei ocupate de

elementul •ters astfel:

Opera•ia de •tergere (scris• în Pascal) a elementului Elem din lista L este

urm•toarea:

Procedure Stergere(Var Elem,Prec,L: Adr); {Prec=precedentul }

Begin { lui Elem }

If L = Elem { dac• se sterge primul element }

Then L := Elem^.Leg

Else Prec^.Leg := Elem^.Leg;

Dispose (Elem);

End;

În exemplul urm•tor se poate urm•ri •tergerea unor elemente precizate prin

cheia con•inut• în informa•ia propriu-zis• a elementelor.

Program Stergere_element_din_lista;{Creeaza o lista de elemente (cheie,string),}

Type Tip_Cheie = Integer; {apoi sterge elemente •i tipareste lista finala }

Tip_Date = String[20];

Tip_Info = Record

Cheie : Tip_Cheie;

Date : Tip_Date

End;

Adr = ^Tip_Elem;


Nil

Primul Prec Elem

119

Tip_Elem = Record

Inf : Tip_Info;

Leg : Adr

End;

Var Lista : Adr; { Adresa primului element }

Procedure Citesc (Var Element:Adr); {Citeste informatia}

Begin {din nodul Element}

Write (’ ............ Cheie, Date : ’);

With Element^.Inf do Readln(Cheie,Date)

End;

Procedure Generare (Var Primul:Adr); {Creaza lista}

Var Nou : Adr; Rasp : Char;

Begin

Primul:=Nil;

Repeat

Repeat

Write (’ Adaugati (D,N) : ’);

Readln (Rasp); Rasp:=Upcase(Rasp);

Until Rasp in [’D’,’N’];

If Rasp = ’D’ Then Begin

New(Nou); Citesc (Nou);

Nou^.leg:=Primul; Primul:=Nou

End {If}

Until Rasp = ’N’

End;

Procedure Stergere (Var Primul,Prec:Adr); {Sterge succesorul}

Var Elem:adr; { lui Prec din lista Primul}

Begin

If (Prec=Nil)

Then Begin Elem:=Primul;

Primul := Primul^.Leg

End

Else Begin Elem:=Prec^.Leg;

120

Prec^.Leg := Elem^.Leg

End;

Dispose (Elem)

End;

Procedure CAUTA(Primul:adr; Cod: Tip_Cheie; Var Prec:adr);

Var Elem:Adr; {Cauta in lista Primul, elementul cu cheia Cod }

Begin { •i retine in Prec predecesorul acestui element }

Elem:=Primul; Prec := Nil;

While (Elem<>Nil) And (Elem^.Inf.Cheie<>Cod) Do Begin

Prec:=Elem; Elem:=Elem^.Leg End; {While}

If (Elem=Nil) Then WriteLN (’ Nu exista elementul cu codul ’,Cod)

End;

Procedure Stergelemente (Var Primul:Adr); {Sterge la cerere}

Var Elem,Prec : Adr; {elemente din lista Primul}

Cod : Tip_Cheie;Rasp : Char;

Begin

Repeat

Write (’Sterg element ? (D,N):’); Readln(Rasp); Rasp:=Upcase(Rasp);

If Rasp=’D’ Then Begin

Write (’ Cheia elementului : ’); Readln(Cod);

Cauta(Primul,Cod,Prec); Stergere(Primul,Prec)

End {If}

until Rasp=’N’

End;

Procedure Parcurgere (Primul:Adr); {Parcurge lista Primul}

Var Elem:adr; {si-i tipareste continutul}

Begin

While Elem <> Nil Do Begin

With Elem^.inf do Writeln (Cheie:5,Date);

Elem:=Elem^.Leg End {While}

End;

121

Begin {Programul principal }

Generare (Lista); { Creerea listei }

Stergelemente(Lista); { Stergere elemente }

Parcurgere (Lista); Readln { Listarea listei }

End.

Lista simplu înl•n•uit• poate fi traversat• doar într-un singur sens începând

cu primul pân• la ultimul element, pentru c• un element con•ine doar adresa

urm•torului element din list•. Dac• dorim sa travers•m lista •i invers (de la coad•

la cap•t) atunci va trebui s• re•inem în fiecare element •i adresa elementului

anterior (precedent) :

O list• care are aceast• proprietate se nume•te lista dublu înl•n•uit•.

Variabilele de tip referin•• dintr-un program Pascal care utilizeaz• o list•

dublu înl•n•uit• se pot declara astfel:

Type Tip_Cheie = ...;

Tip_Date = ...;

Tip_Info = Record

Cod : Tip_Cheie;

Info : Tip_Date

End;

Adr = ^Tip_Elem;

Tip_Elem = Record

Leg.St. Informa•ie Leg.Dr.

Primul Ultim

Nil Nil

LegSt. Inf. LegDr.LegSt. Inf. LegDr. LegSt. Inf. LegDr. LegSt. Inf. LegDr.

122

Leg_Preced : Adr; {Leg_St}

Informatii : Tip_Info;

Leg_Urm•tor : Adr {Leg_Dr}

End;

Var Primul, Ultim, Elem, Prec, Nou : Adr;

Opera•ia de ad•ugare într-o list• dublu înl•n•uit• se poate realiza astfel :

O procedur• Pascal care realizeaz• inserarea elementului Nou în fa•a

elementului Elem este urm•toarea:

Procedure Inserare(Var Nou,Elem: Adr);

Begin

(Elem^.leg_st)^.Leg_dr:=Nou;

Nou^ .Leg_St:=Elem^.Leg_St;

Nou^ .Leg_Dr:=Elem;

Elem^.Leg_St:=Nou;

End;

Opera•ia de •tergere a elementului Elem dintr-o list• dublu înl•n•uit• se

poate schi•a astfel:

O procedur• Pascal corespunzatoare acestei opera•ii este urm•toarea:


Nil NilNou

LegSt. Inf. LegDr.

Primul UltimPrec Elem


Nil Nil

Primul UltimElem

123

Procedure Stergere(Var Elem : Adr);

Begin

(Elem^.Leg_St)^.Leg_Dr:=Elem^.Leg_Dr;

(Elem^.Leg_Dr)^.Leg_St:=Elem^.Leg_St;

Dispose (Elem);

End;

În exemplul urm•tor se poate urm•ri generarea unei liste dublu înl•n•uite

urmate de parcurgerea acesteia în ambele sensuri:

Program Liste_dublu_inlantuite;

Type Tip_Cheie = Integer;

Tip_Date = String[20];

Tip_Info = Record Cheie : Tip_Cheie; Date : Tip_Date End;

Adr = ^Tip_Elem;

Tip_Elem = Record

Inf : Tip_Info; Leg_St, Leg_Dr : Adr

End;

Directie = (Inainte,Inapoi);

Var Prim : Adr; { Adresa primului element }

Ultim : Adr; { Adresa ultimului element }

Disc : Char; { Tipul adaugarii }

Procedure Citesc (Var Element:Adr); {Citeste informatia}

Begin {dintr-un nod}

New (Element);

Write (’ ............... Cheie, Date : ’);

With Element^, Inf Do Readln (Cheie,Date)

End;

Procedure Generare (Disc:Char; Var Primul,Ultim:Adr); {Creaza o lista dublu}

{ înl•n•uit• }

Var Nou : Adr;

Rasp : Char;

Procedure Adaug_in_coada;

124

Begin

Nou^.Leg_Dr:=Nil; Nou^.Leg_St:=Ultim;

If Primul = Nil Then Primul := Nou

Else Ultim^.Leg_Dr := Nou;

Ultim:=Nou

End;

Procedure Adaug_in_cap;

Begin

Nou^.Leg_Dr := Prim; Nou^.Leg_St := Nil;

If Prim = Nil Then Ultim := Nou Else Prim^.Leg_St := Nou;

Prim := Nou

End;

Procedure Inserare_ord; Var Prec,Elem : Adr;

Begin Elem:=Primul;

While (Elem<>Nil) and (Elem^.Inf.Cheie < Nou^.Inf.Cheie)

Do Elem := Elem^.Leg_dr;

If Elem=Nil Then Adaug_in_coada Else

If Elem=Primul Then Adaug_in_cap Else Begin

Prec := Elem^.Leg_St;

Nou^.Leg_St := Prec; Nou^.Leg_Dr := Elem;

Elem^.Leg_St:= Nou;

Prec^.Leg_Dr:= Nou

End {If}

End {inserare};

Begin {Generare}

Primul:=Nil; Ultim:=Nil;

Repeat

Repeat

Write (’ Adaugati (D,N) : ’);

Readln (Rasp); Rasp:=Upcase(Rasp);

until Rasp In [’D’,’N’];

If Rasp = ’D’ Then Begin

New(Nou); Citesc (Nou);

125

Case Disc of

’F’ : Adaug_in_coada; ’L’ : Adaug_in_cap; ’O’ : Inserare_ord

End {Case}

End {If}

until Rasp = ’N’

End;

Procedure Parcurgere (Elem:Adr; Sens:Directie);

Begin


With Elem^.Inf do Writeln (Cheie:5,Date);

If Sens=Inainte Then Elem:=Elem^.Leg_Dr Else Elem:=Elem^.Leg_St

End {While}

End;

Begin

Repeat

Writeln (’ Ce disciplina doriti la ad•ugare ? ’);

Writeln (’ F = in coada listei (FIFO) ’);

Writeln (’ L = in capul listei (LIFO) ’);

Writeln (’ O = lista ordonata ’);

Write (’ Optiune : ’);

Readln (Disc); Disc:=Upcase(Disc)

Until Disc In [’F’,’L’,’O’];

Generare (Disc, Prim, Ultim ); { Creerea listei }

Writeln(’Lista inainte’);

Parcurgere (Prim,Inainte); { Traversare inainte }

Writeln(’Lista inapoi’);

Parcurgere (Ultim ,Inapoi ); { Traversare inapoi }

Readln

End.

126

13.3. Arbori binari.

O colec•ie de elemente are o structur• de tip arborescent dac• elementele

componente sunt în rela•ie unu la mai_multe, adic• un element este în rela•ie cu

mai multe elemente. Elementele unei astfel de structuri se numesc noduri sau

vârfuri. Ele au un unic predecesor numit p•rinte dar mai mul•i succesori numi•i

fii. Un arbore este format din mul•imea nodurilor •i leg•turile dintre acestea. Un

nod al unui arbore poate fi r•d•cin• (dac• nu are predecesor) sau poate fi nod

intern (dac• are un singur predecesor •i mai mul•i succesori) sau poate fi nod

terminal sau frunz• (dac• nu are nici un succesor). Un arbore particular este

arborele binar pentru care rela•ia dintre elemente este de tip unu la dou•, adic•

un element poate avea maxim doi succesori.

Un arbore binar poate fi definit recursiv ca fiind o mul•ime (colec•ie) de

noduri vid• sau format• din nodul R•d•cin•, Subarbore_stâng •i

Subarbore_drept.

La reprezentarea în memorie a unui arbore binar, pe lânga informa•ia

propriu-zis• se vor memora în fiecare nod •i adresele de legatur• spre nodurile

succesoare în felul urm•tor:

R•d.

Sub-arborestâng

Sub- arbore

drept

0

1 2

11 21 22

111 211112 212 222

Nil

Nil

Nil Nil

127

Deci o variabil• de tip arbore va avea tipul Arbore definit astfel:

Type Arbore = ^Tip_Elem;

Tip_Elem = Record

Info : Tip_Info;

As, Ad : Adr

End;

Aici Tip_Info este tipul informa•iei pastrat• într-un nod, putând fi orice tip

Pascal definit anterior.

Prin traversarea unui arbore binar vom în•elege parcurgerea tuturor

vârfurilor arborelui, trecând o singur• dat• prin fiecare nod.

În func•ie de ordinea (disciplina) de vizitare a nodurilor unui arbore binar,

traversarea poate fi în preordine, în inordine sau în postordine.

Traversarea în preordine este aceea în care se parcurge mai întâi nodul

r•d•cin•, apoi subarborele stâng •i dup• aceea subarborele drept. Deci se parcurge

arborele în ordinea (R•d•cin•, Subarbore_stâng, Subarbore_drept). Evident,

defini•ia este recursiv•, parcurgerea unui subarbore fiind facut• dupa acea•i

regul•, deci începând cu r•d•cina. O procedur• Pascal corespunzatoare se d• în

continuare.

Procedure Preordine (R:Arbore);

Begin

If R<>Nil Then With R^ do Begin

Prelucrare (Info);

Preordine (As);

Preordine (Ad) End {if}

End;

Procedura Prelucrare (Nod) poate reprezenta orice subalgoritm de

prelucrare a informa•iei din nodul specificat (de exemplu tip•rirea informa•ilor).

128

Traversarea în inordine este aceea în care se parcurge mai întâi

subarborele stâng, apoi nodul r•d•cin• •i dup• aceea subarborele drept. Deci se

parcurge arborele în ordinea (Subarbore_stâng, R•d•cin•, Subarbore_drept). În

continuare este prezentat• o procedur• Pascal de traversarea în inordine :

Procedure Inordine (R:Arbore);

Begin

If R<>Nil Then With R^ do Begin

Inordine (As);

Prelucrare (Info);

Inordine (Ad) End {if}

End;

Traversarea în postordine este aceea în care se parcurge mai întâi

subarborele stâng, apoi subarborele drept •i dup• aceea nodul r•d•cin•. Deci se

parcurge arborele în ordinea (Subarbore_stâng, Subarbore_drept, R•d•cin•).

Procedura Pascal corespunz•toare este urm•toarea :

Procedure Postordine (R:Arbore);

Begin

If R<>Nil Then With R^ Do Begin

Postordine (As);

Postordine (Ad);

Prelucrare (R) End {if}

End;

Pentru arborele al•turat, ordinea nodurilor corespunz•toare cele trei tipuri

de travers•ri este urm•toarea :

a) în preordine : 16,7,5,2,10,9,13,20,19,25,21,29;

b) în inordine : 2,5,7,9,10,13,16,19,20,21,25,29;

c) în postordine :2,5,9,13,10,7,19,21,29,25,20,16.

16

207

19 25105

2 9 13 21 29

129

În exemplul urm•tor vom genera un arbore binar prin ad•ug•ri succesive

de noduri dup• um•toarea regul•: elementele cu cheie mai mare decât cheia

informa•iei din nodul r•d•cin•, se adaug• în subarborele stâng iar cele cu cheie

mai mic• în subarborele drept. Prin traversarea în inordine a arborelui astfel

construit vom ob•ine lista nodurilor în ordine descrescatoare a cheilor.

Informa•ia pastrat• într-un nod se refer• la un student •i con•ine media

acelui student (aceasta fiind cheia dup• care se face ordonarea) •i numele

studentului.

Program Arbore_Binar_Ordonat; { Prgramul arbore_Binar }

Type

Tip_Info = Record

Medie : real ;

nume : string[20]

End;

Adr = ^Tip_Elem;

Tip_Elem = Record

Info : Tip_Info;

As, Ad : Adr

End;

Var Arb:Adr;

Procedure Citesc (Var InfNod:Tip_Info);

Begin

Write (’ Medie(>0), Nume_Student : ’);

With InfNod Do Readln (Medie,nume)

End;

Procedure Print (InfNod:Tip_Info);

Begin

With InfNod do

Writeln ( Medie:6:2,’ - ’,nume)

End;

130

Procedure Creare (Var Arb:Adr);

Var InfNod: Tip_Info;

Procedure Adaug (Var Sarb:Adr);

Begin

If Sarb<>Nil

Then With Sarb^ Do

If InfNod.medie>Info.medie Then Adaug(As) Else Adaug(Ad)

Else Begin

New (Sarb); Sarb^.Info:=InfNod;

Sarb^.As:=Nil; Sarb^.Ad:=Nil End {if}

End;

Begin

Arb:=Nil;

Repeat

Citesc (InfNod);

If InfNod.medie > 10 Then Writeln(’medie>10?’) Else

If InfNod.medie > 0 Then Adaug(Arb)

Until InfNod.medie <= 0

End;

Procedure Traversare_Inordine (Sarb:Adr);

Begin

If Sarb <> Nil Then With Sarb^ Do Begin

Traversare_Inordine (As);

Print (Info);

Traversare_Inordine (Ad) End

End;

Begin

Writeln(’Se citesc medii •i nume pana media=0’);

Creare (Arb);

Writeln(’Elementele arborelui (lista studentilor dupa medie) : ’);

Traversare_Inordine (Arb);

Readln

End.

131

Urm•torul program va construi un arbore genealogic ascendent (pentru

fiecare nod se re•in informa•ii despre o persoan• •i leg•turile de tip mam• •i tat•

spre nodurile respective) iar apoi se vor depune aceste informa•ii într-o list•

ordonat• dup• anul na•terii. La parcurgerea acestei liste, persoanele vor fi tiparite

în ordinea vârstei.

Program Arbore_Genealogic; {Program pentru str•mo•ii unei persoane }

Type Tip_Info = Record

An_Nastere : Integer;

Nume : String[20];

End;

Adra= ^Tip_Elem_A;

Tip_Elem_A = Record Info : Tip_Info; As, Ad : Adra End;

Adrl= ^Tip_Elem_L;

Tip_Elem_L = Record Info : Tip_Info; Leg : Adrl End;

Var Arb : Adra; { Adresa r•d•cinii arbvorelui }

Lista : Adrl; { Adresa primului element }

Procedure Citesc (Var Pers:Tip_Info); {Citeste in Pers}

Begin {informatiile despre o persoana}

Write (’ Anul_Nasterii, Nume_Prenume : ’);

With Pers do Readln (An_Nastere,nume)

End;

Procedure Adaug_Arbore (Var Sarb:Adra); {Depune la adresa Sarb, }

Var Pers : Tip_Info; { inf. pt.o persoana }

Begin Citesc (Pers); {si decide, dac• e nod terminal sau continua }

If Pers.An_nastere > 0

Then Begin

New (Sarb); Sarb^ .Info:=Pers;

Write (’ Mama ’,Pers.nume,’ : ’); Adaug_Arbore (Sarb^ .As);

Write (’ Tata ’,Pers.nume,’ : ’); Adaug_Arbore (Sarb^ .Ad) End {Then}

Else Sarb:=Nil

End;

132

Procedure Print (Pers:Tip_Info); {Tipareste informatiile}

Begin {despre persoana Pers}

Writeln (Pers.An_nastere:6, Pers.nume)

End;

Procedure Inserare_Lista_Ordonata(Pers:Tip_Info; Var Lista:Adrl); {Insereaza }

Var E, Prec, Nou : Adrl; { un nou element }

Begin {pt. Pers, in Lista ordonata }

E:=Lista; {Se cauta locul inserarii}

While (E<>Nil) and (E^.Info.An_nastere < Pers.An_nastere) do Begin

Prec := E; E := E^.Leg

End;{While}

New (Nou); Nou^.Info:= Pers; Nou^.Leg := E; {Se creaza noul element }

If E = Lista Then Lista := Nou { •i se depune in lista }

Else Prec^.Leg := Nou

End;

Procedure Arbore_Lista (Sarb:Adra: Var L: Adrl); {Creaza lista L prin }

Begin { Traversare in Inordine}

If Sarb<>Nil Then With Sarb^ do Begin

Inserare_Lista_Ordonata (Info, L);

Arbore_Lista (As); Arbore_Lista (Ad) End {If}

End;

Procedure Parcurgere (Elem:Adrl);

Begin


Print(Elem^.Info); Elem:=Elem^.Leg End {While}

End;


Write (’ Persoana: ’); Adaug_Arbore (Arb); Writeln;

Lista:=Nil; Arbore_Lista(Arb,Lista);

Writeln(’Persoanele in ordine cronologica:’);

Parcurgere (Lista); Readln; { Tiparirea listei }

End.

13 tipul referinta( structuri de date dinamice )

Documents