la disciplina STRUCTURI DE DATE

 

STRUCTURI DE DATE

INTRODUCERE:

Se va aprecia avantajele si dezavantajele folosirii unei anumite structuri de date .

Structurile de date folosite, in cazul aplicatei de fata, sunt: masivul, lista dublu inlantuita si fisierul. Pe aceste structuri de date se memoreaza datele ce tin de rezolvarea problemei financiar -contabile "SALARIZAREA". Operatiile realizate pe fiecare structura sunt: adaugarea, stergerea, pontajul zilelor de lucru si de concediu, tiparirea fluturasilor si sortarea articolelor (aceasta operatie ne ajuta la compararea timpilor de lucru pe fiecare structura in parte) . Fiecare din aceste operatii pune in evidenta caracteristicile structurii folosite.

Alegerea acestei teme este determinata de multitudinea formelor de stocare a datelor in memoria RAM a calculatorului si de necesitatea aprecierii acestora prin intermediul unor indicatori ,cum ar fi: timpul de rulare pentru fiecare operatie in parte, numarul de instructiuni pentru fiecare operatie ,memoria ocupata in cazul structurilor folosite.

Nu stiu daca modul meu de evaluare a structurilor folosite este cel mai fericit dar sper sa formeze o imagine sumara asupra structurilor de date.

DESCRIEREA PROBLEMEI:

Scopul este evaluarea comparativa a masivului, listei si fisierului. Pentru a le putea compara efectuez aceleasi operatii in aceleasi conditii pe structurile de date mai sus amintite. Folosirea structurilor de date este asociata cu operatiile asupra unor date de tip articol, operatiile efectuate fiind avand ca rezultat adaugarea, stergerea, modificarea, sortarea si listarea articolelor sub anumite forme.

Se urmareste evaluarea structurilor prin obtinerea unor timpi de executie, prin operatia de sortare pe fiecare varianta in parte, prin gestionarea spatiului de memorie, de cod si de date, ocupat pe fiecare implementare a operatiilor, prin numarul de linii sursa necesare realizarii unei anumite variante, prin obtinere unor timpi de compilare.

DESCRIEREA SOLUTIEI:

Pentru realizarea scopului propus, acela de evaluare a unor structuri de date am folosit o serie de proceduri si functii din unitul DOS cat si un utilitar pus la dispozitie de BORLAND PASCAL, si anume TURBO PROFILER.

Pentru ca indicatorii obtinuti sa fie fideli versiunii alese, in fiecare caz datele se citesc dintru-un fisier creat anterior. Astfel se evita timpii morti in cazul introducerii de la terminal.

Evaluarea variantelor am facut-o prin doua variante pentru a face o comparatie cat mai buna intre structurile de date folosite.

Prima varianta foloseste procedura DOS GETTIME () pentru a returna timpul sistemului. Apoi am facut o comparatie intre timpul luat din sistem inaintea sortarilor si timpul de dupa sortari. Tinand cont de rapiditatea de executie a sistemului si de numarul destul de mic de articole din fisier, aceasta metoda nu mi-a fost suficenta. Cea de-a doua varianta are la baza lansarea programului TPROF ce are ca parametru in linia de comanda, pe rand, fiecare din cele trei variante. Indicatorii rezultati in urma fiecarei lansari sunt:

Timpi de executie pentru fiecare operatie

Frecventa apelurilor fiecarei  proceduri in cadrul unei variante

Timpul total de executie al implementarii

Procentajul timpului de executie al unei operatii in cadrul timpului total de executie al unei variante

Procentajul apelurilor unei operatii raportat la numarul total de apeluri

In urma fiecarei rulari a programului TPROF toate aceste statistici sunt trecute intr-un fisier text ce poate fi vizualizat cu orice editor de texte. Tot in acest fisier sunt trecute rezultatele compilarii fiecarei variante, si anume:

Numarul de linii compilate

Timpul de compilare

Spatiu afectat codului

Spatiu afectat datelor

F de utilitate indirecta si functia de cheltuieli

SCHEMA LOGICA:

