STRUCTURI DE DATE SI TIPURI DE DATE ABSTRACTE

Structuri de datE SI TIPURI DE DATE ABSTRACTE

Structuri de date fundamentale

Gruparea unor date sub un singur nume a fost necesara inca de la inceputurile programarii calculatoarelor. Prima structura de date folosita a fost structura de vector (tabel), utilizata in operatiile de sortare (de ordonare) a colectiilor si prezenta in primele limbaje de programare pentru aplicatii numerice (Fortran si Basic).

Un vector este o colectie de date de acelasi tip, in care elementele colectiei sunt identificate prin indici ce reprezinta pozitia relativa a fiecarui element in vector.

La inceput se puteau declara si utiliza numai vectori cu dimensiuni fixe, stabilite la scrierea programului si care nu mai puteau fi modificate la executie.

Introducerea tipurilor pointer si alocarii dinamice de memorie in limbajele Pascal si C a permis utilizarea de vectori cu dimensiuni stabilite si/sau modificate in cursul executiei programelor.

Gruparea mai multor date, de tipuri diferite, intr-o singura entitate, numita "articol" ("record") in Pascal sau "structura" in C a permis definirea unor noi tipuri de date de catre programatori si utilizarea unor date dispersate in memorie, dar legate prin pointeri : liste inlantuite, arbori si altele. Astfel de colectii se pot extinde dinamic pe masura necesitatilor si permit un timp mai scurt pentru anumite operatii, cum ar fi operatia de cautare intr-o colectie.

Limbajul C asigura structurile de date fundamentale (vectori, pointeri, structuri, uniuni) si posibilitatea de a defini nume pentru alte tipuri de date derivate din acestea.

Dintr-o perspectiva independenta de limbajele de programare se pot considera ca structuri de date fundamentale vectorii, listele inlantuite si arborii, fiecare cu diferite variante de implementare. Alte structuri de date se pot reprezenta prin combinatii de vectori, liste inlantuite si arbori. De exemplu, un tabel de dispersie ("Hash table") este realizat de obicei ca un vector de pointeri la liste inlantuite (liste de elemente sinonime). Un graf se reprezinta deseori printr-un vector de pointeri la liste inlantuite (liste de adiacente), sau printr-o matrice (un vector de vectori in C).

Clasificari ale structurilor de date

O structura de date este caracterizata prin relatiile dintre elementele colectiei si prin operatiile posibile cu aceasta colectie.

Literatura de specialitate actuala identifica mai multe feluri de colectii (structuri de date), care pot fi clasificate dupa cateva criterii.

Un criteriu de clasificare foloseste relatiile dintre elementele colectiei:

- Colectii liniare (secvente, liste), in care fiecare element are un singur succesor si un singur predecesor;

- Colectii arborescente (ierarhice), in care un element poate avea mai multi succesori (fii), dar un singur predecesor (parinte);

- Colectii neliniare generale, in care relatiile dintre elemente au forma unui graf general (un element poate avea mai multi succesori si mai multi predecesori).

Dictionarul Wikipedia imparte structurile de date in numai doua categorii:

- Structuri liniare

- Structuri de graf, care includ si arborii ca un caz particular.

Un alt criteriu poate fi modul de reprezentare a relatiilor dintre elementele

colectiei:

- Implicit, prin dispunerea lor in memorie (ca la vectori si matrice);

- Explicit, prin adrese de legatura (pointeri).

Un alt criteriu grupeaza diferitele colectii dupa rolul pe care il au in aplicatii si dupa operatiile asociate colectiei, indiferent de reprezentarea in memorie, folosind notiunea de tip abstract de date. Astfel putem deosebi :

- Structuri de cautare (multimi si dictionare abstracte);

- Structuri de pastrare temporara a datelor (containere, liste, stive, cozi s.a.)

Dupa numarul de aplicatii in care se folosesc putem distinge intre:

- Structuri de date de uz general ;

- Structuri de date specializate pentru anumite aplicatii (geometrice, cu imagini).

