Structuri de Date

Curs2

1.TIPURI DE DATE

1.1. DATE SI INFORMATII

În practica se face deosebire între o data si o informatie. Exemplele oferite în cele mai multe cazuri sunt edificatoare. Exista si tendinte de a oferi definitii pentru date si pentru informatii. Dilemele când o informatie este considerata data si când o data este o informatie, sunt rezolvate pentru multi specialisti, dar ramân dileme pentru o alta categorie de specialisti.

Din punct de vedere al programatorului, ceea ce face obiectul prelucrarii sunt de fapt siruri de biti care reprezinta date sau informatii, functie de contextul în care sunt generate si de modul în care se interpreteaza rezultatele. Pentru a nu complica si mai mult problematica, se considera ca în activitatea de programare se opereaza cu date. Toate intrarile si iesirile programelor sunt date. Sistemele de prelucrare, însa sunt intitulate în continuare sisteme informationale sau sisteme informatice, în mod ornamental din punctul de vedere al programatorilor.

În realitate, atunci când acestea functioneaza corect, prelucreaza într-adevar informatii. Atunci când, însa, fluxurile sunt greoaie si determina un nivel de istorism costisitor, prelucrarile sunt ale unor date certe.

Pentru ca în literatura de specialitate capitolul detinut descrierii operanzilor – informatii sau date – se numeste STRUCTURI DE DATE, în continuare, nu se mai face deosebirea dintre informatie si data. Utilizatorii sunt aceia care decide daca ofera spre prelucrare informatii sau date si daca rezultatele prelucrarii sunt date sau sunt informatii.

1.2 CLASIFICARI ALE DATELOR

Exista numeroase puncte de vedere de a aborda gruparea datelor, fiecare constituindu-se într-un criteriu. Ceea ce este însa adevarat, este legat de faptul ca fiecarei date i se atasaza totalitatea atributelor ce rezulta din multitudinea de clasificari ce se iau în considerare.

a) Criteriul variabilitatii – grupeaza datele în:

- date constante, care nu se modifica într-un interval de timp sau pe durata executiei programului; în cazul în care pentru a face un program lizibil constantele sunt puse în corespondeta cu anumiti identificatori, în programe sunt vehiculati acestia din urma, formând constantele simbolice.

- date variabile, ale caror niveluri se modifica fie într-un interval de timp, fie pe parcursul executiei unui program; întotdeauna se vorbeste de o valoare initiala, valori intermediare si o valoare finala; numarul valorilor intermediare determina mecanismele necesare prelucrarilor, includerea în structuri repetitive sau stocarea lor în fisiere;

b) Criteriul compunerii – diferentiaza datele astfel:

- date simple sau elementare, fiecare având o anumita semnificatie si fiind independente de celelalte date care apar într-un context specificat; datele elementare se mai numesc atomi;

- date compuse sau structurate, formate din date elementare sau date la rândul lor structurate; fiecare componenta are o anumita pozitie în cadrul structurii si împreuna cu celelalte formeaza un întreg; între partile care alcatuiesc o data compusa exista legaturi în primul rând de continut si numai toate la un loc caracterizeaza un fenomen, un proces sau un individ dintr-o colectivitate: apartenenta si pozitia fiecarei componente se precizeaza explicit la descrierea datei structurate;

c) Criteriul semnificatiei continutului conduce la:

- date care fac obiectul operatiilor de prelucrare, adica participa ca operanzi în expresii, se initializeaza prin atribuiri sau operatii de intrare, se stocheaza pe suporti, se afiseaza sau se transmit ca parametri;

- date care permit adresarea operanzilor si care au valori cuprinse între limite precizate, care prin calcule de adrese localizeaza corect fie operanzi, fie alte date de adresare, fie functii de prelucrare;

- date ce efectueaza prelucrarea, care apar ca succesiuni de instructiuni direct executabile daca fisierul care le apartine este încarcat în memoria unui calculator si se comanda lansarea în executie a acestuia;

d) Criteriul naturii datelor – genereaza tipurile de date urmatoare:

- date de tip întreg, ale caror elemente apartin multimii Z;

- date de tip real, ale caror elemente apartin multimii R;

