STRUCTURI DE DATE

I. INTRODUCERE

Conceptul de structura de date

Orice algoritm primeste date de intrare, le prelucreaza si obtine date de iesire. In fiecare caz, datele de intrare, datele intermediare - cele create in timpul prelucrarii - si datele de iesire sunt structurate (organizate) intr-un anumit fel care corespunde intrarii, necesitatilor de prelucrare sau a celor de utilizare ulterioara.

Pentru a veni in sprijinul programatorilor, limbajele de programare evoluate (de exemplu Pascal, C) pun la dispozitia acestora posibilitatea organizarii datelor in anumite 'sabloane' numite tipuri de date. Mai precis, prin tip de date se intelege:

o multime de valori;

o regula de codificare a acestora;

o multime de operatii definite pe multimea datelor.

La randul lor, tipurile de date pot fi:

simple - descriu date care apartin unor multimi care nu sunt rezultate ca produs cartezian al altor multimi. Exemplu: integer.

structurate -descriu date care apartin unor multimi rezultate ca produs cartezian al altor multimi.

Exemple:

1. type rational=record

p,q:integer;

end

Prin tipul de mai sus se descrie structura unei variabile capabila sa retina numere rationale.

type vector-array [1..100] of real;

Fie b multimea valorilor care pot fi retinute de tipul real. Atunci o variabila de tip vector poate retine la un moment dat un element al multimii:

BxBxxB

de n ori

Practica impune utilizarea unor structuri ale datelor de o mare varietate, care nu se suprapun intotdeauna peste tipurile care pot fi descrise prin limbaj, de obicei obtinandu-se prin combinarea celor elementare .

Prin structura de date vom intelege un asamblu de date caracterizat prin relatiile existente intre ele si a operatiilor care pot fi efectuate cu datele respective.

Vom numi nod o variabila de un tip oarecare. De obicei, acest tip este structurat. Dupa caz, termenul nod poate fi inlocuit cu articol, inregistrare sau entitate.

In cele mai multe cazuri, 'ansamblul de date' care alcatuieste structura e alcatuit dintr-o multime cu un numar variabil de noduri.

2. Clasificarea structurilor de date :

I. Structuri de date elementare :

tablouri ( vectori, matrici, siruri de caractere )

inregistrare

multime

fisiere

II. Structuri de date dinamice :

structura de tip lista ( lista simplu inlantuita, dublu inlantuita, circulara, stiva, coada )

structura de tip arbore: arbori binari, arbori binari de cautare, arbori oarecare.

III. Structuri de tip graf :

grafuri neorientate

arbori

grafuri orientate

Observatie :

Algoritmii de prelucrare a structurilor de date vor fi implementati si prezentati in limbajul Pascal.

II. Structuri de date elementare :

In cele mai multe situatii reale, un program trebuie sa lucreze cu foarte multe date. Utilizand pentru aceste date numai tipuri simple, programul devine foarte greu de inteles si chiar de scris. O data complexa, care memoreaza mai mult decat o data simpla se numeste structura de date. Principalele structuri de date elementare (tipuri structurate de date) ale limbajului Pascal sunt (care au corespondent si alte limbaje de programare):

Tipul de date tablou (ARRAY)

Tipul de date sir de caractere (STRING)

Tipul de date inregistrare (RECORD)

Tipul de date multime (SET)

Tipul de date fisier (FILE)

Structura de tip tablou - se foloseste pentru pastrarea mai multor date de acelasi tip.

Un tablou este o multime finita si ordonata de elemente de acelasi tip caruia i se asociaza un nume. Un element al multimii este identificat prin intermediul numelui tabloului si a valorii unuia sau mai multor indici (tablourile putand fi unidimensionale sau multidimensionale) cu valori in subdomenii ale tipurilor ordinale (integer, char, boolean).

Pentru fiecare tip de date tablou utilizat intr-un program Pascal trebuie specificat domeniul de valori pentru fiecare indice si tipul elementelor tabloului (denumit si tip de baza).

In general, o declaratie de tip tablou are forma :

array lista_domenii_indici ] of tip_element

unde tip_element este tipul de baza iar lista_domenii_indici este o lista formata din elemente de forma : valoare minima .. valoare maxima sau numele unui tip ordinal. Prin tipul indicelui se fixeaza implicit si numarul componentelor tabloului.

Tablourile se pot clasifica in felul urmator:

Tablouri cu o singura dimensiune care se mai numesc si vectori

Tablouri cu doua dimensiuni care se mai numesc si matrici

Tablouri cu mai multe dimensiuni

a) Tablouri cu o singura dimensiune

Se declara in felul urmator:

type nume = array [tip indice] of Tip_element;

O astfel de descriere a tipului tablou poate sa apara intr-o declaratie explicita de tip (sectiunea TYPE). De exemplu declaratia:

type vector = array [1..10] of REAL;

defineste un tip tablou de 10 elemente de tip real, iar declaratia:

var A : vector; ,