Uneori se face diferenta intre organizarea datelor in memoria interna si organizarea datelor pe suport extern ( a fisierelor si bazelor de date), datorita particularitatilor de acces la discuri fata de accesul la memoria interna. De exemplu, indexarea este o tehnica de regasire rapida si de ordonare a fisierelor mari dupa diferite chei, iar arborii B se folosesc pentru organizarea fisierelor index, dar in memoria interna se folosesc alte variante de arbori echilibrati.

O arhiva este un fisier care reuneste mai multe fisiere intr-o structura ierarhica, ce corespunde unor directoare si subdirectoare, structura fara echivalent in memoria interna.

Tot pe suport extern se practica si memorarea unor colectii de date fara o structura interna (date nestructurate), cum ar fi unele fisiere multimedia, mesaje transmise prin e-mail, documente, rapoarte s.a.

Tipuri abstracte de date

Un tip abstract de date este definit numai prin operatiile asociate (prin modul de utilizare), fara referire la modul concret de implementare (cu elemente consecutive sau cu pointeri sau alte detalii de memorare).

Mai nou, un grup abstract de date (pentru care nu ne intereseaza legaturile dintre date si modul de memorare) se numeste colectie (in Java) sau container (in biblioteca de clase STL din C++).

Pentru programele nebanale este utila o abordare in (cel putin) doua etape:

- o etapa de conceptie (de proiectare), care include alegerea colectiilor de date si algoritmilor folositi;

- o etapa de implementare (de codificare), care include scrierea de cod si folosirea unor functii de biblioteca.

In faza de proiectare nu trebuie stabilite structuri fizice de date si trebuie gandita aplicatia in termeni de tipuri abstracte de date. Putem decide ca avem nevoie de un dictionar si nu de un tabel de dispersie, putem alege o coada cu prioritati abstracta si nu un vector heap sau un arbore ordonat, s.a.m.d.

In faza de implementare putem decide ce implementari alegem pentru tipurile abstracte decise in faza de proiectare. Ideea este de a separa interfata (modul de utilizare) de implementarea unui anumit tip de colectie.

De exemplu, verificarea formala a unui fisier XML in sensul utilizarii corecte a marcajelor ("tags") foloseste o stiva de marcaje, deoarece fiecare pereche de marcaje poate include alte perechi de marcaje, pe orice nivel de adancime. Continutul unui document XML se poate reprezenta in memorie ca un arbore multicai. Exemplele care urmeaza ilustreaza o utilizare corecta si apoi o utilizare incorecta a marcajelor:

<stud>

<nume>POPA</nume>

<prenume>ION</prenume>

<medie> 8.50</medie>

</stud>

<stud><nume>POPA<prenume> ION </nume> </prenume> <medie>8.50</medie>

Algoritmul de verificare a unui fisier XML daca este corect format ("well-formed") pune intr-o stiva fiecare marcaj de inceput (<stud>, <nume>,), iar la citirea unui marcaj de sfarsit (</stud>, </nume>,) verifica daca in varful stivei este marcajul de inceput pereche si il scoate din stiva :

initializare stiva

repeta pana la sfarsit de fisier

extrage urmatorul marcaj

daca marcaj de inceput

pune marcaj in stiva

daca marcaj de sfarsit

daca in varful stivei este perechea lui

scoate marcajul din varful stivei

altfel

eroare de utilizare marcaje

daca stiva nu e goala

eroare de utilizare marcaje

Pentru simplificare am eliminat marcajele singulare, care nu se folosesc in perechi, si marcajele cu atribute.

In aceasta faza nu ne intereseaza daca stiva este realizata ca vector sau ca lista inlantuita, daca ea contine pointeri generici sau de un tip particular.

Conceptul de tip abstract de date are un corespondent direct in limbajele orientate pe obiecte, si anume o clasa abstracta sau o interfata. In limbajul C putem folosi acelasi nume pentru tipul abstract si aceleasi nume de functii; inlocuirea unei implementari cu alta poate insemna un alt fisier antet (cu definirea tipului) si o alta biblioteca de functii, dar fara modificarea aplicatiei care foloseste tipul abstract.

