Structuri de Date

CURS 1. - STRUCTURI DE DATE

Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii.

I. INTRODUCERE

1. Conceptul de structură de date

Orice algoritm primeşte date de intrare, le prelucrează şi obţine date de ieşire. În fiecare caz, datele de intrare, datele intermediare - cele create în timpul prelucrării - şi datele de ieşire sunt structurate (organizate) într-un anumit fel care corespunde intrării, necesităţilor de prelucrare sau a celor de utilizare ulterioară.

Pentru a veni în sprijinul programatorilor, limbajele de programare evoluate (de exemplu Pascal, C) pun la dispoziţia acestora posibilitatea organizării datelor în anumite "şabloane" numite tipuri de date. Mai precis, prin tip de date se înţelege:

• o mulţime de valori;

• o regulă de codificare a acestora;

• o mulţime de operaţii definite pe mulţimea datelor.

La rândul lor, tipurile de date pot fi:

• simple - descriu date care apartin unor mulţimi care nu sunt rezultate ca produs cartezian al altor mulţimi. Exemplu: integer.

• structurate -descriu date care apartin unor mulţimi rezultate ca produs cartezian al altor mulţimi.

Exemple:

1. type rational=record

p,q:integer;

end

Prin tipul de mai sus se descrie structura unei variabile capabilă să reţina numere raţionale.

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

Fie B mulţimea valorilor care pot fi reţinute de tipul real. Atunci o variabilă de tip vector poate reţine la un moment dat un element al mulţimii:

BxBx...xB

de n ori

Practica impune utilizarea unor structuri ale datelor de o mare varietate, care nu se suprapun întotdeauna peste tipurile care pot fi descrise prin limbaj, de obicei obţinându-se prin combinarea celor elementare .

- Prin structură de date vom înţelege un asamblu de date caracterizat prin relaţiile existente între ele şi a operaţiilor care pot fi efectuate cu datele respective.

Vom numi nod o variabilă de un tip oarecare. De obicei, acest tip este structurat. După caz, termenul nod poate fi înlocuit cu articol, înregistrare sau entitate.

În cele mai multe cazuri, "ansamblul de date" care alcătuieşte structura e alcătuit dintr-o mulţime cu un număr variabil de noduri.

2. Clasificarea structurilor de date :

I. Structuri de date elementare :

- tablouri ( vectori, matrici, şiruri de caractere )

- înregistrare

- mulţime

- fişiere

II. Structuri de date dinamice :

- structura de tip listă ( listă simplu înlănţuită, dublu înlănţuită, circulară, stivă, coadă )

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

III. Structuri de tip graf :

- grafuri neorientate

- arbori

- grafuri orientate

Observaţie :

Algoritmii de prelucrare a structurilor de date vor fi implementaţi şi prezentaţi în limbajul Pascal.

II. Structuri de date elementare :

În cele mai multe situaţii reale, un program trebuie să lucreze cu foarte multe date. Utilizând pentru aceste date numai tipuri simple, programul devine foarte greu de înţeles şi chiar de scris. O dată complexă, care memorează mai mult decât o dată simplă se numeşte structură 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 înregistrare (RECORD)

- Tipul de date mulţime (SET)

- Tipul de date fişier (FILE)

1. Structura de tip tablou – se foloseşte pentru păstrarea mai multor date de acelaşi tip.

Un tablou este o mulţime finită şi ordonată de elemente de acelaşi tip căruia i se asociază un nume. Un element al mulţimii este identificat prin intermediul numelui tabloului şi a valorii unuia sau mai multor indici (tablourile putând fi unidimensionale sau multidimensionale) cu valori în subdomenii ale tipurilor ordinale (integer, char, boolean).

Pentru fiecare tip de date tablou utilizat într-un program Pascal trebuie specificat domeniul de valori pentru fiecare indice şi tipul elementelor tabloului (denumit şi tip de bază).

În general, o declaraţie de tip tablou are forma :

array [ lista_domenii_indici ] of tip_element