reprezinta declaratia unei variabile de tipul vector care s-a definit mai sus. Limbajul Pascal permite si declaratii de tipuri anonime, cand declaratia tipului tablou se face direct in sectiunea VAR fara a mai atribui un nume tipului respectiv. De exemplu, declaratia de mai sus se poate face si astfel:

var A : array [1..10] of REAL;

Elementele unei variabile de tip tablou sunt tratate ca si variabile avand tipul de baza. Un element al unei variabile de tip tablou este identificat prin: nume[lista_valori_indici] unde nume este numele variabilei de tip tablou iar lista_valori_indici contine cate o expresie pentru fiecare indice, avand tipul compatibil cu cel al indicelui tabloului. De exemplu, elementele tabloului A se pot identifica prin A[1], A[2], , A[10].

Ca indice se poate folosi orice expresie. Aceasta se evalueaza in momentul selectarii elementului iar rezultatul trebuie sa fie de tipul indicelui. Domeniul ales pentru indici nu poate fi oricat de mare deoarece memoria sistemului de calcul este limitata. De exemplu, tipul indicelui poate fi orice tip ordinal cu exceptia tipului integer si word sau longint al caror domeniu de valori este prea mare pentru a putea fi domeniul indicilor unui tablou.

Ex: -notele unui student la cele 6 obiecte (datele sunt de acelasi tip )

7 10 9 10 4 10 tablou unidimensional

Note ( tablou )

Note[1] Note[2] Note[3] Note[4] Note[5] Note[6]

7 10 9 10 4 10

pozitie

Ex:a. Cum am defini o structura care sa pastreze notele timp de un an ( 12 examene )?

TYPE Vector = ARRAY [1..12] OF Byte;

VAR Note : Vector;

b. Cum am defini o structura care sa pastreze valorile reale inregistrate intr-un proces.

TYPE TVector = ARRAY [1..10000] OF Real;

VAR Valori: TVector;

Obs. In Pascal (si in alte limbaje de programare) trebuie avut grija sa nu depasim memoria disponibila atunci cand declaram tablouri. De exemplu, vectorul nu poate depasi 65535 de octeti (adica un segment de date)

b) Tablouri cu mai multe dimensiuni

In practica sunt situatii in care multimea de valori pe care o prelucram poate fi identificata prin doi sau mai multi indici. In acest caz putem folosi un tablou cu mai multe dimensiuni, in care elementele sunt identificate prin 2 sau mai multi indici.

In Pascal, declararea unui tip tablou cu doua dimensiuni (numit matrice) se face cu constructia.

var m : array[tip_indice_1,tip_indice_2] of tip_element;

var m : array[tip_indice_1,tip_indice_2] of tip_element;

iar accesul elementelor se face cu m[i,j];

Tabloul m fiind considerat o matrice, m[i,j] este elementul situat pe linia i si coloana j.

Prin generalizare daca in cazul tabloului m si tip_element este tot un tablou se ajunge la un tablou cu trei dimensiuni si prin generalizare la un tablou cu n dimensiuni care se declara in felul urmator:

type Tab_cu_n_dim = array [tip_ind_1,tip_ind_2,. . .tip_ind_n] of tip_element;

Exemplu:

Ex: - doresc sa pastrez notele pentru 3 studenti

1 2 3 4 5 6 coloane

7 10 9 10 4 5

10 9 10 10 5 5

7 7 8 5 6 6 Note[2, 4]

linii linie/coloana

Note - tablou bidimensional

Exemplu:

TYPE Tnote = ARRAY[1..30,1..12] OF Byte;

VAR Note : Tnote;

Ne intereseaza tehnicile de prelucrare cu aceasta structura de tip tablou.

Prelucrarea ( operarea ) cu structura de tip tablou:

Tablouri unidimensionale ( vector ):

Presupunem ca exista structura :

TYPE Vector = ARRAY [1..100] OF Byte;

VAR X: Vector;

N: Byte;

Vom prezenta cele mai importante operatii cu aceasta structura. In practica, aceste operatii se combina pentru a rezolva cerintele problemei :

a. Citirea vectorului ( tabloului):

PROCEDURE Citire (var X: Vector; var N : Byte);

VAR i : Byte;

BEGIN