Un tip de date abstract poate fi implementat prin mai multe structuri fizice de date.

De exemplu, o multime este un tip abstract de date definit ca o colectie de valori distincte si avand ca operatie specifica verificarea apartenentei unei valori la o multime (deci o cautare in multime dupa valoare ). In plus, exista operatii generale cu orice colectie : initializare, adaugare element la o colectie, eliminare element din colectie, afisare sau parcurgere colectie, s.a.

Trebuie spus ca nu exista un set de operatii unanim acceptate pentru fiecare tip abstract de date, iar aceste diferente sunt uneori mari, ca in cazul tipului abstract 'lista'. Aceste diferente in definirea tipurilor abstracte se pot vedea si din compararea bibliotecilor de clase STL (C++) si Java SDK.

In prezent sunt recunoscute cateva tipuri abstracte de date, definite prin operatiile specifice si modul de utilizare: multimi, colectii de multimi disjuncte, liste generale, liste particulare (stive,cozi), cozi ordonate (cu prioritati), dictionare. Diferitele variante de arbori si de grafuri sunt uneori si ele considerate ca tipuri abstracte.

Aceste tipuri abstracte pot fi implementate prin cateva structuri fizice de date sau combinatii ale lor: vectori extensibili dinamic, liste inlantuite, matrice, arbori binari, arbori oarecare, vectori 'heap', fiecare cu variante.

Conceperea unui program cu tipuri abstracte de date permite modificarea implementarii colectiei abstracte (din motive de performanta, de obicei), fara modificarea restului aplicatiei.

Ca exemplu de utilizare a tipului abstract dictionar vom considera problema determinarii frecventei de aparitie a marcajelor intr-un fisier XML. Un dictionar este o colectie de perechi cheie-valoare, in care cheile sunt unice (distincte). In exemplul nostru cheile sunt sirurile folosite ca marcaje, iar valorile asociate sunt numere intregi ce arata de cate ori apare fiecare marcaj in fisier. Daca fisierul contine date despre 10 studenti dintr-o grupa, atunci rezultatele ar putea fi urmatoarele:

grupa 1

stud 10

nume 10

prenume 10

medie 10

Aplicatia poate fi descrisa astfel:

initializare dictionar

repeta pana la sfarsit de fisier

extrage urmatorul marcaj

daca marcajul exista in dictionar

aduna 1 la numarul de aparitii

altfel

pune in dictionar marcaj cu numar de aparitii 1

afisare dictionar

Implementarea dictionarului de marcaje se poate face printr-un tabel hash daca fisierele sunt foarte mari si sunt necesare multe cautari, sau printr-un arbore binar de cautare echilibrat daca se cere afisarea sa numai in ordinea cheilor (a marcajelor), sau printr-un vector (sau doi vectori) daca se cere afisarea sa ordonata si dupa valori (dupa numarul de aparitii al fiecarui marcaj).

Existenta unor biblioteci de clase predefinite pentru colectii de date reduce problema implementarii structurilor de date la alegerea claselor celor mai adecvate pentru aplicatia respectiva si conduce la programe compacte si fiabile. 'Adecvare' se refera aici la performantele cerute si la particularitatile aplicatiei: daca se cere mentinerea colectiei in ordine, daca se fac multe cautari, daca este o colectie statica sau volatila, etc.

Eficienta structurilor de date

Unul din argumentele care sustin studiul structurilor de date este acela ca alegerea unei structuri nepotrivite de date poate influenta negativ eficienta unor algoritmi, sau ca alegerea unei structuri adecvate poate reduce complexitatea in timp a unor algoritmi (impreuna cu alegerea unui algoritm eficient).

De exemplu, algoritmii Prim sau Kruskal pentru determinarea unui arbore de acoperire de cost minim al unui graf cu costuri au o complexitate care depinde de structurile de date folosite.

Influenta alegerii structurii de date asupra timpului de executie a unui program sta si la baza introducerii tipurilor abstracte de date: un program care foloseste tipuri abstracte poate fi mai usor modificat prin alegerea unei alte implementari a tipului abstract folosit, pentru imbunatatirea performantelor.

