Alocarea dinamica, Notiuni generale, Lista liniara dublu inlantuita



Alocarea dinamica


4.1)Notiuni generale


Din punctul  de vedere al unui programator,memoria calculatorului se prezinta ca o succesiune de octeti,fiecare octet avand o adresa binara bine stabilita.Acesti octeti sunt identificati prin numere cuprinse intre 0 si n-1 .Convenim sa numim adresa numarul de ordine al unui octet.Un octet este format din 8 biti.Fiecare bit poate memora fie cifra binara 1, fie cifra binara 0.Diversele tipuri de date cunoscute pana acum(INTEGER,REAL) ocupa 2 sau mai multi octeti consecutivi.Pentru fiecare tip de data cunoscut exista o anumita logica potrivit careia se face memorarea efectiva a continutului.De exemplu, pentru tipul INTEGER,memorarea se face in COD COMPLEMENTAR.Nu ne propunem sa prezentam modul de reprezentare a datelor.Ne marginim numai sa atragem atentia ca o variabila folosita de noi in program are un anumit nume(simbolic),o valoare si o adresa la care o gasim memorata(adresa primului octet din cei p octeti consecutivi ocupati de variabila).In general,in limbajele evoluate nu este necesar ca programatorul sa cunoasca adresa la care se gasesc variabilele cu care lucreaza.



Se cunosc doua forme de alocare a memoriei de catre programator in cadrul limbajului PASCAL:statica si dinamica.

Utilizand forma de alocare statica ,variabilele se declara utilizand cuvantul cheie VAR la inceputul programului.

Utilizand forma de alocare dinamica,in timpul rularii programului,in functie de necesitati,se aloca memorie suplimentara sau se renunta la ea.

Pentru alocarea dinamica utilizam tipul de date referinta.Se considera secventa de program:


type ref=^inr;

inr=record

nr:integer;

adrurm:ref;

end;

var c:ref;


Aici variabila c este o variabila de tip referinta.Ea retine adrese de inregistrari.La randul ei,o inregistrare are doua campuri:nr,care retine un numar intreg(informatia utila) si adrurm(adresa urmatoare) care retine adresa unei alte inregistrari.

Procedura NEW(c) rezerva spatiu(un numar de octeti consecutivi) pentru o inregistrare,adresa primului octet fiind depusa in variabila c.

Presupunem ca variabila c contine adresa unei inregistrari.Procedura DISPOSE(c) elibereaza spatiul de memorie afectat acelei inregistrari care avea adresa in c.Cuvantul cheie NIL  are semnificatia 'nici o adresa'.


Observatii:

1)c se refera la adresa care se gaseste in variabila c;

2)c^.nr se refera la campul numeric al inregistrarii care are adresa                       memorata in variabila c;

3)c^.adrurm semnifica adresa de inregistrare care se gaseste memorata in cadrul inregistrarii care are adresa c;

4)c^.adrurm^.nr semnifica variabila nr care se gaseste in inregistrarea care are adresa plasata  in campul adrurm al inregistrarii cu adresa c.


Observatie foarte importanta:spatiul necesar variabilelor alocate dinamic se rezerva intr-o zona de memori,special destinata,numita HEAP(pentru PC compatibila IBM)




4.2) Lista liniara dublu inlantuita


O lista dublu inlantuita este o structura de date de forma:




Operatiile pe care le facem cu o lista dublu inlantuita sunt urmatoarele:

creare

adaugare la dreapata

adaugare la stanga

adaugare in interiorul listei

stergere din interiorul listei

stergere la stanga listei

stergere la dreapta listei

listare de la stanga la dreapta

listare de la dreapta la stanga

4.2.1) Creare

O lista dublu inlantuita se creeaza cu o singura inregistrare .Pentru a ajunge la numarul de inregistrari dorit,utilizam proceduri de adaugare la stanga sau la dreapta.Putem realiza o procedura numita creare care sa realizeze urmatoarele:

citirea informatiei utile

alocarea de spatiu pentru inregistrare

completarea inregistrarii cu informatia utila

completarea adreselor de legatura la stanga si la dreapta cu NIL

variabilele tip referinta b si s vor capata valoarea adresei acestei prime inregistrari(b semnifica adresa inregistrarii cea mai din stanga,s adresa ultimei inregistrari din dreapta);


procedure creare(var b,s :ref);

begin

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

new(b);b^.nr:=n;

b^.as:=nil;b^.ad:=nil;

s:=b;

end;

Procedura se va apela creare(b,s)


4.2.2) Adaugarea la dreapta


Aceasta operatie este realizata de procedura adrr.Pentru adaugarea unei inregistrari se realizeaza urmatoarele operatii:

citirea informatiei utile

alocarea spatiului pentru inregistrare

completarea adresei la dreapta cu NIL

completarea adresei din stanga cu adresa celei mai din dreapta inregistrari(retinute in variabila s)

modificarea campului de adresa la dreapta a inregistrarii din s cu adresa noii inregistrari

s va lua valoarea noii inregistrari,deoarece acesta va fi cea mai din dreapta.


procedure addr( var s:ref);

var d:ref;

begin

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

new(d);d^.nr:=n;

d^.as:=s;d^.ad:=nil;

s^.ad:=d;s:=d;

end;

Procedura se va apela addr(s)


4.2.3) Adaugare in interiorul listei


Aceasta operatie este realizata de procedura includ,care realizeaza urmatoarele operatii:

parcurge lista de la stanga la dreapta cautand inregistrarea cu informatia utila m,in dreapta careia urmeaza sa introducem noua inregistrare

citeste informatia utila

aloca spatiu pentru noua inregistrare

completeaza informatia utila

adresa stanga a noii inregistrari ia valoarea adresei inregistrarii de informatie utila m

adresa stanga a inregistrarii care urma la acest moment inregistrarii cu informatia utila m  capata valoarea adresei noii inregistrari


procedure includ(m:integer;b:ref);

var d,e:ref;

begin

d:=b;

while d^.nr<>m do d:=d^.ad;

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

new(e);

e^.nr:=n;

e^.as:=d;

d^.ad^.as:=e;

e^.ad:=d^.ad;

d^.ad:=e;

end;

Procedura se va apela includ(m,b)





4.2.4) Stergerea in interiorul listei


Aceasta operatie este realizata de procedura sterg.Operatiile efectuate de aceasta procedura sunt urmatoarele:

se parcurge lista de la stanga la dreapta pentru a ne pozitiona pe inregistrarea care urmeaza a fi stearsa;

campul de adresa dreapta al inregistrarii care o precede pe aceasta va lua valoarea campului de adresa dreapta al inregistrarii care va fi stearsa

campul de adresa stanga al inregistrarii care urmeaza inregistrarii care va fi stearsa va lua valoarea campului de adresa stanga al inregistrarii pe care o stergem;

se elibereaza spatiul de memorie rezervat inregistrarii care se sterge;


procedure sterg(m:integer;b:ref);

var d:ref;

begin

d:=b;

while d^.nr<>m do d:=d^.ad;

d^.as^.ad:=d^.ad;

d^.ad^.as:=d^.as;

disose(d);

end;


Procedura se va apela sterg(m,b)


4.2.5) Listare de la stanga la dreapta


Aceasta operatie este realizata de procedura listare,procedura care realizeaza urmatoarele operatii:

porneste din stanga listei

atat timp cat nu s-a ajuns la capatul din dreapta al listei,se tipareste informatia utila si se trece la inregistrarea urmatoare;


procedure listare(b:ref);

var d:ref;

begin

d:=b;

while d<>nil do

begin

writeln(d^.nr);

d:=d^.ad;

end;

end;

Procedura se apeleaza listare(b);