Structuri de Date

Tipuri Abstracte de Date în C

Un Tip Abstract de Date (TAD) este o colecţie de obiecte de un anumit tip, împreună cu

operaţiile asociate acestor obiecte. Un TAD folosit într-un program, este implementat

printr-un modul.

Orice modul este de sine stătător şi are o interfaţă bine definită, care lămureşte modul în

care este folosit modulul.

De ce sunt necesare TAD? Limbajele de programare posedă un mecanism de creere a

unor noi tipuri de date. Implementările acestor tipuri de nivel înalt, dispersate în

program, cresc complexitatea şi influienţează negativ asupra clarităţii. Dacă operaţiile

asupra acestor tipuri de nivel înalt nu se folosesc în mod consistent, atunci pot apare erori

în program.

Un TAD constă din:

· o mulţime S de structuri numite stări sau valori.

· un set de operaţii care pot fi aplicate stărilor din S.

Fiecare obiect sau instanţă a TAD are o stare. Operaţiile se clasifică în:

· operaţii de modificare a stării TAD şi

· funcţii de access, care furnizează informaţii asupra unui obiect al TAD, fără să

modifice starea.

Un TAD este o entitate matematică abstractă, cu existenţă independentă. TAD sunt

implementate prin module. Există o distincţie între TAD matematic şi implementarea sa

într-un limbaj de programare. Un singur TAD poate avea mai multe implementări

diferite.

Exemplu:Considerăm o coadă de întregi.In acest caz S este mulţimea tuturor secvenţelor

finite de întregi, iar operaţiile asociate sunt: Enq,Deq,Front,Q_Size, şi Q_Empty.

Proceduri de manipulare

Enq Inserează un întreg ca ultimă poziţie în coadă

Deq Şterge primul element din coadă

Funcţii de acces

Front furnizează întregul din vârful cozii

Q_Size furnizează numărul de întregi din coadă

Q_Empty testează dacă lungimea cozii este 0 sau nu

Alte exemple de structuri matematice care pot reprezenta TAD : mulţimi, grafuri, arbori,

matrice, polinoame, etc.

Mulţimea S este un set de obiecte matematice discrete de un tip oarecare.

Un obiect sau instanţă a TAD este asociat cu o istorie, de stări, provenite din aplicarea

operaţiilor TAD.

Pentru starea Empty operaţiile, Front şi Deq nu sunt definite. Trebuiesc stabilite

precondiţii pentru fiecare operaţie, indicând exact când se pot aplica aceste operaţii.

Astfel o precondiţie atât pentru Front cât şi pentru Deq este: ‘not Empty’.

Pentru ca un TAD să fie util, trebuie să fie îndeplinite precondiţiile pentru fiecare

operaţie. TAD bine definite indică clar precondiţiile pentru fiecare operaţie. TAD

documentează şi postcondiţiile, -condiţii care devin adevărate după executarea unei

operaţii. De exemplu, după executarea operaţiei Enq apare postcondiţia ‘not Empty’.

Operaţiile TAD pot fi gândite ca funcţii în sens matematic. Precondiţiile şi postcondiţiile

definesc domeniul şi codomeniul funcţiei. TAD este complet specificat numai în

momentul în care toate operaţiile au fost definite, cu toate precondiţiile şi postcondiţiile

implicate.

Implementarea TAD

Un Modul este o parte a programului izolată de restul programului printr-o interfaţă bine

definită. Modulele asigură servicii (funcţii, tipuri de date, ..) Clienţilor.

Un client poate fi orice (program, persoană, alt modul) care foloseşte servicile modulului.

Spunem că servicile se exportă clientului, sau sunt importate din modul.

Conceptul de modul implementează ideea ascunderii informaţiei, clienţii nu au acces la

detaliile implementării modulului. Clientul are acces la serviciile exportate prin interfaţă.

În general, există un modul separat pentru fiecare TAD.

În C fiecare TAD constă dintr-o structură. Utilizatorul TAD (clientul) primeşte o

referinţă (un pointer) la această structură. Pentru fiecare operaţie a TAD se defineşte o

funcţie, care conţine ca argument pointerul la TAD. Clientul nu poate folosi acest pointer

pentru a accesa direct câmpurile structurii, asigurându-se în acest mod ascunderea

informaţiei.

struct coada

Coada fata data

Q spate next

lung struct nod

Implementarea trebuie să conţină:

· O funcţie care crează un nou obiect (constructor)

Modul Utilizator

Interfaţă

· O funcţie care eliberează memoria asociată cu obiectul TAD când acesta nu se

mai foloseşte (destructor).

In C, se separă:

· implementarea modulului TAD într-un fişier .c care conţine structura concretă şi

definiţiile funcţilor,

· interfaţa modulului, într-un fişier .h care conţine definiri de tipuri şi prototipurile

funcţiilor exportate.