TEXTELE SURSA

program principal;

uses crt,graph,fisier,masive,liste;

begin

clrscr;

Gd := Detect; InitGraph (Gd, Gm, 'c:bpbgi') ;

eroare:=graphresult;

if eroare <> grOk then begin writeln (grapherrormsg (eroare) ) ;

Halt (1) ;

end;

ecran;

assign (fis,'salarii') ;

repeat

c:=readkey;

case c of

'1' : begin

ecran1;

fisi (opti) ;

ecran;

end;

'2' : begin

ecran1;

mas (opti) ;

ecran;

end;

'3' : begin

ecran1;

lis (opti) ;

ecran;

end;

'4' :begin

clrscr;

gotoxy (4,2) ;write ('TIMPUL DE LUCRU <Śn milisecunde>: ') ;

gotoxy (27,7) ;write ('Pentru fisiere : ',lz (tsec1) ,':',lz (tsut1) ) ;

gotoxy (27,8) ;write ('Pentru masive : ',lz (tsec2) ,':',lz (tsut2) ) ;

gotoxy (27,9) ;write ('Pentru liste : ',lz (tsec3) ,':',lz (tsut3) ) ;

textcolor (red) ;

gotoxy (29,24) ;write ('press any key!!!') ;

TEXTCOLOR (BLACK) ;

readln;

ecran;

end;

end;

until c='5';

closegraph;

end.

PROCEDURILE PRINCIPALE:

Din unitul fisir.tpu:

procedure stergf;

var v:byte;

begin

repeat

cap4;

gotoxy (6,6) ;

write ('Numele salariatului : ') ;

valchar20 (num) ;

er:=false;

reset (fis) ;

read (fis,art) ;

while not eof (fis) do

begin

if num=art.nume then

begin

er:=true;

v:=filepos (fis) -1;

while not eof (fis) do

begin

read (fis,art1) ;

seek (fis,filepos (fis) -2) ;

write (fis,art1) ;

seek (fis,filepos (fis) +1) ;

end;

seek (fis,filesize (fis) -1) ;

truncate (fis) ;

seek (fis,v) ;

end;

read (fis,art) ;

end;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

close (fis) ;

write ('Continuati ?<D/N> : ') ;readln (c) ;

until (c='n') or (c='N') ;

end;

procedure pontajf;

begin

repeat

cap3;

gotoxy (6,6) ;

write ('Numele salariatului : ') ;

valchar20 (num) ;

er:=false;

reset (fis) ;

read (fis,art) ;

while not eof (fis) do

begin

if num=art.nume then

begin

er:=true;

repeat

write ('Nr. zilelor lucratoare ? ') ;valmult031 (0,31,art.zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ? ') ;valmult031 (0,31,art.zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ? ') ;valmult031 (0,31,art.zile.zile_con_fplat) ;

until 31> (art.zile.zile_luc+art.zile .zile_con_med+art.zile.zile_con_fplat) ;

seek (fis,filepos (fis) -1) ;

write (fis,art) ;

end;

read (fis,art) ;

end;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

close (fis) ;

write ('Continuati ?<D/N> : ') ;readln (c) ;

until (c='n') or (c='N') ;

end;

procedure fisi;

var r:zil;

begin

repeat

case op of

'1':begin

clrscr;

textcolor (7) ;

reset (fis) ;

seek (fis,filesize (fis) ) ;

while r<>0 do

with art do

begin

clrscr;

gotoxy (25,2) ;

textcolor (RED) ;

writeln ('Introduceti datele noului salariat : ') ;

gotoxy (1,5) ;

textcolor (7) ;

write ('Marca salariatului ?<byte> ') ;valnumerby (marca) ;

write ('Numele salariatului ?<string[20]> ') ;valchar20 (nume) ;

write ('Compartimentul salariatului ?<string[15]> ') ;valchar15 (compartiment) ;

write ('Functia salariatului<string[15]> ? ') ;valchar15 (functie) ;

write ('Salariul angajatului<word> ? ') ;valnumerwo (salariu) ;

