Capitolul 8

Alocarea memoriei în Turbo Pascal

Cuprins

Introducere 3

Capitolul I. Alocarea statică a memoriei în Turbo Pascal. Structuri statice 5

Capitolul II. Alocarea dinamică a memoriei în Turbo Pascal. Structuri dinamice 21

Concluzii 68

Bibliografie 69

Introducere

Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le voi prezenta în continuare.

Definiţie: Printr-un tip de dată înţelegem o mulţime cu elemente numite valori.

De sxemplu:{-32768, -32767,...0,1, ...32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. În Turbo Pascal un astfel de tip se numeşte integer şi este predefinit.

Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului.

De exemplu, pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc.

Pentru fiecare tip se defineşte modul în care se memorează valorile sale.

De exemplu, pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi.

Pentru a lucra cu date de un anumit tip se folosesc variabile. O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi).

Tipurile de date pot fi simple şi structurate.

Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date.

Noţiunea de tip de date este strînsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date. De exemplu, mulţimea este o structură de date. În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi.

Variabilele declarate în secţiunea var a unui program sau subprogram se numesc variabile statice. Numărul variabilelor statice se satabileşte în momentul scrierii programului şi nu poate fi schimbat în timpul execuţiei. Există însă situaţii în care numărul necesar de variabile nu este cunoscut din timp. De exemplu, presupunem că este necesară prelucrarea datelor referitoare la persoanele care formează o listă de aşteptare (o coadă) la o casă de bilete. Lungimea cozii este nedefinită. De fiecare dată cînd apare o persoană nouă, trebuie să se creeze o variabilă de tipul respectiv. După ce persoana pleacă – variabile evine inutilă.

Variabilele care sunt create şi eventual distruse în timpul execuţiei programului se numesc variabile dinamice.

Capitolul I. Alocarea statică a memoriei în Turbo Pascal. Structuri statice

O structură de date este formată din datele propriu-zise şi relaţiile dintre ele. În funcţie de modul de organizare, o structură de date poate fi implicită sau explicită.

Tablourile, şirurile de caractere, articolele, fişierele şi mulţimile sunt structuri implicite de date. Relaţiile dintre componentele acestor structuri sînt predefinite şi nemodificabile. De exemplu, toate componentele unui şir de caractere au un nume comun, iar caracterul s[i+1] este succesorul caracterului s[i] în virtutea poziţiei ocupate.

Structurile de date se clasifică în două mari categorii: statice şi dinamice. Criteriul de clasificare este dat de modul de alocare a memoriei interne.

Întrucît structura tablourilor, şirurilor de caractere, articolelor, mulţimilor, fişierelor nu se modifică în timpul execuţiei oricărul program sau subprogram, structurile respective reprezintă structuri statice de date.

§1. Tabloul

Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale.

Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi.

Definiţie: Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare. Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente.

Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indicii.

Exemplul 1: Distanţa dintre două mulţimi în plan se consideră distanţa dintre două puncte ale acestor mulţimi, situate cel mai aproape unul de altul. Aflaţi distanţa dintre două mulţimi de puncte date. (pr.38, §5, [1])

Rezolvare:

Pentru rezolvarea acestei probleme vom utiliza două masive, care au două linii (pentru a stoca coordonatele unui punct: linia1 va memora abscisa x, iar linia 2 va memora ordonata y) şi 100 de colonane. În total vom putea lucra cu mulţimi de 100 de puncte maxim. Pentru această problemă se va aloca static următorul volum de memorie:

mas1: 2*100=200*2o=400octeţi

mas2: 2*100=200*2o=400octeţi

i,j,p1,p2: 4*2o=8octeţi

min, d2: 2*6o=12octeţi

În total: 400+400+8+12=820octeţi

Acest număr de octeţi va fi alocat static indiferent de numărul de puncte al celor două mulţimi. Se va ţine cont doar ca el să fie mai mic ca 100.
Program p5_pr38;

uses crt;

const n=3;

const m=4;

var mas1,mas2:array[1..2,1..100] of integer;