Problema alegerii unei structuri de date eficiente pentru un tip abstract nu are o solutie unica, desi exista anumite recomandari generale in acest sens. Sunt mai multi factori care pot influenta aceasta alegere si care depind de aplicatia concreta.

Astfel, o structura de cautare poate sau nu sa pastreze si o anumita ordine intre elementele colectiei, ordine cronologica sau ordine determinata de valorile memorate. Daca nu conteaza ordinea atunci un tabel de dispersie ("hash") este alegerea potrivita, daca ordinea valorica este importanta atunci un arbore binar cu autoechilibrare este o alegere mai buna, iar daca trebuie pastrata ordinea de introducere in colectie, atunci un tabel hash completat cu o lista coada este mai bun.

In general un timp mai bun se poate obtine cu pretul unui consum suplimentar de memorie; un pointer in plus la fiecare element dintr-o lista sau dintr-un arbore poate reduce durata anumitor operatii si/sau poate simplifica programarea lor.

Frecventa fiecarui tip de operatie poate influenta de asemenea alegerea structurii de date; daca operatiile de stergere a unor elemente din colecie sunt rare sau lipsesc, atunci un vector este preferabil unei liste inlantuite, de exemplu. Pentru grafuri, alegerea intre o matrice de adiacente si o colectie de liste de adiacente tine seama de frecventa anumitor operatii cu graful respectiv; de exemplu, obtinerea grafului transpus sau a grafului dual se face mai repede cu o matrice de adiacente.

In fine, dimensiunea colectiei poate influenta alegerea structurii adecvate: o structura cu pointeri (liste de adiacente pentru grafuri, de exemplu) este buna pentru o colectie cu numar relativ mic de elemente si care se modifica frecvent, iar o structura cu adrese succesive (o matrice de adiacente, de exemplu) poate fi preferabila pentru un numar mare de elemente.

Eficienta unei anumite structuri este determinata de doi factori: memoria ocupata si timpul necesar pentru operatiile frecvente. Mai des se foloseste termenul de "complexitate", cu variantele "complexitate temporala" si "complexitate spatiala".

Complexitatea temporala a unui algoritm se estimeaza de obicei prin timpul maxim necesar in cazul cel mai nefavorabil, dar se poate tine seama si de timpul mediu si/sau de timpul minim necesar. Pentru un algoritm de sortare in ordine crescatoare, de exemplu, cazul cel mai defavorabil este ca datele sa fie ordonate descrescator (sau crescator pentru metoda "quicksort"). Cazul mediu este al unui vector de numere generate aleator, iar cazul minim al unui vector deja ordonat.

In general, un algoritm care se comporta mai bine in cazul cel mai nefavorabil se comporta mai bine si in cazul mediu, dar exista si exceptii de la aceasta regula cum este algoritmul de sortare rapida QuickSort, care este cel mai bun pentru cazul mediu (ordine oarecare in lista initiala), dar se poate comporta slab pentru cazul cel mai nefavorabil (functie si de modul de alegere a elementului pivot).

Pentru a simplifica compararea eficientei algoritmilor se apreciaza volumul datelor de intrare printr-un singur numar intreg N, desi nu orice problema poate fi complet caracterizata de un singur numar. De exemplu, in problemele cu grafuri conteaza atat numarul de noduri din graf cat si numarul de arce din graf, dar uneori se considera doar numarul arcelor ca dimensiune a grafului (pentru cele mai multe aplicatii reale numarul de arce este mai mare ca numarul nodurilor).

O alta simplificare folosita in estimarea complexitatii unui algoritm considera ca toate operatiile de prelucrare au aceeasi durata si ca putem numara operatii necesare pentru obtinerea rezultatului fara sa ne intereseze natura acelor operatii. Parte din aceasta simplificare este si aceea ca toate datele prelucrate se afla in memoria interna si ca necesita acelasi timp de acces.

Fiecare algoritm poate fi caracterizat printr-o functie ce exprima timpul de rulare in raport cu dimensiunea n a problemei; aceste functii sunt mai greu de exprimat printr-o formula si de aceea se lucreaza cu limite superioare si inferioare pentru ele.