repeat

write ('Nr. zilelor lucratoare ?<0..31> ') ;valmult031 (0,31,zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ?<0..31> ') ;valmult031 (0,31,zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ?<0..31> ') ;valmult031 (0,31,zile.zile_con_fplat) ;

until 31> (zile.zile_luc+zile.zile_con_med+zile.zile_con_fplat) ;

write ('Indicele de stare referitor la retinerile salariatului <1-DA,0-NU>? ') ;valmult031 (0,1,retineri.ind_stare) ;

if retineri.ind_stare=0 then

begin

retineri.suma_retin:=0;

retineri.rata_lunara:=0;

end

else

begin

write ('Unitatea de la care s-a facut imprumutul <CAR,CEC,BANCA,etc> ?<strin[5]> ') ;valchar5 (retineri.unitati) ;

write ('Suma de retinut ?<word> ') ;valnumerwo (retineri.suma_retin) ;

write ('Rata lunara ?<word> ') ;valnumerwo (retineri.rata_lunara) ;

end;

writeln ('Data angajarii ? ') ;

write ('<1..31> Ziua : ') ;valmult031 (1,31,data.zi) ;

write ('<1..12> Luna : ') ;valmult031 (1,12,data.luna) ;

write ('<1939..1999>Anul : ') ;valmult3999 (1939,1999,data.an) ;

write (fis,art) ;

write ('Continuati <DA-1/NU-0> ? ') ;

valmult031 (0,1,r) ;

end;

close (fis) ;

ecran1;

end;

'2':begin

stergf;

ecran1;

end;

'3':begin

pontajf;

ecran1;

end;

'4':begin

fluturasif;

ecran1;

end;

'5':begin

GetTime (h,m,s,hund) ;

reset (fis) ;

for i:=0 to filesize (fis) -2 do

seek (fis,i) ;

read (fis,art,art1) ;

if art.nume>art1.nume then

begin

seek (fis,i) ;

write (fis,art,art1) ;

end;

delay (20) ;

close (fis) ;

Gettime (h1,m1,s1,hund1) ;

if s1<s then

begin

s1:=s1+60;

tsec1:=s1-s;

end

else

tsec1:=s1-s;

if hund1<hund then

begin

hund1:=hund1+100;

tsut1:=hund1-hund;

end

else

tsut1:=hund1-hund;

ecran1;

end;

end;

op:=readkey;

until op='6';

end;

Din unitul masive.tpu:

procedure stergm;

var v:byte;

begin

repeat

cap4;

gotoxy (6,6) ;

write ('Numele salariatului :<string[20]> ') ;

valchar20 (num) ;

er:=false;

for i:=1 to k-1 do

if num=vec[i].nume then

begin

er:=true;

for j:=i to k-2 do

vec[j]:=vec[j+1];

k:=k-1;

end;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

write ('Continuati ?<D/N> : ') ;readln (c) ;

until (c='n') or (c='N') ;

end;

procedure pontajm;

begin

repeat

cap3;

gotoxy (6,6) ;

write ('Numele salariatului :<string[20]> ') ;

valchar20 (num) ;

er:=false;

for i:=1 to k-1 do

if num=vec[i].nume then

repeat

er:=true;

write ('Nr. zilelor lucratoare ?<0..31> ') ;valmult031 (0,31,vec[i].zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ?<0..31> ') ;valmult031 (0,31,vec[i].zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ?<0..31> ') ;valmult031 (0,31,vec[i].zile.zile_con_fplat) ;

until 31> (vec[i].zile.zile_luc+vec[i].zile.zile_con_med+vec[i].zile.zile_con_fplat) ;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

write ('Continuati ?<D/N> : ') ;

readln (c) ;

until (c='n') or (c='N') ;

end;

procedure mas;

var r:zil;

begin

reset (fis) ;

k:=1;

while not eof (fis) do

begin

read (fis,art) ;

vec[k]:=art;

k:=k+1;

end;

close (fis) ;

repeat

case op of

'1':begin

clrscr;

textcolor (7) ;

reset (fis) ;

seek (fis,filesize (fis) ) ;

while r<>0 do

with art do

begin

clrscr;

gotoxy (25,2) ;

textcolor (RED) ;

writeln ('Introduceti datele noului salariat : ') ;

gotoxy (1,5) ;

textcolor (7) ;

write ('Marca salariatului ?<byte> ') ;valnumerby (marca) ;

write ('Numele salariatului ?<string[20]> ') ;valchar20 (nume) ;

write ('Compartimentul salariatului ?<string[15]> ') ;valchar15 (compartiment) ;

write ('Functia salariatului ?<string[15]> ') ;valchar15 (functie) ;

write ('Salariul angajatului ?<word> ') ;valnumerwo (salariu) ;

repeat

write ('Nr. zilelor lucratoare ?<0..31> ') ;valmult031 (0,31,zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ?<0..31> ') ;valmult031 (0,31,zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ?<0..31> ') ;valmult031 (0,31,zile.zile_con_fplat) ;

until 31> (zile.zile_luc+zile.zile_con_med+zile.zile_con_fplat) ;

write ('Indicele de stare referitor la retinerile salariatului <1-DA,0-NU>? ') ;valmult031 (0,1,retineri.ind_stare) ;

if retineri.ind_stare=0 then

begin

retineri.suma_retin:=0;

retineri.rata_lunara:=0;

end

else

begin

write ('Unitatea de la care s-a facut imprumutul <CAR,CEC,BANCA,etc> ?<string[5]> ') ;valchar5 (retineri.unitati) ;

write ('Suma de retinut ?<word> ') ;valnumerwo (retineri.suma_retin) ;

write ('Rata lunara ?<word> ') ;valnumerwo (retineri.rata_lunara) ;

end;

writeln ('Data angajarii ? ') ;

write ('<1..31> Ziua : ') ;valmult031 (1,31,data.zi) ;

write ('<1..12> Luna : ') ;valmult031 (1,12,data.luna) ;

write ('<1939..1999>Anul : ') ;valmult3999 (1939,1999,data.an) ;

vec[k]:=art;

write (fis,art) ;

k:=k+1;

write ('Continuati <DA-1/NU-0> ? ') ;

valmult031 (0,1,r) ;

end;

close (fis) ;

ecran1;

end;

'2':begin

stergm;

ecran1;

end;

'3':begin

pontajm;

ecran1;

end;

'4':begin

fluturasim;

ecran1;

end;

'5':begin

GetTime (h,m,s,hund) ;

for i:=1 to k-2 do

for j:=i+1 to k-1 do

if vec[i].nume>vec[j].nume then

begin

art1:=vec[i];

vec[i]:=vec[j];

vec[j]:=art1;

end;

delay (20) ;

Gettime (h1,m1,s1,hund1) ;

if s1<s then

begin

s1:=s1+60;

tsec2:=s1-s;

end

else

tsec2:=s1-s;

if hund1<hund then

begin

hund1:=hund1+100;

tsut2:=hund1-hund;

end

else

tsut2:=hund1-hund;

ecran1;

end;

end;

op:=readkey;

until op='6';

end;

Din unitul liste.tpu:

procedure stergl;

var v:byte;

begin

repeat

cap4;

gotoxy (6,6) ;

write ('Numele salariatului :<string[20]> ') ;

valchar20 (num) ;

er:=false;

p:=sant1^.dr;

repeat

if num=p^.inf.nume then

begin

er:=true;

p^.st^.dr:=p^.dr;

p^.dr^.st:=p^.st;

dispose (p) ;

end;

p:=p^.dr;

until p=sant2;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

write ('Continuati ?<D/N> : ') ;readln (c) ;

until (c='n') or (c='N') ;

end;

procedure pontajl;

begin

repeat

cap3;

gotoxy (6,6) ;

write ('Numele salariatului :<string[20]> ') ;

valchar20 (num) ;

er:=false;

p:=sant1^.dr;

repeat

if num=p^.inf.nume then

repeat

er:=true;