- date de tip complex, ale caror elemente apartin multimii C, iar coeficientii care desemneaza partea reala si partea imaginara apartin multimii R;

- date de tip boolean, ale caror elemente apartin multimii

{TRUE, FALSE} sau multimii {0, 1};

- date de tip caracter, ale caror elemente apartin multimii caracterelor ce sunt definite prin combinatie de biti la nivelul unui bait; din cele 256 de combinatii unele sunt grupate pentru litere, altele pentru cifre, altele pentru caractere speciale si pentru caractere de control; corespunzator, sunt definite date de tip alfabetic, de tip numeric, date de tip caractere de control etc.; aceste date au câte un singur element din multimea ce-i defineste tipul;

- date de tip sir de caractere – reprezinta o compunere prin concatenare a datelor de tip caracter; datele acestea au un delimitator al sfârsitului de sir, fie o constanta de tip întreg la început, precizând numarul de caractere care intra în alcatuirea sirului;

e) Criteriul construirii tipurilor conduce la:

- date de tip fundamental – ce apartin unui tip implementat în fiecare limbaj de programare, precum tipurile întreg, real, caracter, boolean, complex; programatorul are posibilitatea definirii constantelor simbolice si variabilelor proprii specificând tipurile fundamentale si alege prelucrarile compatibile acestora;

- date de tip derivat – care se obtin prin includerea în cadrul unor structuri a componentelor având unul din tipurile fundamentale implementate în limbaj; rezultatul obtinut este un tip de data derivat care se pune în corespondenta cu un identificator si care este folosit de programator pentru a defini variabilele în program având respectivul tip;

f) Criteriul dispunerii în memoria interna, grupeaza datele în:

- date dispuse în zone contigue – care permit localizarea uneia dintre ele cunoscând o adresa si o deplasare; în cazul în care zonele de memorie ocupate au aceeasi lungime, adresa fiecarei date se constituie ca termen al unei progresii aritmetice si este calculata cunoscând adresa primei date si pozitia în sirul datelor contigue a elementului cautat;

- date dispersate în memoria interna - se obtin în cazul alocarii dinamice a memoriei necesare, ceea ce impune stocarea si conservarea adresei zonei de memorie asociata fiecarei date; daca datele dispuse în zone contigue, au realizata proiectarea alocarii în faza de compilare, datelor dispersate li se aloca memorie efectiv în faza de executie si nu exista posibilitatea ca în mod direct sa se construiasca modele de calcul a adreselor fizice pe care datele le ocupa, mai ales daca alocarea memoriei este un proces ce depinde de testarea unor conditii din program;

g) Criteriul câmpului de actiune, împarte datele în:

- date cu caracter global – care se definesc o singura data, dar care sunt utilizate din orice punct al programului sau a functiilor si procedurilor care intra în componenta lui; aceste date se definesc si li se aloca memorie o singura data si au câmpul de actiune cel mai cuprinzator;

- date cu caracter local – sunt în fiecare procedura si li se aloca memorie dinamic, automat, la apelarea fiecarei proceduri sau functii; odata cu revenirea în secventa apelata deci la iesirea din functie sau din procedura, are loc eliberarea memoriei alocate (dealocarea memoriei); variabilele locale nu sunt folosite decât în procedura sau functia unde au fost definite;

- date de tip registru – au rolul de a pune la dispozitie programatorului în limbaje evoluate, accesul la registrele calculatorului; în cazul unei folosiri judicioase exista posibilitatea cresterii vitezei de prelucrare, iar în cazul folosirii abuzive a registrelor se obtine fenomenul invers;

h) Criteriul definirii domeniului presupune:

- date al caror domeniu este specificat prin limita inferioara, limita superioara si forma de prezentare generica a elementelor;

- date al caror domeniu este definit odata cu enumerare elementelor care îi formeaza.

i) Criteriul alocarii memoriei, grupeaza datele în:

- date statistice – calcule de alocare a memoriei se efectueaza în faza de compilare, iar înainte de executie, alocarea este efectiva;

- date dinamice a caror memorie este alocata si dealocata în timpul executiei programului, prin functii de biblioteca apelate.

Într-un program, o anumita data este astfel definita încât se încadreaza într-una din subgrupele fiecarui criteriu. Astfel, definirea: