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);
|