i,j,p1,p2:integer;

min,d2:real;

Begin

clrscr;

writeln('Introduceti coordonatele punctelor primei multimi:');

for i:=1 to n do

readln(mas1[1,i],mas1[2,i]);

writeln('Introduceti coordonatele punctelor cele dea doua multimi:');

for j:=1 to m do

readln(mas2[1,j],mas2[2,j]);

min:=sqrt(sqr(mas2[1,1]-mas1[1,1])+sqr(mas2[2,1]-mas1[2,1]));

for i:=1 to n do

for j:=1 to m do begin

d2:=sqrt(sqr(mas2[1,j]-mas1[1,i])+sqr(mas2[2,j]-mas1[2,i]));

if d2

min:=d2;

p1:=i;

p2:=j;

end;end;

writeln('Distanta dintre multimi este:',min:5:2);

writeln('Coordonatele celor mai apropiate puncte:');

writeln('Coord p-lui din I multime','(',mas1[1,p1],',',mas1[2,p1],')');

writeln('Coord p-lui din multimea II','(',mas2[1,p2],',',mas2[2,p2],')');

readkey

end.

§2. Articolul

Alături de alte tipuri de date structurate limbajul de programare Pascal acceptă şi un alt tip de date structurat şi anume tipul record. Deşi nu sunt unice în Pascal, record-urile sunt elemente nepreţuite ale limbajului, deoarece ele facilitează prelucrarea datelor structurate în fişiere, dar în plus ele ne permit să creăm array-uri de date agregate de tipuri mixte - un instrument foarte puternic de organizare a datelor. Structura array-ului este potrivită atunci cînd toate datele de intrare sunt de acelasi tip.

În Pascal partea fixă a unui record are exact aceeaşi structură, component cu component, pentru fiecare entitate din acel tip de record.

De exemplu:

with scoala do

begin

numescoala:=

Gr[5].fete:=

end;
Tipurile record pot fi numite în secţiunea type (cu nume) sau pot fi declarate direct (anonime) în secţiunea var;

Din moment ce "tip" este foarte general, record-urile pot conţine componente de orice tip Pascal, valide - simple sau structurate. Putem avea record-uri de set-uri (mulţimi), record-uri de array-uri ş.a.

Avantajele utilizarii tipului record sunt acelea care corespund oricarui tip structurat:

1. 
   O data ce am ales un tip de identificator putem declara în secţiunea var orice număr de variabile avînd acelaşi tip.
   
2. 
   Tipul de identificator ales poate fi citat în antetul unei funcţii sau proceduri, dar nu poate fi rezultat de funcţie:
   

Sunt valabile următoarele reguli:

 Zona de memorie nu este alocată cînd tipul unui record este declarat în zona type; ea este alocată numai cînd record-urile sunt create în secţiunea var;

 Odată creat în secţiunea var, unui record i se alocă spaţiu, dar componentele lui sunt nedefinite pînă în momentul cînd un enunţ input sau de atribuire se execută şi le atribuie valorile corespunzătoare;

 Referirea la un cîmp al record-ului se face cu respectarea sintaxei: .. Punctul (plasat între nume variabilă şi cîmp selector ) este un operator ca şi parantezele drepte utilizate pentru array-uri. Aşa cum valoarea indexată inclusă în paranteze drepte se referă la un anumit component în array, tot acţionează şi un selector de cîmp ce urmează unui punct;

 Instrucţiunea with permite scrierea simplificată a referinţelor la cîmpurile variabilelor record;

 Cîmpurile unui record pot fi utilizate în program în acelaşi mod ca şi variabilele simple;

 Valoarea unei variabile de tip record poate fi atribuită altei variabile de acelaşi tip;

 O variabilă de tip record poate face parte din lista de parametri a unei funcţii sau proceduri, dar o funcţie nu poate fi de tip record;

 Este posibil ca variabilele aparţinînd aceluiaşi tip record să conţină componente diferite. Pentru definirea acestora se utilizează record-uri cu variante.