Pentru estimarea complexitatii algoritmilor in cazul cel mai defavorabil se folosesc trei notatii:

Litera O mare exprima o limita superioara pentru functia f(n);

Litera sigma mare exprima o limita inferioara pentru f(n);

Litera teta mare exprima o limita superioara si o limita inderioara pentru f(n).

Se spune ca un algoritm are complexitatea de ordinul lui f(n) si se noteaza O(f(n)) daca timpul de executie pentru n date de intrare T(n) este marginit superior de functia f(n) astfel:

T(n) = O(f(n)) daca T(n) <= k * f(n) pentru orice n > n0

unde k este o constanta a carei importanta scade pe masura ce n creste.

Relatia anterioara spune ca rata de crestere a timpului de executie a unui algoritm T(n) in raport cu dimensiunea n a problemei este inferioara ratei de crestere a functiei f(n). De exemplu, un algoritm de complexitate O(n) este un algoritm al carui timp de executie creste liniar (direct proportional) cu valoarea lui n.

Majoritatea algoritmilor utilizati in practica au complexitate polinomiala, deci f(n) = n^k. Un algoritm liniar are complexitate O(n), un algoritm patratic are complexitate O(n²), un algoritm cubic are ordinul O(n³) s.a.m.d.

Diferenta in timpul de executie dintre algoritmii de diferite complexitati este cu atat mai mare cu cat n este mai mare. Tabelul urmator arata cum creste timpul de executie in raport cu dimensiunea problemei pentru cateva tipuri de algoritmi.

n O(log(n)) O(n) O(n*log(n)) O(n²) O(n³) O(2ⁿ)

10 2.3 10 23 100 1000 10e3

20 3.0 20 60 400 8000 10e6

30 3.4 30 102 900 27000 10e9

40 3.7 40 147 1600 64000 10e12

50 3.9 50 195 2500 125000 10e15

Complexitatea unui algoritm este deci echivalenta cu rata de crestere a timpului de executie in raport cu dimensiunea problemei.

Algoritmii O(n) si O(n log(n)) sunt aplicabili si pentru n de ordinul 10⁹. Algoritmii O(n²) devin nepracticabili pentru n >10⁵, algoritmii O(n!) nu pot fi folositi pentru n > 20, iar algoritmii O(2ⁿ) sunt inaplicabili pentru n >40.

Cei mai buni algoritmi sunt cei logaritmici, indiferent de baza logaritmului.

Operatiile asociate unei structuri de date sunt algoritmi, mai simpli sau mai complicati, iar complexitatea lor temporala este estimata prin notatia O(f(n)) care exprima rata de crestere a timpului de executie in raport cu dimensiunea n a colectiei pentru cazul cel mai nefavorabil.

Daca durata unei operatii nu depinde de dimensiunea colectiei, atunci se spune ca acea operatie are complexitatea O(1); exemple sunt operatiile de introducere sau de scoatere din stiva, care opereaza la varful stivei si nu depind de adancimea stivei. Un timp constant are si operatia de apartenenta a unui element la o multime realizata ca un vector de biti, deoarece se face un calcul pentru determinarea pozitiei elementului cautat si o citire a unui bit (nu este o cautare prin comparatii repetate).

Operatiile de cautare secventiala intr-un vector neordonat sau intr-o lista inlantuita au o durata proportionala cu lungimea listei, deci complexitate O(n) sau liniara.

Cautarea binara intr-un vector ordonat si cautarea intr-un arbore binar ordonat au o complexitate logaritmica de ordinul O(log₂n), deoarece la fiecare pas reduce numarul de elemente cercetate la jumatate. Operatiile cu vectori heap si cu liste skip au si ele complexitate logaritmica (logaritm de 2). Cu cat dimensiunea colectiei n este mai mare, cu atat este mai mare castigul obtinut prin cautare logaritmica in raport cu cautarea liniara.

Practic nu exista operatii cu colectii care sa aiba complexitate mai mare ca O(n), daca nu socotim si sortarea printre aceste operatii.