| Ad_Infinitum |
| Administrator |
 |
 |
| Data inscrierii: 23/Iun/2007 |
| Mesaje: 212 |
|
|
|
|
|
 |
|
Mulþimi
Cea mai obiºnuitã definiþie a mulþimii (set) este aceea prin a specifica dacã un obiect aparþine sau nu unei mulþimi date, adicã:
x S, înseamnã cã x aparþine mulþimii S.
Dacã x1, x2,…xn sunt toate elementele unei mulþimi S, se poate scrie: S = { x1, x2,…xn }. Acest mod de a defini o mulþime prin elementele ei ingrediente nu înseamnã cã elementele mulþimii sunt ordonate, adicã putem scrie ºi S = { x2, x1,…xn }.
Nu existã elemente duplicat în mulþimi.
Aceste particularitãþi deosebesc mulþimile de liste, în care ordinea elementelor este esenþialã ºi pot exista elemente duplicat.
Pentru reprezentarea în programe a mulþimilor se utilizeazã diferite tipuri de colecþii de date (vectori, liste, arbori), cu condiþia ca la operaþia de inserare a unui nou element sã se verifice dacã mai exitã un element identic cu noul element ºi nu se mai insereazã elementul dacã el existã deja în mulþimea datã. Acest lucru înseamnã cã la inserare trebuie sã fie testate toate elementelor mulþimii, pentru a nu se permite multipliciatea elementelor în listã. O altã operaþie care se defineºte într-o mulþime este operaþia de cãutare a unui element. Fiind datã o mulþime S, trebuie aflat dacã un element oarecare x aparþine sau nu mulþimii.
Pentru a se implementa mai eficace aceste operaþii, cea mai bunã metodã este de a menþine elementele mulþimii într-o colectie (arbore sau listã) ordonatã. Astfel se ajunge la situaþia cã, deºi o mulþime nu presupune ordonarea elementelor sale, pentru accelerarea operaþiilor în mulþimi, se folosesc colecþii ordonate, ca de exemplu liste ordonate, implementate ca vectori sau liste înlãnþuite, sau arbori binari ordonaþi.
3.3.1Implementarea prin liste a mulþimilor
O mulþime, reprezentatã ca o listã ordonatã de elemente, se poate implementa ca un vector (tablou unidimensional), sau ca o listã înlãnþuitã.
De exemplu, pentru implementarea ca vector a unei mulþimi de numere întregi, se defineºte clasa IntSet care pãsteazã elementele mulþimii într-un vector alocat dinamic în memorie:
class IntSet{
int *set;
int count; // numar de elemente
int size; // mărime multime
public:
IntSet(int d){
size = d;
set = new int[d];
count = 0;
}
~IntSet(){delete set;}
int insert(int t);
int remove(int t);
int lookup(int t) const;
// functii iterator
void start(int& x)const {x = 0;}
int inside(int& x) const {return x < count;}
int next(int& x) const {return set[x++];}
};
Constructorul clasei IntSet alocã un vector de dimensiune datã ca argument în memoria liberã ºi destructorul dezalocã acest spaþiu de memorie.
Elementele mulþimii stocate în vectorul set sunt menþinute ordonate crescãtor, ceea ce permite accelerarea operaþiilor de inserare ºi cãutare a elementelor în mulþime. Operaþiile de bazã într-o mulþime sunt: operaþia de inserare a unui nou element într-o mulþime datã, implementatã prin funcþia insert(), operaþia de ºtergere a unui element din mulþime, implementatã prin funcþia remove() ºi operaþia de cãutare a unui element, implementatã prin funcþia lookup().
Numerele sunt adăugate sau ºterse din mulþime astfel încât ele sã fie menþinute în ordine crescãtoare:
int IntSet::insert(int t){
int i = count;
if (count >= size){
cout << "Depasire capacitate\n";
return 1;
}
while(i>0 && t<set[i-1]){
set[i] = set[i-1]; // deplasare elemente i--;
}
set[i] = t;
count++;
return 0;
}
int IntSet::remove(int t){ // cautare binara
int l = 0;
int u = count -1;
while(l <= u){
int m = (l+u) /2;
if( t < set[m] )
u = m-1;
else if (t > set[m])
l = m+1;
else { // gasit
int i = l;
count --;
while(i<count){
set[i] = set[i+1];
i++;
}
return l;
}
}
return -1; // nu este gasit
}
Operaþia de aflare dacã un membru aparþine mulþimii foloseºte un algoritm de cãutare binarã, la fel ca ºi operaþia de ºtergere:
int IntSet::lookup(int t)const{
int l = 0;
int u = count -1;
while(l <= u){
int m = (l+u) /2;
if( t < set[m] )
u = m-1;
else if (t > set[m])
l = m+1;
else return 1; // gasit
}
return 0; // nu este gasit
}
Pentru parcurgerea elementelor mulþimii în scopul de a fi utilizate (de exemplu, afiºate la consolã) se defineºte un mecanism care itereazã prin mulþimea datã în ordinea doritã. Cel mai simplu mod de a defini un iterator este prin intermediul unor funcþii publice ale clasei IntSet, care stabileºte punctul de pornire al iteraþiei ºi ordinea în care sunt parcurse elementele mulþimii. Un astfel de mecanism ascunde utilizatorului modul de organizare internã a datelor clasei IntSet, ºi poate fi exploatat ºi dacã se modificã modul de implementare a mulþimii, de exemplu se poate folosi o listã înlãnþuitã sau arbore de cãutare binarã.
Un iterator necomplicat pentru mulþimea definitã prin clasa IntSet se implementeazã prin intermediul a trei funcþii publice: funcþia start() care stabileºte punctul de pornire a parcurgerii, funcþia next() care poziþioneazã iteratorul pe elementul urmãtor ºi funcþia inside() care returneazã 0 dacã poziþia de iterare a depãºit dimensiunea mulþimii.
Pentru testarea mulþimilor modelate de clasa IntSet se genereazã în mod aleator o secvenþe de numere întregi folosind funcþia rand() din biblioteca standard stdlib ºi se insereazã într-o mulþime datã. Conþinutul listei se afiºeazã în ordine crescãtoare folosind funcþiile de iteraþie ale clasei ºi o variabilã localã pos, prin care se controleazã parurgerea mulþimii:
void fset1(){
IntSet set(100);
int n = 10;
for(int i=0; i<n ;i++)
set.insert(rand()%100);
int pos; // variabilã de control iteraþie
set.start(pos);
while(set.inside(pos))
cout << set.next(pos) << " ";
cout<<endl; //afiseaza 0 24 34 41 58 62 64 67 69 78
}
O altã modalitate de a defini un iterator pentru mulþimi din clasa IntSet este prin definirea unei clase deosebite care memoreazã ºi actualizeazã poziþia de parcurgere a unei mulþime date. O astfel de clasã, clasa SetIter se declarã clasã friend în clasa IntSet ºi se defineºte în felul urmãtor:
class SetIter{
IntSet* s;
int pos;
public:
SetIter(IntSet* p){s = p; pos = 0;}
void start(){pos = 0;}
int next(){
if (pos < s->count-1){
pos++;
return 1;
}
else return 0;
}
int elem(){ return s->set[pos];}
};
Un iterator se construieºte pentru un obiect din clasa IntSet, al cãrui pointer îl primeºte ca argument al constructorului ºi-l memoreazã în variabila protejatã s. La construcþie, sau la apelul funcþiei start() se iniþializeazã poziþia de început a parcurgerii, pos = 0. Funcþia membrã next() avanseazã cu o poziþie în mulþime; funcþia elem() returneazã valoarea elementului din poziþia curentã a iteraþiei.
Se poate parcurge o mulþime folosind un iterator din clasa SetIter astfel:
void fset2(){
IntSet set(100);
int n = 10;
for(int i=0;i<n;i++)
set.insert(rand()%100);
SetIter iter(&set); // iterator pt. set
cout << iter.elem() << " ";
while(iter.next())
cout << iter.elem() << " ";
cout<<endl; //afiseaza 0 24 34 41 58 62 64 67 69 78
set.remove(0);
iter.start();
cout << iter.elem() << " ";
while(iter.next())
cout << iter.elem() << " ";
cout<<endl; //afiseaza 24 34 41 58 62 64 67 69 78
}
Operaþiile cu mulþimi, cum sunt reuniunea, intersecþia, diferenþa a douã mulþimi, se pot implementa prin funcþii membre ale clasei care modeleazã mulþimea datã (Exemplul 3…). Ca ºi operaþia de cãutare, aceste operaþii beneficiazã de faptul cã mulþimea de elemente este reprezentatã sortatã.
De exemplu, operaþia de reuniune a douã mulþimi se poate implementa printr-un algoritm de combinare (merge), dacã mulþimile sunt reprezentate ca liste ordonate. Singura diferenþã faþã de un operaþia de combinare este cã în mulþimea rezultat se insereazã o singurã copie a unui element comun în cele douã mulþimi, în loc de douã copii cum este în cazul recombinãrii, ºi nici o copie dacã elementul respectiv nu este comun celor douã mulþimi.
Exemplul de mai sus, care foloseºte un vector pentru reprezentarea listei ordonate a elementelor mulþimii, a ilustrat în principal modul de reprezentare a mulþimilor, dar nu este cea mai eficientã reprezentare a acestora. Chiar dacã operaþia de cãutare este rapidã (se poate executa cãutare binarã, care este în ordinul lui log n, pentru n elemente ale mulþimii – în O(log n) ), operaþiile de inserare ºi de ºtergere sunt cumplit de ineficiente, datoritã necesitãþii deplasãrii unor elemente pentru menþinerea ordonãrii.
De aceea, cel mai frecvent, mulþimile se implementeazã prin liste înlãnþuite, în care elementele se menþin de întocmai ordonate. Operaþia de cãutare a unui element nu se mai poate efectua prin cãutare binarã (deoarece nu existã posibilitatea de a accesa noduri interne ale listei fãrã ca aceasta sã fie parcursã), de aceea se foloseºte cãutarea secvenþialã, care este în ordinul lui n pentru n elemente ale listei (în O(n)). În schimb, operaþiile de inserare ºi ºtergere a unui element sunt nult mai eficiente pentru că nu necesitã deplasãri pentru menþinerea ordonãrii listei.
3.3.2Implementarea prin arbori binari ordonaþi a mulþimilor
Un arbore binar ordonat poate fi folosit pentru a implementa o mulþime de elemente de un anumit tip (predefinit sau definit de utilizator). Într-o astfel de reprezentare, operaþiile de inserare, stergere ºi cãutare a unui element într-o mulþime sunt executate eficient (în ordinul lui log n pentru n elemente ale mulþimii). În schimb, operaþiile cu mulþimi (reuniunea, intersecþia, diferenþa) pot sã nu fie la fel de eficiente datoritã apelurilor recursive ale funcþiei de parcurgere în ordine crescãtoare a elementelor (inorder()).
Pentru implementarea mulþimilor se mai pot folosi ºi alte structuri de date, cum sunt vectorii caracteristici, vectorii asociativi sau tabele de dispersie (hash table). Alegerea celei mai adecvate metode de reprezentare a unei mulþimi depinde, evident, de cerinþele aplicaþiei în care este folositã aceasta.
Exerciþii
E3.1 Se defineºte clasa IntNode care reprezintã un nod al unei liste simplu înlãnþuite de numere întregi.
class IntNode{
int v;
IntNode* link;
public:
IntNode(int x) {v = x; link = NULL; }
~IntNode();
IntNode* AddHead(int x);
int GetHead(){return v;}
IntNode *RemoveHead();
void Display();
};
Se poate admite ca o listã înlãnþuitã sã fie reprezentatã printr-un pointer la inițialul nod de tip IntNode, care le înlãnþuie pe urmãtoarele, ºi atunci se pot defini funcþiile AddHead() ºi RemoveHead() pentru adãugarea ºi ºtergerea unui element din listã. Se cere sã se defineascã funcþiile declarate în clasa IntNode().
O astfel de listã poate implementa direct o stivã de numere întregi:
void fnode(){
IntNode* list1 = new IntNode(1);
list1 = list1->AddHead(2); // push 2
list1 = list1->AddHead(3); // push 3
list1->Display(); // afiseaza 3 2 1
cout << list1->GetHead()<< endl; // afiseaza 3
IntNode* list2 = list1->RemoveHead(); // pop
delete list1;
list2->Display(); // afiseaza 2 1
}
Care sunt dezavantajele acestei implementãri a listei înlãnþuite?
E3.2 Sã se defineascã destructorii claselor IntSListNode ºi IntSList astfel încât destructorul clasei IntSListNode sã ºteargã elementul urmãtor din listã, dacã acesta existã. Cum se explicã faptul cã se modificã mesajele afiºate la execuþia funcþiei fslist1() dupã aceast modificare?
E3.3 Sã se defineascã constructorii, destructorii ºi celelalte funcþii ale claselor IntDListNode ºi IntDList. Pentru definirea constructorilor se vor testa douã modalitãþi de implementare: folosind funcþia AddTail() sau folosind funcþia AddHead().
E3.4 Sã se defineascã o listã dublu înlãnþuitã de elemente de un tip oarecare definit de utilizator, utilizând ca element al listei un pointer la obiectele de tipul respectiv.
E3.5 Se se defineascã o listã dublu înlãnþuitã ordonatã de numere întregi. Pentru inserarea unui numãr în listã, se va folosi un algoritm de cãutare binarã.
E3.6 Sã se defineascã destructorul ºi funcþiile clasei BTree.
E3.6 Fie urmãtoarea definiþie a claselor GenListNode ºi GenList, care implementeazã o listã dublu înlãnþuitã generalizatã:
typedef void* Pdate;
class GenListNode {
friend class GenList;
public:
Pdate data;
GenListNode *next, *prev;
GenListNode(Pdate d)
{ data = d; next = prev = 0; }
~GenListNode();
};
class GenList {
private:
int count;
GenListNode *first;
GenListNode *last;
public:
GenList() {first = 0; last = 0; count = 0;}
GenList(Pdate p);
~GenList();
int GetCount(){return count;}
int insert(Pdate d);
int remove(Pdate d);
int lookup(Pdate d) const;
GenList& union(const GenList& m1,
const GenList& m2);
GenList& intersection(const GenList& m1,
const GenList& m2);
GenList& diference(const GenList& m1,
const GenList& m2);
};
Sã se completeze definiþia clasei GenList ºi sã se defineascã funcþiile membre ale acestei clasei, astfel încât sã implementeze o mulþime de obiecte de un tip oarecare predefinit sau dat printr-o clasã.
Sã se testeze aceastã clasã pentru tipul de date ºir de caractere ºi sã se utilizeze pentru afiºarea în ordine lexicograficã a unor cuvinte introduse aleator în mulþime.
E3. Sã se defineascã o clasã care sã reprezinte conceptul de mulþime de numere întregi, clasa IntSet. Pentru aceastã clasã sã se implementeze urmãtoarele funcþii:
constructori, destructor;
funcþie de introducere a unui numãr în mulþimea respectivã;
funcþie de aflare dacã un numãr dat aparþine sau nu mulþimii;
operaþii cu mulþimi (reuniunea, intersecþia, diferenþa).
Pentru reprezentarea numerelor din mulþimea datã se va folosi un |
|