Exemplul 1: scrieţi un program asistat de un meniu care să realizeze următoarele funcţii: citirea datelor în vector, afişarea meniului, afişarea studenţilor după punctaj şi specializări.

Lista programului, conţinînd procedurile: getdata, scriemenu, specialitate, punctaj este prezentată în continuare.

PROGRAM cautaclass;

type

studentrec=record

nume:string[20];

specializare:string[4];

punctaj:char

end {studentrec};

classtype=array[1..30] of studentrec;

var

class:classtype;

dim, alegere:integer;

procedure GETDATA (var class:classtype;var dim:integer);

var

i:integer;

begin

i:=0;

while NOT eof do

begin

i:=i+1;

with class[i] do

begin

readln(nume);

readln(specializare);

readln(punctaj)

end {with}

end {while};

dim:=i

end {GETDATA};

procedure SCRIEMENU;

begin

writeln(' MENIU ');

writeln(' 1. Toti studentii cu o specializare data');

writeln(' 2. Toti studentii cu un punctaj dat');

writeln(' 3. Exit ')

end {SCRIEMENU};

procedure SPECIALIZARE(class:classtype; dim:integer);

var

stud:integer;

specializaredorita:string[4]

begin

writeln('Introduceti primele patru litere (toate majuscule)');

write('ale specializarii dorite');readln(specializaredorita);

writeln('Lista specializarii ',specializaredorita);

for stud:=1 to dim do

with class[stud] do

IF specializare=specializaredorita then

writeln(nume,' ', punctaj)

end {SPECIALIZARE};

procedure PUNCTAJ(class:classtype; dim:integer);

var

stud:integer;

punctajcautat:char;

begin

writeln('Introduceti punctajul');readln(punctajcautat);

writeln('Lista studentilor cu punctaj' ,punctajcautat);

for stud:=1 to dim do

with class[stud] do

IF punctaj=punctajcautat then

writeln(nume,' ', specializare)

end {PUNCTAJ};

 

begin {corp principal}

GETDATA(class,dim);

REPEAT

SCRIEMENU;

write('Introduceti optiunea dumneavoastra: ');readln(alegere);

case alegere of

1:specializare(class,dim);

2:punctaj(class,dim);

3:{iesirea din iteratie}

else writeln('optiune incorecta')

end {case};

writeln

UNTIL alegere=3

end {cautaclass}.
Observaţie: Volumul de memorie alocat static pentru rezolvarea acestei probleme este: 20+4+1=25octeţi pentru o înregistare.

class: 25octeţi*30înregistrări=750octeţi.

dim, alegere: 2*2°=4 octeţi.

În total sunt necesari 754octeţi, indiferent de numărul de studenţi din grupă, care nu trebuie să fie mai mare ca 30.

Un record poate avea, alături de partea sa fixă şi o parte variabilă, în funcţie de existenţa mai multor variante de structură a înregistrării. Structura parţii variante a unui record poate avea diferite forme, depinzînd de împrejurări. În vectorii de record-uri pe care i-am utilizat pîna acum, fiecare înregistrare dintr-un vector a avut exact aceleaşi cîmpuri. Există însă situaţii în care formatul unei singure înregistrări nu este adecvat pentru toate articolele din vector. De exemplu, o companie ar putea dori sa înmagazineze tipuri diferite de informaţii despre angajaţii care lucrează în mod curent şi despre aceia care sunt concediaţi. Înregistrările cu variante oferă această flexibilitate.

Programatorul poate concepe structura înregistrării astfel încît prima parte a unei înregistrări cu variante stochează acelaşi tip de informaţii pentru toate înregistrările, dar ultima parte a înregistrării poate conţine tipuri de date diferite. Această ultimă parte a unei înregistrări cu variante este numită tag field (de capăt liber) şi este, de obicei, definită folosind un enunţ case.

Se vor respecta următoarele reguli:

• 
  Formatul pentru case ar putea părea familiar, dar folosirea lui aici diferă într-un mod important de modul cum este folosit într-o structură de control. Ca structură de control, un enunţ case se afla în partea de enunţ a programului, funcţiei sau procedurii, iar etichetele case sunt folosite pentru a eticheta enunţurile executabile. Aşa cum s-a folosit în definirea record-ului cu variante, un enunţ case survine în partea declarativă a programului, funcţiei sau procedurii. În clauza case se specifică tipul unui cîmp al record-ului numit discriminator. Constantele case grupează între paranteze toate cîmpurile care corespund variantelor record particulare care au fost definite (constantele case folosite pentru a eticheta record-uri cu variante pot fi de orice tip ordinal);
  
• 
  Enunţul case folosit pentru a defini cîmpul de "capat liber" (tag field) al record-ului, nu are nevoie de un enunţ end, întrucît end-ul pentru record închide de asemenea şi enunţul case;
  
• 
  Reţineţi folosirea parantezelor în definirea cîmpurilor în tag field. Parantezele goale pentru clasa demisionat precizează că nici un alt cîmp nu este parte componentă a record-ului pentru un angajat demisionat;
  
• 
  Numele de variante date cîmpurilor în tag field-ul unui record trebuie să fie unice;
  

Exemplul 2: Se citesc datele despre candidaţii la admiterea într-o instituţie de învăţămînt. Pentru fiecare candidat se cunoaşte:

• 
  numele şi prenumele ;
  
• 
  data naşterii (ziua, luna, anul) ;
  
• 
  sexul;
  
• 
  studii (medii sau liceu);
  

Pentru fiacare absolvent de liceu se ştie nota medie din diplomă. Fiecare absolvent al şcolii medii susţine 2 examene (la română şi la profil), după care i se calculează nota medie. Să se afişeze lista candidaţilor în ordinea descreşterii notei medii.

Rezolvare:

Program studii;

uses crt;

type TStudii=(bac,medii);

data=record

zi:1..31;

luna:1..12;

an:word;

end;

TCand=record

nume,pren:string[20];

dn:data;

sex:char;

nm:real;

case studii:TStudii of

medii:(rom,profil:1..10);

bac:();

end;

var a:array[1..50] of TCand;

t:TCand;

n,i,j:integer;

s:char;

Begin

clrscr;

write('Introdu numarul de candidati, n=');

readln(n);

for i:=1 to n do

with a[i] do begin

writeln('-----',i,'-----');

write('Nume: ');readln(nume);

write('Prenume: ');readln(pren);

write('Ziua,luna,anul nasterii: ');

readln(dn.zi,dn.luna,dn.an);

write('Sexul (m/f): ');readln(sex);

write('Bacalaureat (b) sau scaoala medie (m): ');

readln(s);

if s='m' then begin

studii:=medii;

write('Romana: ');readln(rom);

write('Profil: ');readln(profil);

nm:=(rom+profil)/2;end

else begin

studii:=bac;

write('Nota medie: ');readln(nm);end;

writeln;end;

for j:=1 to n do

for i:=1 to n-1 do

if a[i].nm

t:=a[i];

a[i]:=a[i+1];

a[i+1]:=t;end;

for i:=1 to n do

with a[i] do begin

write(nume:15, ' ',pren:15,' ',sex:3,' ',nm:6:2,' ');

if studii=medii then write('{Rom: ',rom:2,',', ' Profil: ',profil:2,'}');

writeln;

end;

readkey;

End.
Introdu numarul de candidati, n=3

-----1-----

Nume: Ivanov

Prenume: Ion

Ziua,luna,anul nasterii: 21 4 1986

Sexul (m/f): m

Bacalaureat (b) sau scaoala medie (m): b

Nota medie: 8.97

-----2-----

Nume: Ilascu

Prenume: Vasile

Ziua,luna,anul nasterii: 12 4 1989

Sexul (m/f): m

Bacalaureat (b) sau scaoala medie (m): m

Romana: 8

Profil: 7

-----3-----

Nume: Petrov

Prenume: Alina

Ziua,luna,anul nasterii: 13 7 1990

Sexul (m/f): f

Bacalaureat (b) sau scaoala medie (m): b

