Variabile statice şi variabile dinamice.
Variabilele pot fi statice sau dinamice. Cele statice au o zonă de memorie bine definită. Structura, locul, tipul acestei zone nu poate fi schimbată în procesul execuţiei programului. Accesul la variabilele statice se face direct, după nume. Structurile statice de date au un număr fix de elemente, care nu poate fi modificat. Alocarea memoriei se face într-un spaţiu strict determinat al memoriei, care permite adresarea directă.
O altă categorie de variabile, accesibile în limbajul Pascal este cea dinamică. Pentru acest tip de variabile poate fi modificat volumul de memorie rezervat, ceea ce face mai flexibilă alocarea memoriei în procesul de lucru al programului. Structurile dinamice pot acumula elemente în procesul de funcţionare al programului, sau pot lichida elementele ce au devenit neutilizabile. Accesul la aceste variabile şi declararea lor se face în mod diferit de cel al variabilelor statice. Accesarea (definirea) este indirectă, prin intermediul unui tip mediator de variabile – tipul referinţă.
Variabile de tip referinţă conţin referiri (adresări indirecte) la variabilele dinamice. Referirea se realizează prin memorarea în variabila referinţă a adresei unde e stocată variabila dinamică.
Pentru variabilele tip referinţă se alocă un spaţiu de memorie de 4 octeţi, care conţin adresa variabilei dinamice. Memoria pentru variabilele dinamice se alocă dintr-o zonă specială, care foloseşte adresarea indirectă, numită heap. Această zonă este diferită de zona pentru variabilele statice.
Variabilele dinamice ocupă un spaţiu de memorie în corespundere cu tipul lor: Integer, real, string etc.
Definirea tipului referinţă.
Pentru a defini un tip referinţă vom folosi secţiunea Type în blocul de declarare a variabilelor. Procedura de definire este următoarea:
type <tip_referinţă> = ^<tip_variabilă_dinamică>;
^ - se citeşte ca “pointer la…” sau “adresare la…“
Mulţimea valorilor variabilelor tip referinţă este formată dintr-o mulţime de adrese, fiecare din ele identificînd o variabilă dinamică. Mulţimea de valori mai e completată prin valoarea Nil, care nu conţine nici o adresă.
Schema de lucru a variabilelor referinţă:
Exemplu:
type pointReal = ^Real;
var ar, br, cr : pointReal;
Exemplu
type pointReal = ^Real;
var ar, br, cr : pointReal;
Begin
New (ar); New (br); New (cr);
Readln (ar^, br^);
cr^ := ar^+ br^;
Writeln (cr^);
End.
Variabila tip_referinţă păstrează adresa adresei variabilei dinamice. Pentru a putea utiliza variabilele dinamice în program ele trebuie iniţializate prin procedura NEW.
Ca variabilele dinamice pot fi declarate şi structuri de tip Record, iar tipul lor poate fi definit (declarat) mai tîrziu, dat în acceaşi secţiune de declaraţii type:
type num_complex = ^complex;
complex = record
re,
im : Real
end;
var
num1, num2 : num_complex;
num3 : ^complex;
simbol : ^char;
Liste unidirectionale
Logica creării unei liste (este cea mai simplă structură) e următoarea: pentru fiecare element al listei vom avea nevoie de spaţiu pentru el însuşi şi de spaţiu pentru adresa elementului următor al listei.
Exemplu:
type lista = ^element;
element = record
a: integer,
urmator : lista
end;
Var
lis : lista;
Schema creării listei:
acesta este lis^ acesta este lis^.urmator
a urmator a urmator
un articol
(primul din lista lis)
Aşa dar, memorarea şi atribuirea valorilor se realizează după schema:
a. declararea variavilei dinamice
b. alocarea memoriei pentru variabila dinamică prin procedura
New (nume variabilă dinamică)
c. atribuirea valorii numerice prin unul din procedeele standard.
Eliberarea memoriei ocupate de variabila dinamică se va realiza prin procedura
Dispose (nume variabilă dinamică)
type lista = ^element;
element = record
a: integer; {elementul propriu zis}
urmator : lista {adresa următorului element al listei}
end;
Var
lisinit, liscurent : lista;
raspuns : char;
begin
lisinit := Nil; {lista nu contine nici un element, ea se initializeaza}
repeat
begin
New(liscurent); {un nou element in lista }
Writeln ('Elementul curent');
readln(liscurent^.a); {dam valori elemetului listei}
liscurent^.urmator := lisinit;
{indicam urmatoarea adresă, acea a primului element din listă, transformîndu-l în al doilea. De fapt plasăm elementul la începutul listei, împingîndu-le pe toate celelalte spre dreapta}
lisinit:=liscurent; {Lista nou formată o memorăm în variabila listinit}
writeln ('Continuati? [D - Da, N / Nu]'); readln(raspuns);
end;
until (raspuns='N') or (raspuns='n');
while liscurent <> Nil do
begin
writeln (liscurent^.a);
liscurent:= liscurent^.urmator;
end;
end.
Arbori
Numim arbori,un graf conex fara cicluri
TEOREMA:
1.Un arbore cu n varfuri are n-1 muchii;
2.Urmatoarele afirmatii sunt echivalente:
- G este arbore
- G este un graf conex minimal cu aceasta proprietate,adica prin eliminarea unei muchii se obtine un graf neconex;
- G este un graf fara cicluri maximal cu aceasta proprietate,adica prin adaugarea unei muchii se obtine cel putin un ciclu;
Vor aparea urmatoarele notiuni:
- radacina(varful arborelui) este nodul in care nu intra niciun arc;
- parintii(predecesorii) reprezinta nodurile din care ies arce;
- fiii (succesorii) sunt nodurile legate de parinti;
- frunzele(noduri terminale) sunt nodurile situate pe ultimul nivel sau care nu au descendenti;
- nivelele arborelui sunt stratificari(trepte) ale arborelui stiind ca radacina se situeaza pe nivelul 1;
- inaltimea arborelui reprezinta lungimea celui mai lung lant ce pleaca din radacina si ajunge in frunze;
Reprezentarea arborelui
Se va folosi un vector “tata” in care in tata de i se va retine parintele nodului i.
Pentru radacina se retine 0.
Descendentii directi ai unui nod reprezinta fiii nodului situati pe nivelul urmator.
Toti descendentii unui nod reprezinta toti fiii nodului respective pana la frunza.
Arborele binar reprezinta arboreal pentru care toate nodurile cu exceptia frunzelor au cel mult 2 descendenti.
Reprezentarea arborilor binari
1.Se specifica radacina si se vor folosi 2 vectori s si d in care se va specifica in s[i] sid[i],nodul successor stang,respectiv nodul succesor drept.
2.Se vor folosi 2 vectori tata[i] si p[i]. In tata[i] se va retine tatal nodului i, iar inp[i] se va retine tipul succesorului: - 0 pentru radacina;
- -1 pentru subarborele stang
- 1 pentru subarborele drept
