Structuri de Date și Algoritmi

1. Conceptul de dată

În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine noi informaţii despre fenomenele, procesele şi obiectele lumii reale.

O dată care apare ca o entitate indivizibilă atât din punct de vedere al informaţiei pe care o reprezintă cât şi din punct de vedere al procesorului care o prelucrează se numeşte dată elementară sau scalară.

O dată elementară, ca model de reprezentare a informaţiei, poate fi privită la nivel logic sau la nivelul calculatorului, din punct de vedere fizic.

Exemplu de dată elementară: x=8

Datele pot fi private din punct de vedere:

- logic, o dată poate fi definită ca un triplet de forma (identificator, atribute, valori)

- fizic, ca o zonă de memorie de o anumită lungime situată la o anumită adresă absolută în care sunt memorate în timp şi într-o formă specifică valorile date.

Identificatorul este un simbol asociat datei respective pentru a o putea distinge de alte date şi pentru a o putea referi în cadrul programului respectiv.

Atributele sunt proprietăţi ale datei şi precizează modul în care aceasta va fi tratată în cadrul procesului de prelucrare. Dintre atribute cel mai important este atributul de tip – defineşte apartenenţa datei la o anumită clasă de date, clasă definită după natura şi domeniul valorilor pentru care sunt precizate anumite operaţii specifice şi căreia îi este specific un anumit model de reprezentare internă.

Vom vorbi astfel de date de tip întreg, real, logic, şir de caractere, etc.

O dată care păstrează aceeasi valoare pe tot parcursul procesului de prelucrare se numeşte simplu constantă, în caz contrar se numeşte variabilă.

O dată constantă este identificată prin însuşi valoarea ei, altfel spus, o dată se identifică prin formas textuală a valorii. Tipul unei date, utilizate în cadrul unui program, este precizat în cadrul programului de prelucrare printr-o declaraţie de tip ce precede utilizarea respectivei constante, variabile sau funcţii. În afara atributului de tip, unei date i se pot asocia şi alte atribute. De exemplu: precizia reprezentării interne; încadrarea datei în zona afectată; modul de alocare al memoriei (static sau dinamic), valoarea iniţială.

Valorile datei pot fi precizate prin enumerare (tipul de enumerare în Pascal) sau printr-o proprietate comună. Valorile datei pot fi numere sau valori de adevăr sau şiruri, de biţi, etc.

2. Conceptul de structură de date

De foarte multe ori în realitate, datele apar sub forma unor colecţii de date asupra unor mulţimi de date pe care însă s-a definit o anumită organizare menită să faciliteze prelucrarea.

O colecţie de date pe care s-a definit o anumită organizare, o numită structură şi căreia îi este specific un anumit mod de selecţie şi identificare, poartă denumirea de structură de date.

Componetele unei structuri de date pot fi identificate prin nume (selecţia prin nume) sau prin ordinea pe care o ocupă în cadrul structurii în conformitate cu structura existentă.

Dacă accesul la o anumită componentă a unei structuri de date se poate face fără să se ţină seama de celelalte componente, vom spune că structura de date este cu acces direct. Un exemplu este cazul unui tablou de elemente la care se poate accesa oricare element prin poziţia sa în cadrul tabloului, de ex. A[5]

În schimb, dacă accesul la o componentă a structurii se face ţinând cont de alte câmpuri ale structurii în conformitate cu ordinea structuriii (printr-un proces de traversare) atunci vom spune că structura este cu acces secvenţial (este cazul unui fişier text).

Structurile de date pot fi create pentru memoria internă sau externă (fişiere pe disc magnetic sau banda magnetică; acestea poartă denumirea de fişier).

Structurile interne au un caracter de date temporare, ele dispar odată cu oprirea programului, încetarea activităţii de prelucrare, iar cele externe au un caracter de date permanente, care nu se pierd odată cu întreruperea tensiunii de alimentare.

Dacă pe lângă componentele structurii se înregistrează pe suport şi alte date suplimentare care să materializeze pe suport relaţia de ordonare, atunci structura de date respectivă este explicită, în caz contrar este implicită.

Structura de date de tip tablou este o structură implicită; listele liniare simplu înlănţuite sunt structuri explicite de date.

Asupra structurilor de date se pot efectua mai multe operaţii care se referă la valorile datei şi/sau la structură.

Cele mai frecvente operaţii pot fi:

- operaţia de creare care constă în memorarea pe suportul de memorie a structurii de date în forma sa iniţială

- operaţia de consultare care constă în accesul la elementele structurii în vederea prelucrării valorilor acestora

- operaţia de actualizare care constă în adăugarea de noi elemente, ştergerea elementelor care nu mai sunt necesare şi modificarea valorilor unor componente ale structurii

- operaţia de actualizare constă în modificarea structurii de date

- operaţia de sortare care presupune aranjarea, ordonarea elementelor unei structuri într-o anumită ordine precizată de valorile date

- operaţia de descompunere care constă în descompunerea unei structuri de date în două sau mai multe structuri

- operaţia de fuzionare – combinarea a două sau mai multe structuri la fel ordonate în una singură

- operaţia de copiere – realizarea unei copii a structurii de date, de regulă pe un alt suport de memorie.

Operaţiile care pot fi efectuate asupra unei structuri de date şi eficienţa cu care acestea pot fi utilizate depind în mare măsură de natura relaţiilor de ordonare şi modul în care acestea sunt ordonate pe suport. Din acest punct de vedere, operaţiile constituie element distinctiv al unei structuri de date, deci o proprietate a structurii.

Toate structurile de date la fel organizate şi pe care s-au definit aceleaşi operaţii, poarta numele de tip de structură de date. Dacă analizăm însă operaţiile care se efectuează asupra unei structuri de date, vom putea vedea că toate acestea se reduc la executarea, eventual repetată, a unui grup de operaţii specifice numite operaţii de bază.

Prin tip de structură de date vom înţelege o colecţie de date (ordonată) pe care s-a definit un grup de operaţii de bază cu o anumită semantică. Cele mai avansate metode de structurare de bază sunt tablourile şi structurile.

Structurile avansate de date nu se descriu ca structuri statice deoarece ele se generază în mod dinamic în timpul procesului de prelucrare – se vor numi structuri dinamice 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.