Nota medie: 9.14

Petrov Alina f 9.14

Ivanov Ion m 8.97

Ilascu Vasile m 7.50 {Rom: 8, Profil: 7}

Observaţie: Volumul de memorie alocat static pentru rezolvarea acestei probleme este: 2+2+2+20+20+1+6+2+2=57octeţi pentru o înregistare.

a: 57octeţi*50înregistrări=2850octeţi

t: 57octeţi

n,i,j: 3*2°=6 octeţi

s: 1octet.

În total sunt necesari 2914 octeţi, indiferent de numărul de abiturienţi, care nu trebuie să fie mai mare ca 50.

Evident putem prelucra şi liste mult mai mari, adică care vor ocupa un volum de memorie mult mai mare. Pentru aceasta vom utiliza fişierele.

§3. Mulţimea

Fie A o mulţime finită. Ea poate fi privită ca o structură de date. Puţine dintre limbaje admit un tip de date numit mulţime (set). Însă şi aici numărul elementelor unei mulţimi nu poate fi mai mare decît 255 (avantajul este că sunt predefinite operaţiile cu mulţimi). În ipoteza că programatorul doreşte să implementeze algoritmi care lucrează cu mulţimi, indiferent de limbaj, se poate folosi vectorul caracteristic. Astfel, pentru o mulţime cu n elemente, orice submulţime a sa va fi definită cu ajutorul unui vector cu n componente, în care fiecare componentă poate lua doar două valori 0 şi 1.

În acest caz, este sarcina programatorului să simuleze diversele operaţii cu mulţimi.

Exemplul 1: Se dă numărul natural n, n<20. Se citesc de la tatatură n mulţimi de numere naturale mai mici decît 100. Să se afişeze reuniunea şi intersecţia acestor mulţimi.

Rezolvare:

Vom păstra mulţimile într-un vector. Iniţial vom atribui mulţimii-intersecţie toate numerele de la 0 la 100. Deoarece nu dispunem de peoceduri de intare – ieşire pentru tupul de date mulţime, vom utiliza o variabilă el, care ne va permite citirea unei valori de tip byte pe care mai apoi o vom adăuga la mulţime:

readln(el);

a[i]:=a[i]+[el];

iar pentru afişarea elementelor unei mulţimi (în cazul nostru mulţimea inter – intersecţia tuturor mulţimilor) vom utiliza secvenţa de program:

for i:=0 to 100 do

if i in inter then write(i,’ ’);

Programul Pascal este următorul:

Program multimile;

uses crt;

type multime=set of byte;

var a:array[1..20] of multime;

reun,inter:multime;

i,n,el:byte;

Begin

clrscr;

write('Introdu numarul de multimi: ');

readln(n);

for i:=1 to n do begin

a[i]:=[];

{introducem elementle multimii i}

writeln('Multimea ',i);

repeat

write('Elementul: ');

readln(el);

a[i]:=a[i]+[el];

until not (el in [0..100]);

end;

reun:=[];

inter:=[0..100];

for i:=1 to n do begin

reun:=reun+a[i];

inter:=inter*a[i];

end;

writeln('Reuniunea:');

for i:=0 to 100 do

if i in reun then write(i,' ');

writeln;

writeln('Intersectia:');

for i:=0 to 100 do

if i in inter then write(i,' ');

readkey;

End.
Introdu numarul de multimi: 3

Multimea 1

Elementul: 1

Elementul: 2

Elementul: 3

Elementul: 4

Elementul: 5

Elementul: 6

Elementul: 9

Elementul: 101

Multimea 2

Elementul: 5

Elementul: 6

Elementul: 7

Elementul: 8

Elementul: 9

Elementul: 102

Multimea 3

Elementul: 4

Elementul: 5

Elementul: 6

Elementul: 7

Elementul: 8

Elementul: 9

Elementul: 10

Elementul: 12

Elementul: 11

Elementul: 103

Reuniunea:

1 2 3 4 5 6 7 8 9 10 11 12

Intersectia:

5 6 9