Tipul abstract multime. Implementare prin vectori.
Tipuri de date abstracte si strucuri de date fizice
Un tip abstract de date (TDA) este definit în principal prin modul cum este utilizat, deci prin operatiile specifice asociate acelui tip, independent de modul concret de reprezentare în memorie. Notiunea de TDA a apãrut în urma observatiilor cã structuri de date foarte diferite (ca reprezentãri si programare) pot îndeplini aceleasi functii într-o aplicatie si pot fi substituite una prin alta fãrã sã afecteze restul aplicatiei (dar pot influenta performantele ).
Tipul abstract multime ("Set") poate fi definit ca o colectie de valori distincte (toate de acelasi tip) cu urmãtoarele operatii asociate:
- Creare multime vidã (initializare multime vidã) : initS ;
- Test de multime vidã : emptyS ;
- Verificarea apartenentei unei valori la o multime: containsS ;
- Adãugarea unei valori date la o multime: addS ;
- Eliminarea unei valori date dintr-o multime: removeS ;
- Afisarea continutului unei multimi: printS ;
- Determinarea dimensiunii (cardinalului) unei multimi: sizeS ;
Fatã de alte colectii abstracte, multimea are drept caracteristicã definitorie cãutarea unui element dupã continut, cãutare care este o operatie frecventã si trebuie sã se facã cât mai rapid. De aceea, multimea este o structurã de cãutare ce contine valori individuale, spre deosebire de structura de dictionar care este o structurã de cãutare ce contine perechi cheie-valoare.
Tipul abstract multime poate fi implementat prin diverse structuri de date fizice: vect 23423c25x ori, liste înlãntuite, arbori binari, tabele de dispersie ("hashtable"), vectori de biti.
In esentã, structurile de date fizice (fundamentale) sunt de douã tipuri mari:
- Structuri cu date memorate la adrese consecutive ( Vectori)
- Structuri cu date dispersate în memorie, dar legate prin pointeri.
Pentru a exemplifica utilizarea unei multimi vom considera problema extragerii cuvintelor distincte dintr-un fisier text. Fiecare cuvânt extras din text este cãutat în tabelul de cuvinte; dacã este gãsit atunci nu se mai adaugã în tabel; dacã nu este gãsit atunci se adaugã noul cuvânt la sfârsitul tabelului. Un cuvânt este un sir de caractere separat prin spatii albe de alte cuvinte.
Tabelul de cuvinte este de tipul abstract multime, pentru cã asigurã unicitatea elementelor memorate în multime. Elementele multimii pot fi chiar cuvintele extrase din text sau pointeri la cuvintele citite si memorate în heap. In varianta urmãtoare se memoreazã adresele cuvintelor (alocate dinamic) si presupunem cã existã functii pentru operatiile necesare cu multimi, fãrã sã ne intereseze modul de implementare al tipului multime "Set" :
void main ()
printS (a); // afiseaza cuvinte din multime
printf ( "%d \n", sizeS(a)); // afiseaza numarul de cuvinte
Modul de implementare a tipului "Set" este "ascuns" în functiile initS, addS, printS, sizeS iar modificarea sa nu va produce modificãri în restul aplicatiei. Prin definirea de functii specifice unui tip abstract de date se realizeazã separarea algoritmului specific aplicatiei de algoritmii specifici structurilor de date utilizate.
Multimi realizate ca vectori cu dimensiune fixã
Structura de vector ('Array') prezintã câteva mari avantaje fatã de alte structuri de date (liste înlãntuite, arbori, s.a.):
- Nu trebuie memorate decât datele necesare aplicatiei, nu si adrese de legãturã (pointeri);
- Este posibil accesul direct la orice element dintr-un vector prin indici;
- Programarea operatiilor de acces la elementele unui tablou este foarte simplã.
- Cãutarea într-un vector ordonat este foarte eficientã (prin cãutare binarã), dar o listã ordonatã nu permite reducerea timpului de cãutare.
Atunci când este posibilã estimarea dimensiunii maxime a unui vector putem folosi un vector cu dimensiune constantã, stabilitã la scrierea programului si care nu se mai modificã ulterior. Fiecare functie care lucreazã cu o multime trebuie sã primeascã un vector si dimensiunea sa. Pentru a reduce numãrul de argumente se practicã gruparea vectorului si a dimensiunii sale efective într-o structurã. Exemple de functii pentru operatii cu o multime vector de dimensiune fixã.
#define MAXW 1000
// definire tip multime si tip adresa multime
typedef struct set, * Set;
// initializare vector
void initS ( Set p)
// afisare vector
void printS ( Set p)
// dimensiune vector
int sizeS (Set * p)
// verificare apartenenta la multime
int containsS (Set p, char * w)
// adaugare la vector
void addS ( Set p, char* w)
Multimi realizate ca vectori extensibili
De obicei se considerã cã utilizarea vectorilor de date are ca dezavantaj dimensionarea constantã, acoperitoare. Aceastã afirmatie este adevãratã numai pentru vectori cu dimensiune fixatã la scrierea programului dar nu si pentru vectori alocati dinamic, în cursul executiei.
In functie de specificul aplicatiei putem avea douã situatii de alocare dinamicã pentru vectori:
- Dimensiunea vectorului este cunoscutã de program înaintea valorilor ce trebuie memorate în vector si aceastã dimensiune nu se mai modificã pe durata executiei programului; în acest caz este suficientã o alocare initialã de memorie pentru vector (un singur apel "malloc" sau "calloc").
- Dimensiunea vectorului nu este cunoscutã de la început sau numãrul de componente poate creste (sau scade) pe mãsurã ce programul evolueazã; în acest caz este necesarã extinderea dinamicã a vectorului (se apeleazã repetat "realloc").
In Limbajul C nu existã nici o diferentã între utilizarea unui vector alocat dinamic si utilizarea unui vector cu dimensiune constantã, iar functia "realloc" simplificã extinderea unui vector dinamic cu pãstrarea datelor memorate.
Când dimensiunea efectivã ajunge egalã cu capacitatea curentã a vectorului, atunci devine necesarã extinderea vectorului. Extinderea se poate face cu o valoare constantã, cu un procent din dimensiunea curentã sau prin dublarea dimensiunii curente.
Structura "Vector" trebuie redefinitã pentru a include si capacitatea vectorului, pe lângã numãrul de elemente introdus efectiv în vector. Mãrirea capacitãtii vectorului se poate 'încapsula' în funcita de adãugare la vector, fãrã ca ea sã fie vizibilã pentru programul care foloseste functia. Urmeazã modificãrile aduse functiilor prezentate anterior (nu toate functiile se modificã):
#include <stdlib.h> // ptr malloc si realloc
#define INC 100 // increment de extindere vector
typedef struct set, *Set;
// initializare multime vida
void initS ( Set p)
// adaugare la vector
void addS ( Set p, char* w)
p->v[p->n]= w; // adauga la sfirsitul vectorului
++ p->n;
}
Uneori este utilã o variantã a functiei de initializare care sã primeascã ca al doilea argument capacitatea initialã a vectorului, care poate rãmâne neschimbatã pe parcursul programului.
Implementarea unei multimi printr-un vector are câteva dezavantaje:
- Cãutarea într-un vector neordonat necesitã un timp direct proportional cu dimensiunea vectorului desi existã si alte solutii de implementare cu timpi de cãutare mai buni.
- Eliminarea unui element din multime necesitã deplasarea tuturor elementelor care urmeazã celui eliminat.
- Operatiile cu douã multimi (intersectie, reuniune, diferentã) sunt consumatoare de timp pentru cã folosesc repetat operatia de cãutare.
O utilizare frecventã a unei multimi vector este pentru a tine evidenta elementelor dintr-o colectie care au fost prelucrate pânã la un moment dat; de exemplu, la explorarea grafurilor în adâncime se foloseste un vector de noduri deja vizitate, pentru a evita vizitarea lor repetatã.
O multime de întregi cu valori între 0 si un întreg dat se poate reprezenta si printr-un vector de biti, în care bitul din pozitia k este 1 daca multimea contine valoarea k si este 0 daca multimea nu contine valoarea k. Vectorul de biti este de fapt un vector de numere întregi, de orice lungime sau chiar o singurã variabilã de tip "int" sau "long", dacã multimea are maxim 16 (32) de elemente. Pentru o multime de maxim 256 de numere înre 0 si 255 putem folosi un vector de 16 întregi sau un vector de 32 de caractere sau un vector de 8 intregi lungi.
Avantajele folosirii unui vector de biti pentru o multime de întregi sunt: spatiu de memorie redus, timp neglijabil pentru operatiile de apartenentã la o multime (care nu este o cãutare, deci nu este un ciclu de operatii repetate) si pentru operatii cu douã multimi (intersectie, reuniune, diferentã). Exemple de functii pentru operatii cu multimi de biti:
#define DIM 16
typedef int Set[DIM]; // maxim 256 de elemente in multime
void addS (Set m,int x)
int containsS (Set m, int x)
Vectori cu date de un tip neprecizat
O parte din functiile pentru operatii cu multimi vectori scrise anterior depind de tipul datelor memorate în multime : operatia de cãutare în multime, operatia de afisare s.a.
O multime poate contine valori numerice de diferite tipuri si lungimi sau siruri de caractere sau alte tipuri de date agregat (structuri), sau pointeri (adrese). Ideal ar fi ca operatiile cu un anumit tip de colectie sã poatã fi scrise ca functii generale, adaptabile pentru orice tip de date memorate în colectie. Acest obiectiv este de dorit mai ales pentru colectii de date care necesitã algoritmi mai complicati, pentru a evita rescrierea functiilor pentru fiecare nou tip de date folosit.
O colectie ce poate contine date de orice tip este o colectie genericã, iar algoritmii asociati unei colectii generice sunt în general algoritmi generici.
Prima solutie pentru un vector generic foloseste tipuri neprecizate pentru elementele colectiei:
// multimi de elemente de tipul T
typedef int T; // tip componente multime
typedef struct set, * Set;
// adaugare la vector
void addS ( Set p, T w)
p->v[p->n ++]= w; // adauga la sfirsitul vectorului
}
Inlocuirea tipului "int" cu un alt tip numeric necesitã numai modificarea declaratiei "typedef", dar compararea, afisarea si alte operatii depind de tipul T.
Operatiile de citire-scriere a unor elemente din multime depind de asemenea de tipul T , dar ele fac parte în general din programul de aplicatie. Pentru a scrie operatii cu colectii de date de orice tip T avem mai multe posibilitãti:
a) Utilizarea unor functii de comparare cu nume predefinite, care vor fi rescrise în functie de tipul T al elementelor multimii. Exemplu:
typedef char * T;
int comp (T a, T b )
int containsS ( Set p, T x)
b) Transmiterea functiilor de comparare, atribuire, s.a ca argumente la functiile care le folosesc (fãrã a impune nume fixe acestor functii). Exemplu:
typedef (int *) Fcmp ( T a, T b) ; // tip functie de comparare
int containsS ( Set a, T x, Fcmp cmp )
Solutia cu tipuri neprecizate pentru colectii generice conduce la programe mai usor de înteles dar presupune cã programatorul aplicatiei dispune de codul sursã al functiilor folosite. Aceastã idee a fost extinsã în C++ prin folosirea de tipuri parametrizate ("templates") în functii si în clase.
Vectori de pointeri la un tip neprecizat
O a doua solutie pentru o colectie genericã este o colectie de pointeri la orice tip (void *), care vor fi înlocuiti cu pointeri la datele folosite în fiecare aplicatie. Si în acest caz functia de comparare trebuie transmisã ca argument functiilor de inserare sau de cãutare în colectie. Avantajul asupra solutiei cu tip neprecizat T este acela cã functiile pentru operatii cu colectii pot fi compilate si puse într-o bibliotecã si nu este necesar codul sursã. Utilizarea acestor functii este ceva mai dificilã.
Exemplu de vector generic cu pointeri:
// Operatii generale cu un vector de pointeri
typedef void * Ptr;
typedef int (* Fcmp) (Ptr,Ptr); // tip functie de comparare
typedef void (* Fprnt) (Ptr); // tip functie de afisare
// definire tip vector
#define INC 100
typedef struct set, *Set;
// initializare multime vector
Set initS()
// afisare multime
void printS ( Set a, Fprnt prnt )
int containsS ( Set a, Ptr x, Fcmp cmp )
// adauga un pointer la o multime
void addS ( Set a, Ptr x, Fcmp cmp)
a->v[a->n ++]= x; // adauga la sfirsitul vectorului
}
Programul de aplicatie trebuie sã aloce dinamic memorie pentru datele ale cãror adrese se vor introduce în vector, pentru a avea adrese distincte pentru fiecare variabilã.
Ca exemplu, vom considera cã trebuie sã extragem cuvinte distincte dintr-un fisier text si cã trebuie sã afisãm, la fiecare cuvânt si numãrul primei linii în care apare acel cuvânt.
// tip date memorate in multime
typedef struct T;
//afisare tip T
void printT ( void * p)
// compara var de tip T
int compT (void * p1, void * p2)
// extrage cuvinte dintr-un fisier text
void main (int argc, char* argv[])
}
printS (set,printT);
|
