Structuri dinamice de date (alocare dinamica)

Structuri dinamice de date (alocare dinamica)

In Pascal exista 2 modalitati de alocare a memoriei: statica si dinamica.O variabila statica este declarata in sectiunea VAR a unui bloc printr-un nume si va exista(deci va ocupa memoria alocata ei) atata timp cat blocul este activ.

Variabilele dinamice nu sunt declarate intr-o sectiune VAR deci nu se pot identifica prin nume.Variabilele dinamice se aloca intr-o zona de memorie speciala(HEAP) si se distrug la cererea programatorului.Deoarece nu au nume,variabilele dinamice sunt referite prin intermediul variabilelor reper(referinta).Variabilele reper sunt alocate static si au ca valori adrese ale unor variabile dinamice.

1 Tipul reper(referinta)-are urmatoarea diaf. de sintaxa:

identificator de tip

tip

reper

-unde identificator de tip reprezinta numele tipului variabilelor dinamice pe care le refera variabilele de tipul reper respectiv.

Valorile unui tip reper reprezinta fie adresele din HEAP ale unor variabile dinamice de tipul specificat in definitia tipului reper respectiv,fie valoarea constantei nil.Diadrama de sintaxa a variabilei dinamice este:

identificator de variabila de tip reper

Variabilele de tip reper ,fiind statice,se declara in sectiunea VAR.

Exemplu:

type tip_var_dinamica=..

reper=^tip_var_dinamica;

var p:reper;

indica    variabila dinamica

adrasa

(refera) p^ de tip tip_var_dinamica

2 Operatii cu variabile de tip reper

1)Atribuirea:

O variabila de tip reper primeste valoarea unei alte variabile(functii) de acelasi tip reper cu ea sau este initializata cu constanta nil.

2)Comparatia:

Variabilele reper pot sa apara in expresii relationale,

singurii operatori relationali admisi fiind '=' si '< >'.

3)Variabilele reper pot fi parametri ai unor proceduri sau functii:

O variabila de tip reper se poate initializa fie prin atribuire fie cu procedura NEW din unit-ul SYSTEM.Procedura se apeleaza prin comanda NEW(p),unde p este o variabila de tip reper.

Eliberarea zonei de memorie ocupata de o variabila dinamica se realizeaza cu procedura DISPOSE din unit-ul SYSTEM.Apelul acesteia are forma DISPOSE(P),unde p este o variabila de tip reper.

3 Structuri de date inlantuite(structuri de date dinamice):

Structurile dinamice sunt structuri de date ale caror numar de componente se modifica in timpul executiei programului.

Alocarea dinamica evita dezavantajele alocarii statice:

-spatiul alocat structurii poate fi insuficient ;

-spatiul alocat structurii poate fi mult prea mare;

Elementele structurii dinamice sunt inlantuite,fiecare componenta cuprinzand,pe langa informatia propriu-zisa si informatia de legatura,prin care se realizeaza inlantuirea(vezi figura de mai jos):

informatia utila informatia utila

un element al unei structuri dinamice

Exemple de structuri dinamice:lista liniara,arbore retea.

3.1 Liste:

O lista liniara simplu inlantuita este o structura de forma:

adr1    adr2 adr n

unde:

-adr 1,adr 2,,adr n reprezinta adresele de memorie ale celor n inregistrari;

-inf 1,inf 2,,inf n reprezinta informatiile utile din cele n inregistrari;

Operatiile elementare intr-o lista simplu inlantuite sunt:crearea,inserarea,cautarea,

eliminarea unui element.

Aceste operatii vor fi definite in urmatorul program prin procedurile corespunzatoare:

type reper=^nod;

nod=record

inf:integer;

leg:reper;

end;

var cap,curent,ultim:reper;

n,i:integer;

procedure creare;

begin

write('Introduceti nr.de noduri n=');readln(n);

new(cap);readln(cap^.inf);

ultim:=cap;

for i:=1 to n do

begin

new(curent);

readln(curent^.inf);   

ultim^.leg:=curent;   

ultim:=curent;

end;

curent^.leg:=nil;

end;

procedure ins_dupa;

begin

write('Introduceti inf. nodului dupa care se face inserarea:');

readln(i);

write('Introduceti inf. nodului pe care-l inserez:');

readln(n);

curent:=cap;

while curent^.inf< >i do curent:=curent^.leg;   

new(ultim);

ultim^.inf:=n;

ultim^.leg:=curent^.leg;

curent^.leg:=ultim;

end;

procedure stergere;

begin

write('Introduceti informatia nodului pe care-l stergeti:');

readln(i);

if cap^.inf=i then

begin

curent:=cap;

cap:=cap^.leg;

dispose(curent);

end

else begin

curent:=cap;

while curent^.inf< >i do

begin

ultim:=curent;

curent:=curent^.leg;

end;

ultim^.leg:=curent^.leg;

dispose(curent)

end;

end;

3.2 Liste liniare simplu inlantuite:

Tipuri speciale:stiva,coada,lista dublu inlantuita,liste circulare.

Stiva(Stack)-este o lista liniara de tip special,in care adaugarea sau scoaterea unui element se face la un singur capat al listei,numit varful stivei.(Aceste structuri se mai numesc de tip LIFO).Elementul introdus primul in lista poarta numele de baza stivei.Informatia de legatura a fiecarui element din stiva reprezinta adresa elementului pus anterior in stiva,exceptie facand baza,a carei inf. de legatura este nil.

varf

Stiva

(STACK)

baza

Operatii care se aplica stivelor:

Adaugare-(procedura push)

a)-se aloca meorie pt. noul nod;

-se incarca campul cu inf. utila;

-se initializeaza zona de legatura cu adresa nodului care a fost anterior in varful stivei,adresa pastrata in variabila varf;

b)-se reinitializeaza var. varf cu adresa noului element alocat;

2)Traversarea:(parcurgerea) nodurilor stivei(procedura LIST)

Ordinea de traversare (prelucrare) va fi inversa celei in care acestea s-au pus in stiva.

3)Stergerea unui nod din varful stivei(procedura POP)

-stergerea se poate realiza daca stiva este nevida.In acest caz:

a)se salveaza in p adresa varfului stivei;

b)adresa elementului urmator celei din varful stivei devine adresa noului varf al stivei;

c)se elibereaza memorie ocupata de varful anterior al stivei;

Coada-reprezinta o alta categorie speciala de lista liniara,in care elementele se adauga la un capat(sfarsit) si se sterg (suprima) la celalalt capat(inceput).Coada se mai numeste lista de tip FIFO.Nodurile unei structuri dinamice de tip coada sunt structurate ca in figura:

inf4 NIL

inf3

inf2

inf1

prim ultim

Operatii ce se aplica cozilor

I. Adaugarea unui element-dupa ultimul din coada:

prim ultim

Se observa ca adaugarea unui nou nod se face la sfarsitul cozii.

(1)-se aloca memorie pt. noul nod si se incarca campul cu inf. utila;

(2)-se initializeaza campul de legatura a ultimului nod(ultim) cu adresa noului nod;

(3)-se reinitializeaza variabila ultim cu adresa noului nod alocat;

II.Stergerea primului element-din coada

prim ultim

(1)-se salveaza in p adresa primului nod din coada(prim);

(2)-adresa nodului urmator celui din capul(inceputul) cozii devine adresa noului cap(prim) al cozii;

(3)-se elibereaza memoria ocupata de capul(prim) anterior al cozii;

Observatie Coada este vida cand variabila de tip reper prim este nil.

Lista dublu inlantuita-este un tip special de lista,in care informatia de legatura a fiecarui element cuprinde atat adresa elementului precedent in lista,cat si adresa elementului urmator.

inf3 NIL errrtuytrrtpstubpogier'pferyqwrtyreqynnnnnnnNNILNIL

inf2

inf1 NIL

prim ultim

Operatiile-posibile cu o lista dublu inlantuita sunt:

1)adaugarea unui element listei,intr-o pozitie oarecare;

2)stergerea unui element(nod) oarecare al listei;

3)traversarea(parcurgerea) listei folosind una din cele doua adrese de inlantuire;

4)cautarea unui anumit element(nod) al listei;

Observatie:Cele patru operatii anterior amintite includ pe langa operatiile de la lista liniara simplu inlantuita si gestionarea celei de-a doua adrese;

Lista circulara:este o lista liniara simplu inlantuita unde informatia de legatura a ultimului nod face referire la adresa primului nod.

inf n

inf2

inf1

Observatie:Toate operatiile specifice listei circulare sunt similare cu cele de la lista liniara simplu inlantuita.

11. Metoda Greedy

11.1 Prezentare generala:

Metoda Greedy(metoda optimului local) se utilizeaza in cazul in care se face construirea unei solutii prin parcurgerea in etape a unor solutii partiale.La fiecare pas se alege o solutie,pe baza careia se va face cautarea in pasul urmator.Metoda pleaca de la ideea ca,daca in fiecare pas se alege o solutie optima pentru pasul respectiv exista,o buna sansa de obtinere a unei solutii optime in final.O astfel de abordare conduce,eventual,la obtinerea rapida a unei soluti,dar pe aceasta cale nu se asigura,pentru orice problema,optimalitatea globala a solutiei.De asemenea,exista probleme pentru care o astfel de abordare poate sa nu conduca la o solutie,cu toate ca aceasta exista.

11.2 Probleme:

Problema rucsacului:Se da un rucsac de capacitate M si un numar de n obiecte,specificandu-se masele obiectelor si profiturile ce se obtin prin introducerea lor in rucsac prin vectorii m=(m1,m2,,mn),respectiv p=(p1,p2,,pn).Se cere un program care sa determine varianta de introducere a obiectelor in rucsac in urma careia se obtine un profit maxim.

Solutia:se va da sub forma unui vector X definit astfel:

x(i)= 1,daca obiectul i este introdus in rucsac

0,daca obiectul i nu este introdus in rucsac

Se va considera ca 0 x(i) 1;daca o fractie x(i) a obiectului i este plasata in rucsac se obtine un profit p(i) x(i).

Problema poate fi formalizata astfel:

max S pi xi , cu conditia S mi xi M

1 i n    1 i n

Daca suma maselor este mai mare sau egala cu M,in mod clar xi i n) este solutia optima.Presupunem in continuare ca mi<M;conditia pentru solutia optima se rescrie atunci S mi xi=M.

1 i n

Problema este de a se introduce un criteriu potrivit caruia alegerea obiectului i este mai avantajoasa decat alegerea obiectului j.

Dam mai jos trei variante posibile de criterii de optimizare:

1)pi>pj

2)mi<mj

3)pi/mi>pj/mj

Evident criteriul 3 este mai eficient.Vom ordona obiectele astfel incat

pi/mi pi+1/mi+1.In acest caz procedura de rezolvare este:

procedure Greedy(p,m,M,x,n)

x 0

Cn    M

i i+1

While (mi <=Cn) and (i<=n) do

xi 1

Cn Cn-mi

i i+1

If i<=n then xi Cn / mi

14.Probleme de combinatorica

14.1 Generarea produsului cartezian:

Problema: Fiind date m multimi A1,A2,,Am,sa se genereze elementele produsului

cartezian A1xA2xxAm,unde Ai= cu 1 i m.

Solutie: Vom determina elementele produsului cartezian intr-un vector v cu m componente,in ordine lexicografica(ordinea stabilita de termenii unui dictionar,in cazul nostru ordinea precizata de codul ASCII).Vom determina I=I xI xxIm,unde Ii= cu 1 i m.

Pornim de la elementul cel mai mic in sens lexicografic al produsului cartezian I,si anume

v=(1,1,,1).Avand un element v,pentru a construi succesorul lui,determinam cel mai mare indice i cu vi<ni si drept succesiv al lui v se alege vectorul (v1,,vi-1,vi+1,1,1,,1).Daca nu exista un astfel de indice,inseamna ca s-a obtinut vectorul v=(n1,n2,,nm),adica cel mai mare element al produsului cartezian in sens lexicografic si algoritmul se termina.

Exemplu:Fie I =,I =,I =.Elementele prod. cartezian I xI xI se obtin in ordinea:(1,1,1) (1,1,2) (2,1,1) (2,1,2) (3,1,1) (3,1,2).