write ('Nr. zilelor lucratoare ? <0..31> ') ;valmult031 (0,31,p^.inf.zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ? ') ;valmult031 (0,31,p^.inf.zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ? ') ;valmult031 (0,31,p^.inf.zile.zile_con_fplat) ;

until 31> (p^.inf.zile.zile_luc+p^.inf.zile.zile_con_med+p^.inf.zile.zile_con_fplat) ;

p:=p^.dr;

until p=sant2;

if not er then writeln ('Nume inexistent in baza de date !!! ') ;

write ('Continuati ?<D/N> : ') ;readln (c) ;

until (c='n') or (c='N') ;

end;

procedure lis;

var r:zil;

begin

reset (fis) ;

new (sant1) ;new (sant2) ;

sant1^.dr:=sant2;

sant2^.st:=sant1;

for i:=0 to filesize (fis) -1 do

begin

read (fis,art) ;

p:=sant2;

new (sant2) ;

p^.inf:=art;

p^.dr:=sant2;

sant2^.st:=p;

end;

close (fis) ;

repeat

case op of

'1':begin

clrscr;

textcolor (7) ;

reset (fis) ;

seek (fis,filesize (fis) ) ;

while r<>0 do

with art do

begin

clrscr;

gotoxy (25,2) ;

textcolor (RED) ;

writeln ('Introduceti datele noului salariat : ') ;

gotoxy (1,5) ;

textcolor (7) ;

write ('Marca salariatului ?<byte> ') ;valnumerby (marca) ;

write ('Numele salariatului ?<string[20]> ') ;valchar20 (nume) ;

write ('Compartimentul salariatului ?<string[15]> ') ;valchar15 (compartiment) ;

write ('Functia salariatului ?<string[15]> ') ;valchar15 (functie) ;

write ('Salariul angajatului ?<word> ') ;valnumerwo (salariu) ;

repeat

write ('Nr. zilelor lucratoare ?<0..31> ') ;valmult031 (0,31,zile.zile_luc) ;

write ('Nr. zilelor nelucratoare (concediu medical ?<0..31> ') ;valmult031 (0,31,zile.zile_con_med) ;

write ('Nr. zilelor nelucratoara (concediu fara plata ?<0..31> ') ;valmult031 (0,31,zile.zile_con_fplat) ;

until 31> (zile.zile_luc+zile.zile_con_med+zile.zile_con_fplat) ;

write ('Indicele de stare referitor la retinerile salariatului <1-DA,0-NU>? ') ;valmult031 (0,1,retineri.ind_stare) ;

if retineri.ind_stare=0 then

begin

retineri.suma_retin:=0;

retineri.rata_lunara:=0;

end

else

begin

write ('Unitatea de la care s-a facut imprumutul <CAR,CEC,BANCA,etc> ?<string[5]> ') ;valchar5 (retineri.unitati) ;

write ('Suma de retinut ?<word> ') ;valnumerwo (retineri.suma_retin) ;

write ('Rata lunara ?<word> ') ;valnumerwo (retineri.rata_lunara) ;

end;

writeln ('Data angajarii ? ') ;

write (' <1..31> Ziua : ') ;valmult031 (1,31,data.zi) ;

write (' <1..12> Luna : ') ;valmult031 (1,12,data.luna) ;

write (' <1939..1999>Anul : ') ;valmult3999 (1939,1999,data.an) ;

p:=sant2;

new (sant2) ;

p^.inf:=art;

p^.dr:=sant2;

sant2^.st:=p;

write (fis,art) ;

write ('Continuati <DA-1/NU-0> ? ') ;

valmult031 (0,1,r) ;

end;

close (fis) ;

ecran1;

end;

'2':begin

stergl;

ecran1;

end;

'3':begin

pontajl;

ecran1;

end;

'4':begin

fluturasil;

ecran1;

end;

'5':begin

GetTime (h,m,s,hund) ;

p:=sant1^.dr;

if p<>sant2 then

repeat

q:=p^.dr;

repeat

if p^.inf.nume>q^.inf.nume then

begin

art:=p^.inf;