Write( Numarul de componente :

Readln(n);

FOR i:=1 TO N DO

BEGIN

Write(' Dati componenta ',i,' :');

Readln(X[i]);

END;

END;

b.      Afisarea vectorului :

PROCEDURE Afisare ( X: Vector; N: Byte);

VAR i: Byte ;

BEGIN

Write('Vectorul este :');

FOR i:=1 TO N DO

Write(X[i],' ');

END

c.       Ordonarea vectorului :

c1. Metoda bulelor :

Ex: 7 3 5 9 2 - se iau primele 2 elemente, daca nu sunt ordonate

crescator se inverseaza ; avem 5 elemente si deci

3 7 5 9 2 5-1= 4 perechi de numere; in procedura vom avea

3 5 7 9 2 N elemente si N-1 perechi ;

3 5 7 2 9

3 5 2 7 9

3 2 5 7 9

3 5 7 9

PROCEDURE OrdonareaBS (var X: Vector; N:Byte);

VAR k, i, Aux : Byte;

BEGIN

REPEAT

k:=0;

FOR i:=1 TO N-1 DO

IF X[i] > X[i+1] THEN

BEGIN

Aux := X[i] ;

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

X[i+1] := Aux ;

k:=1;

end;

UNTIL k=0;

END;

c2. Metoda aducerii minimului pe prima pozitie (selectiei):

Ex: 7 3 5 9 2 - se determina minimul dintre cele cinci elemente

-minimul se inverseaza cu primul element

vectorul format din patru elemente: 3,5,9,7 are min. 3,

2 3 5 9 7

2 3 5 9 7 - pentru vectorul cu 5 elemente am calculat 5-1=4

2 3 5 7 9 minime

Pentru un vector cu N elemente vom avea (N-1) minime.

PROCEDURE OrdonareMin (var X: Vector; N: Byte);

VAR i, j, Poz, Min: Byte;

BEGIN

FOR i:=1 TO N-1 DO

BEGIN

Min := X[i];

Poz := i;

FOR j:=i TO N DO

IF Min>X[ j] THEN

BEGIN

Min := X[ j];

Poz := j;

END;

X[Poz] := X[i];

X[i = Min;

END;

END;

c3. Sortarea prin numarare: se ia fiecare element si se numara cati sunt mai mici decat el.

Ex: x= 7 3 5 9 2

y= 3 1 2 4 0 pozitia in vecror +1   

sunt 3 numere in vector mai mici decat 7 ( 7 se afla pe prima

pozitie ); numarul 3+1 va fi noua pozitie in vector a lui 7 ;

z = 2 3 5 7 9

PROCEDURE OrdonareNum( var x:Vector; N: Byte );

VAR y, z : Vector;

i,j : Byte;

BEGIN

FOR i 1 TO N DO

y[i] := 0;

FOR i 1 TO N DO

FOR j i+1 TO N DO

IF x[i]<x[ j] THEN

y[ j]:= y[ j] +1

ELSE

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

FOR i 1 TO N DO

z[y[i] +1] := x[i];

FOR i 1 TO N DO

x[i] :=z[i];

END;

d.      Contorizarea elementelor:

Ex: Sa se afle numarul elementelor mai mici decat 5 ( sunt doua ):

Note = 7 4 5 3 10

PROCEDURE Contorizare (x: Vector; N:Byte; var: Nr: Byte);

VAR i:Byte;

BEGIN

Nr := 0;

FOR i:=1 TO N DO

IF conditie THEN

Nr := Nr+1;

END;

Conditia pentru aflarea numarului de examene nepromovate Note[i] < 5.

e.       Insumarea elementelor :

Ex: Sa se afle media notelor unui student :

S= (7+4+5+3+10)/5 = 28/5 = 5.6

PROCEDURE Suma (x:Vector; N:Byte; var S:LongInt);

VAR i: Byte;

BEGIN

S 0;

FOR i 1 TO N DO

S:= S + x[i];

END;

f.       Determinarea minimului (maximului) din vector:

Ex: 7 4 5 3 10

Observatie: se foloseste o variabila suplimentara care retine Min .

Se ia - primul element 7, Min =7;

-al II-a element 4, se compara 4<7, inversam , Min=4, se retine acest minim;

- al III-a element 5, se compara 4<5, lasam Min=4;

-al IV-a element 3, se compara 3<4, inversam, Min=3, se retine acest minim;

-al V-a element 10, se compara 3<10, lasam Min=3;

Obs. Daca nu se poate cunoaste prima valoare pentru a o atribui variabilei min, se poate initializa cu o valoare mare care nu face parte din vector.

PROCEDURE Minim( x:Vector;N: Byte; var: Min: Byte);

VAR i: Byte;

BEGIN

Min := x[1];

For I 2 to n do

IF Min > x[i] then

Min := x[i];

END;

PROCEDURE Maxim (x:Vector;N: Byte; var: Max: Byte);

VAR i: Byte;

BEGIN

Max := x[1];

For I 2 to n do

IF Max < x[i] then

Max := x[i];

END;

g.      Cautarea unui element in vector:

PROCEDURE Cautare (x:Vector; N:Byte;y:Byte;var Gasit : boolean);

VAR i: Byte;

BEGIN

Gasit := False ;

FOR i 1 TO N DO

IF x[i]= y THEN

Gasit := True;

END;

PROCEDURE Cautare1 (x:Vector; N:Byte;y:Byte;var Poz : Byte);

VAR i: Byte;

BEGIN

Poz 0;

FOR i 1 TO N DO

IF x[i]= y THEN

Poz I;

END;

Prelucrarea matricilor se face similar, cu deosebirea ca vor fi necesare doua instructiuni for pentru a parcurge elementele (unul care parcurge liniile si altul care parcurge coloanele)