Observatie:Fiecare element (i ,i ,,im) al produsului cartezian I=I xI xxIm genereaza un element si numai unul al produsului cartezian A xA xxAm si anume (a1i ,a2i ,,amim

14.2 Fiind data o multime A cu n elemente,se cere generarea tuturor submultimilor sale.

Solutie:Daca A=,sa observam ca intre aceasta multime si multimea

B= exista o bijectie.Vom lucra doar cu multimea B determinand toate submultimile sale (multimea B va fi multimea indicilor si fiecare submultime a lui B va selecta din A elementele unei submultimi).

Pentru reprezentarea submultimilor lui B vom folosi vectorii caracteristici(care contin doar elementele 0 sau 1).Fie S= o submultime a lui B.Ei ii asociem un vector v cu n componente apartinand multimii,care va avea valoarea 1 doar pe pozitiile

i ,i ,,ik.V se numeste vectorul caracteristic al multimii S (si reprezinta de fapt functia caracteristica asociata luiS.Intr-adevar

v[i]= 1,daca i apartine multimii S

0,in caz contrar

De asemenea fiecarui vector cu n componente binare i se poate asocia o multime S a lui B

astfel:S=

Exemplu:fie B= si S=.Lui S i se asociaza vectorul caracteristic

v=(0,1,1,0,1).Invers vectorului v=(1,1,1,0,1) i se poate asocia submultimea S=,S

fiind inclus in B.

Generarea vectorilor caracteristici se face simuland adunarea in baza 2,intre numarul reprezentat de vectorul v si 1.Atat timp cat se gasesc valori egale cu 1,pornind de la componenta v[n],in sens invers,spre inceputul vectorului,acestea se transforma in zorouri,conform egalitatii 1+1=10(in baza 2).Cand s-a intalnit primul element egal cu zero,el se transforma in 1(dupa egalitatea 1+0=1,valabila si in baza 2).In acest moment

s-a terminat generarea unui nou vector caracteristic si se afiseaza submultimea lui B corespunzatoare lui.Algoritmul se termina dupa ce s-a afisat multimea B,cand de fapt nu mai este posibila generarea unui nou vector caracteristic.

14.3 Generarea aranjamentelor:

Problema:Fie multimea A= si 0 m n.Sa se genereze toate modalitatile de

selectare si aranjare a m elemente din multimea A.

Solutie:Dupa cum stim,exista aranjamente de n elemente luate cat m posibilitati.Problema generarii aranjamentelor unei multimi A cu n elemente se reduce la problema generarii aranjamentelor multimii.Orice solutie (ai,ai ,,aim) a problemei initiale fiind obtinuta din solutia (i ,,im) a celei de-a doua probleme.

Solutiile vor fi memorate succesiv intr-un vector A cu m componente.

Exemplu:A= si m=2.Aranjamentele sunt:

Vom genera aranjamentele in ordine lexicografica(ordinea determinata de codul ASCII).

Pentru exemplul de mai sus ordinea va fi:(1,2) (1,3) (2,1) (2,3) (3,1) (3,2).

Pornim de la aranjamentul cel mai mic in sens lexicografic si anume (1,2,,m).Avand un aranjament a=(a ,,am) pentru determinarea succesorului sau cautand cel mai mare indice i,cu proprietatea ca ai poate fi marit(macar una din valorile ai+1,,n este disponibila).Daca exista un astfel de indice,aranjamentul urmator este obtinut din a prin inlocuirea elementelor ai,ai+1,,am cu cele mai mici numere disponibile in ordine crescatoare.Daca nu exista un indice i cu proprietatea mentionata inseamna ca am ajuns la vectorul (n,n-1,,n-m+1) care este si cel mai mare in sens lexicografic si deci generarea s-a incheiat.

14.4 Generarea permutarilor:

Problema:Pentru o multime data A,sa se genereze toate permutarile sale.

Solutie:Numim permutarea unei multimi A= o aplicatie bijectiva f:A->A.

Orice permutare f a unei multimi A cu n elemente,o vom retine intr-un vector p de dimensiune n,in care p[i]=f(ai).Daca A are n elemente exista n! permutari.

Exemplu:Daca A= exista 3! permutari,si anume:

Intre permutarile multimii A= si permutarile multimii I= exista o corespondenta biunivoca,deci problema generarii permutarilor unei multimi A cu n elemente se reduce la generarea permutarilor multimii .

Vom genera permutarile in ordine lexicografica(crescatoare).

Se pleaca de la permutarea cea mai mica in ordine lexicografica si anume de la permutarea identica (1 ,,n).Avand o permutare construita p=(p1,p2,,pn) pentru determinarea urmatoarei permutari ,punem in evidenta acel indice i astfel incat pi<pi+1;

pi+1>pi+2>>pn.Urmatoarea permutare se obtine din p prin inlocuirea lui pi cu cel mai mic dintre elementele pi+1,,pn care este mai mare ca pi,urmata de inversarea ordinii ultimilor n-i elemente,incat ele sa apara in ordine crescatoare.Daca nu exista un indice i ca mai sus,inseamna ca am ajuns la permutarea cea mai mare in ordinea lexicografica,

adica la (n,n-1,,1) si algoritmul se termina.