p^.inf:=q^.inf;

q^.inf:=art;

end;

q:=q^.dr;

until q=sant2^.st;

p:=p^.dr;

until p=sant2^.st^.st;

delay (20) ;

Gettime (h1,m1,s1,hund1) ;

if s1<s then

begin

s1:=s1+60;

tsec3:=s1-s;

end

else

tsec3:=s1-s;

if hund1<hund then

begin

hund1:=hund1+100;

tsut3:=hund1-hund;

end

else

tsut3:=hund1-hund;

ecran1;

end;

end;

op:=readkey;

until op='6';

end;

ANALIZA SOLUTIEI:

Urmatoarele rezultate au fost obtinute in urma rularii pe un calculator cu urmatoarele caracteristici:

Procesor Pentium 200MMX

32 MB Ram

Turbo Profiler Version 2.2 Wed Jan 06 22:01:08 1999

Program: C:BPBINSTRUCTTURPRO.EXE

Execution Profile

Total time: 0.0215 sec

% of total: 83 %

Run: 1 of 1

Filter: All

Show: Time

Sort: Frequency

PROFILER.SORTMAS 0.0100 sec  56% | ** ** ** ** ***

PROFILER.SORTLIS 0.0045 sec  25% | ** ** ******

PROFILER.SORTFIS 0.0032 sec  17% | ** **

CRT.ASSIGNCRT 0.0000 sec <1% |

In urma copilarii am abtinut rezultatele:

Pentru PRINCIPA.PAS

45 lines

0.5 seconds

47536 bytes code

10120 bytes data

FISIER.PAS (varianta cu fisier) ;

687 lines

0.3 seconds

11695 bytes code

940 bytes data

LISTE.PAS (varianta cu liste dublu inlantuite) ;

290 lines

0.3 secondes

5909 bytes code

16 bytes data

MASIVE.PAS (varianta cu masive) ;

264 lines

0.3 seconds

5849 bytes code

7402 bytes data

CONCLUZII:

In urma rezultatelor obtinute putem trage concluzii referitoare la situatiile in care se recomanda folosirea uneia din cele trei structuri testate in programul analizat.

Astfel se observa ca cei mai mici timpi de executie si cel mic spatiu de memorare se obtin in cazul folosirii listelor ca modalitate de memorare .

In cazul in care pe structura respectiva se realizeaza multe stergeri se recomanda folosirea listelor caci daca s-ar folosi vectori sau fisiere o astfel de operatie ar atrage dupa sine realizarea a n-k operatii de deplasare la stanga ,unde n-dimensiunea masivului sau a fisierului iar k -pozitia elementului ce urmeaza a fi sters.

Observatiile de mai sus sunt valabile si in cazul operatiilor de adaugare numai ca in acest caz deplasarea se face pentru n-k elemente la dreapta.

Folosirea listelor nu implica existenta unor zone contigue de memorie ca in cazul masivelor si nici limitarea numarului de elemente memorate astfel in RAM.

Se recomanda folosirea vectorilor in cazul in care o anumita prelucrare nu necesita o parcurgere integrala a structurii ci multe accesari directe.

Cele mai slabe performante se obtin in cazul folosirii fisierului ca modalitate de memorare datorita numarului mare de operatii de I/O. Fisierele se folosesc atunci cand volumul de date este mare si nu pot fi stocate in memoria interna.

Nu poate fi data o solutie referitoare la o problema legata de modalitatea de memorare. Solutia optima trebuie sa tina cont problema in cauza si de cerintele acesteia, de contextul in care se rezolva.

BIBLIOGRAFIE:

ION IVAN, ROMICA ADAM ...STRUCTURI DE DATE;

ROBERT R. KORFHAGE ....PRINCIPLES OF DATA STRUCTURES

AND ALGORITHMS WITH PASCAL;

RANCEA D. ..........LIMBAJUL TURBO PASCAL;

KOTLER P. ...........MANGEMENTULMARKETINGULUI;

DOUGLAS MCGREGOR.....PARTEA UMANA A INTREPRINDERII