Implementarea modelelor de date

Implementarea modelelor de date

Programele pentru calculatoare utilizeaza de obicei tabele de informatii care presupun anumite relatii structurale intre datele care le compun. Aceste relatii structurale diferentiaza mai multe modele de organizare a datelor, dintre care cele mai importante sunt: liste, arbori, multimi. Toate aceste modele se reprezinta in programare prin colectii de date care, in programarea orientata pe obiecte, se implementeaza prin clase (tipuri definite de utilizator).

Fiecare programator isi poate defini propriile implementari ale modelelor de date, sau poate sa foloseasca unele tipuri definite in bibliotecile sistemului, pe care le modifica in mod corespunzator cerintelor aplicatiei. In ambele situatii, insa, este necesara cunoasterea modului de organizare interna a unor astfel de modele de date, precum si posibilitatile de reprezentare si de exploatare a acestora prin intermediul claselor de colectii, a claselor container si a claselor template. Reprezentarea colectiilor de date prin intermediul claselor derivate si al claselor template vor fi prezentate in sectiunile 5 si, respectiv, 7.

Liste liniare

O lista liniara este o secventa finita de elemente de un tip dat. Secventa in care apar elementele este definitorie. De exemplu, lista (a₁, a₂, a_n este diferita de lista (a₂, a₁, a_n). De asemenea, in lista este posibil sa existe elemente cu acceasi valoare (elemente duplicat, ceea ce in multimi nu este admis). Lungimea listei este data de numarul de elemente in lista. Modelul de lista include si lista vida, care are zero elemente. Daca lista nu este vida, atunci ea contine un element de inceput, numit capul listei (head), iar restul elementelor se numeste coada listei (tail). Elementele listei pot fi identificate prin pozitia lor in lista, un index i, care poate avea valori £ i £ n , unde n este lungimea listei. De multe ori, (mai ales in implementarile in limbajul C), elementele listei se indexeaza de la la n-1, asa cum sunt indexate datele in tablourile din C.

O sublista este formata dintr-o parte a elementelor unei liste, cu indici cuprinsi intre i si j a_i, a_i a_j) unde £ i £ j £ n.

Operatiile care se pot executa asupra listelor sunt foarte variate: inserari, extrageri, cautari, concatenari, divizari, sortari. Dintre acestea, primele trei operatii sunt operatii fundamentale de tip dictionar:

Operatia de inserare consta in adaugarea unui nou element x unei liste L Pozitia in care se poate insera noul element este oricare pozitie in lista: inaintea primului element (in aceasta situatie se modifica capul listei), dupa ultimul element, sau intre oricare doua elemente. Este admisa inserarea unui nou element care are aceeasi valoare cu un alt element component al listei.

Operatia de stergere (extragere) a unui element dintr-o lista inseamna eliminarea unui element x dintr-o lista. Daca in lista exista mai multe elemente cu aceeasi valore, se specifica suplimentar care dintre acestea se elimina.

Operatia de cautare (lookup) returneaza valoarea "adevarat" daca elementul cu valoarea x apartine listei, si valoarea "false", daca elementul nu apartine listei.

Liste ordonate

Operatia de sortare intr-o lista presupune ca elementele listei apatin unei multimi in care se poate defini o relatie de ordine liniara. Fie o lista:

L = (a, c, b, f, e, d), unde a, b, I S

Multimea S careia in apartin elementele listei trebuie sa fie o multime ordonabila liniar. O multime de elemente S este ordonabila liniar daca si numai daca:

pentru fiecare doua elemente a si b ale multimii S este indeplinita una din conditiile: a < b a = b sau a > b

pentru oricare trei alemente a b c ale multimii S, daca a < b si b < c, atunci a < c

Simbolul " < " semnifica "precede". Un exemplu de multime care satisface conditiile de ordine liniara este multimea numerelor intregi. Un alt exemplu este multimea literelor alfabetului Latin. Intr-o secventa S = compusa din elemente care apartin unei multimi ordonabile liniar, rangul k al unui element s_i este definit ca numarul de elmente in S care preced elementul s_i plus 1.

Sortarea unei liste (secventa de elemente) inseamna efectuarea unei permutari intre elementele listei, astfel incat fiecare sa respecte regula de precdenta fata de elementul aflat inaintea lui in lista. Ca rezultat al unei operatii de sortare in lista L rezulta lista L'

L' = (a, b, c, d, e, f), unde a < b < c < d < e < f

O astfel de lista se numeste lista ordonata.

In programarea orientata pe obiecte elementele unei liste sunt de un tip dat, predefinit sau definit de utilizator (clasa). Pentru tipurile de date fundamentale ale limbajului C relatia de precedenta < " este definita printr-un operator de relatie. Pentru tipurile definite de utilizator, obiectele (instante ale unei clasei) dintr-o lista pot fi ordonate daca pentru clasa respectiva se defineste operatia de precedenta. In general, aceasta operatie se defineste prin supraincarcarea operatorul de relatie " <

Stive si cozi

Pe baza modelului de date lista liniara sunt definite alte tipuri de date abstracte, cum sunt stiva (stack) si coada (queue), prin restrictionarea modului de executie a operatiilor asupra listei.

Stiva este o lista in care toate operatiile (de inserare si de extragere) au loc printr-un singur capat al listei, care se numeste varful stivei (top) (Fig. 3.1-a). Datorita f 333g66d aptului ca operatiile in stiva se executa printr-un singur capat, aceste operatii se desfasoara intotdeauna in ordinea ultimul inserat, primul extras (last-in, first-out - LIFO), de unde si numele LIFO sub care este frecvent intalnit acest tip de date.

Coada este o lista in care operatiile de inserare si extragere au loc prin capete diferite ale listei. Operatia de inserare se executa la sfarsitul cozii (spate, rear), in timp ce extragerea se executa din inceputul (fata, front) cozii (Fig. 3.1-b). Temenul de lista FIFO, frecvent folosit pentru coada, provine din acest mod de executie: primul intrat, primul extras (first-in, first-out, FIFO)

Fig. 3.1 Doua tipuri de liste: stiva (a) si coada(b)

Modelul de date abstract lista se poate reprezenta, in principal, prin doua structuri (tipuri) de date: tablou de elemente (vector) si lista inlantuita.

Implementarea listelor liniare prin tablouri

In aceasta implementare elementele listei sunt memorate intr-un tablo, ceea ce inseamna ca elementele vecine in lista ocupa locatii vecine in memorie. Implementarea prin tablouri a listelor beneficiaza de acces rapid la un element intr-o pozitie data. In schimb, inserarea sau stergerea unui element poate necesita operatii costisitoare de deplasare a unor elemnte pentru a face loc unuia nou (la inserare) sau pentru a le realipi, la stergerea unui element.

Pentru implementarea unei liste liniare se poate folosi un tablou unidimensional (vector) de elemente ca tip derivat de date, alocat static sau dinamic in memorie. De exemplu

T vector[d];

defineste un vector de elemente de tipul T, predefinit sau definit de utilizator (clasa) alocat static in memorie, in care se poate stoca o lista de maximum d elemente. Se poate defini si un vector alocat dinamic in memorie, de exemplu

T vector = new T[d];

Numarul de elemente n ale listei este o informatie strict necesara in cazul implementarii listelor ca tablouri, deoarece dimensiunea tabloului (d) nu coincide cu numarul de elemente ale listei, fiind in general mai mare, pentru a se asigura posibilitatea de inserare a noi elemente (Fig. 3.2).

Fig. 3.2 Implementarea ca vector a unei liste liniare.

In abordarea orientata pe obiecte, o lista de elemente de tipul T implementata ca vector se poate reprezenta printr-o clasa care, in general, memoreaza vectorul de date de tipul respectiv T, dimensiunea vectorului d si numarul n de elemente ale listei. Functiile membre ale clasei modeleaza operatiile impuse de destinatia listei. De exemplu, pentru o clasa care reprezinta o stiva, sunt necesare operatiile de inserare (push) si de extragere (pop

Aceasta a fost modul de implementare din Exemplul 2.5 din sectiunea precedenta: clasa IntStack implementeaza o stiva de numere intregi, reprezentata printr-un tablou (vector) alocat static in memorie, de dimensiune (MAX_SIZE) care este o constanta in program. In implementarea prin vector a stivei, operatiile de inserare si de extragere a elementelor stivei (push() si pop()) se executa fata de ultimul element al listei care reprezinta stiva: se insereaza un element dupa ultimul element memorat (cu indice maxim in lista) si se extrage ultimul element memorat. Aceasta pozitie de varf a stivei este memorata in clasa IntStack printr-un indice (tos). Intr-o versiune similara de stiva (cea prezentata in subsectiunea 7.1 ), in clasa template TStack varful stivei este memorat printr-un pointer (top), dar aceasta diferenta este nesemnificativa.

Cealalta posibilitate de implementare a listelor liniare, prin alocarea dinamica a vectorului in memoria libera, cu o dimensiune care se stabileste in momentul executiei, a fost exemplificat in Exemplul 2.7, prin clasa DStack pentru o stiva de numere intregi.

Ambele versiuni, folosind vectori de date de dimensiuni fixe, stabilite la compilare sau la crearea dinamica a stivei, au dezavantajul inflexibilitatii si al consumului nejustificat de memorie.

O varianta imbunatatita de implementare a unei liste prin vector alocat dinamic in memorie este propusa in Exercitiul 2.6, prin clasa IntArray, in care dimensiunea vectorului creste atunci cand se depaseste spatiul de memorare existent la un moment dat cu o cantitate fixa (grows) stabilita in definitia clasei. O astfel de implementare este avantajoasa din punct de vedere al spatiului de memorie ocupat, dar devine ineficienta ca timp de executie, daca au loc operatii frecvente de ajustare a dimensiunii vectorului. Pentru cresterea dimensiunii vectorului, se aloca un nou vector in memorie, se copiaza tot continutul precedent si se elibereaza vechiul vector.

Implementarea unei cozi se poate face folosind un vector de elemente, dar pentru accesul la ambele capete ale listei, asa cum este necesar in structora FIFO, se aranjeaza astfel ca vectorul sa fie parcurs circular.

Vectorul de elemente are dimensiune p locatii posibile (elemente) si o structura circulara. Doua variabile memoreaza pozitia (indicele) de scriere (writer) si pozitia de citire din vector (reader) (Fig. 3.3).

reader

Fig 3.3 Implementarea unei cozi printr-un vector parcurs circular

Initial coada este goala, numarul de elemente ocupate in vector (n) este egal cu zero, iar indicii de inserare si de extragere sunt de asemenea initializati cu valoarea 0. Un element se insereaza in vector in pozitia (indicele) writer, dupa care acesta este incrementat circular writer = (writer+1)%d; si de asemenea este incrementat numarul n de elemente ale listei. Daca lista nu este vida (daca n > 0) se poate extrage un element din vector de la adresa reader, dupa care acest indice este incrementat circular: reader = (reader+1)%d; iar numarul de elemente n este decrementat. Operatia de inserare trebuie sa fie permisa numai daca mai exista pozitii libere in vector (daca n < d). Operatia de extragere trebuie sa fie permisa numai daca exista cel putin un element in vector (n > 0

Listele, impreuna cu ale modele de date (cum sunt multimile sau arborii) sunt in general denumite si colectii de date, deoarece contin mai multe elemente de acelasi tip, cu o anumite relatii intre ele.

Implementarea colectiilor de date prin liste inlantuite

O lista liniara ca model de date abstract (secventa finita de elemente de acelasi tip) se poate implementa si printr-o structura de date de tip lista simplu sau dublu inlantuita.

O lista simplu inlantuita este o schema de implementare a colectiilor de elemente in care fiecare nod al listei este compus din doua campuri: un camp contine un element al colectiei, de un tip dat, iar celalalt camp contine un pointer catre urmatorul nod al listei (Fig. 3.3-a).

O lista dublu inlantuita este compusa din noduri, fiecare nod avand trei campuri: un camp contine un element al colectiei, al doilea camp contine un pointer catre urmatorul nod al listei, iar al treilea camp contine un pointer catre nodul precedent al listei (Fig. 3.3-b). In reprezentarea obisnuita a listelor inlantuite, pointerii se reprezinta prin sageti catre nodurile vecine, valoarea efectiva a acestora (adresa din memorie a nodului) fiind de obicei nesemnificativa. Pointerii de inlantuire au valoarea 0 pentru nodurile terminale si in reprezentarile grafice sunt marcati printr-un punct sau o legatura la masa ("impamantare") In lista simplu inlantuita, ultimul nod este nod terminal si are pointerul catre nodul urmator 0. In lista dublu inlantuita primul nod are pointerul catre nodul precedent 0, iar ultimul nod are pointerul catre urmatorul nod 0.

In listele inlantuite elementele succesive nu ocupa, in general, in locatii succesive in memorie. Fiecare nod se aloca dinamic in memoria libera, iar campurile de inlantuire (pointerii) se pozitioneaza astfel incat sa se asigure inlantuirea corecta a nodurilor. Listele inlantuite ofera avantajul ca pot reprezenta colectii cu numar variabil de elemente, fara sa se ocupe un spatiu suplimentar in memorie (cu exceptia spatiului de memorare a pointerilor). De asemenrea, operatiile de inserare si de extragere a elementelor sunt mai simple, implicand numai modificari de valori ale pointerilor, si nu deplasari ale elementelor (asa cum se poate intampla in cazul utilizarii vectorilor).

Principalul dezavantaj al listelor inlantuite il reprezinta timpul mare si variabil de cautare al unui element dat in lista, dar chiar si asa, listele inlantuite sunt frecvent utilizate in programare.

Reprezentarea listelor inlantuite este posibila in orice limbaj procedural, prin definirea structurilor compuse din campurile corespunzatoare (elementul listei si pointerii la noduri vecine).

In modelarea orientata pe obiecte a listelor inlantuite se pot folosi una sau mai multe clase, in functie de destinatia listei respective. In orice situatie va exista o clasa care va modela un nod al listei, avand ca date membre un element al colectiei de date (sau un pointer catre acesta) si pointerul sau pointerii de inlantuire.

Se poate ca o lista inlantuita sa fie reprezentata numai printr-o astfel de clasa. In Exercitiul 3.1 este propusa o astfel de rerprezentare a unei liste simplu inlantuite. Nodurile se inlantuie intre ele, iar lista se indica printr-un pointer la primul sau nod. Daca se analizaza o astfel de reprezentare se pot observa diferite anomalii in operatiile efectute asupra listei. In primul rand, o operatia asupra primului nod (ca, de exemplu eliminarea primului nod) modifica lista insasi, adica pointerul la primul nod al inlantuirii prin care se cunoaste lista. Mai sunt si alte anomalii in reprezentarea listelor inlantuite folosind o singura clasa (tip de date). Acestea sunt evidentiate in Exercitiul 3.1.

O reprezentare mai completa a unei liste inlantuite se poate face prin doua tipuri de date (clase): o clasa reprezinta un nod al listei si o alta clasa reprezinta lista insasi; in subsectiunile care urmeaza sunt descrise astfel de reprezentari ale listelor simplu si dublu inlantuite de numere intregi.

Lista simplu inlantuita de numere intregi

Se definesc doua clase pentru reprezentarea unei liste simplu inlantuite de numere intregi: o clasa IntSListNode pentru reprezentarea unui nod al listei si o clasa IntSList pentru reprezentarea listei. In clasa IntSListNode este memorat elementul listei (un numar intreg, variabila int v) si pointerul link la nodul urmator. In clasa IntSList este memorat pointerul la primul nod al listei (first), pointerul la ultimul nod al listei (last) si numarul de elemente ale listei (count . Memorarea ultimului nod al listei (last) si al numarului de elemente (count) nu sunt strict necesare, deoarece ele pot fi calculate de fiecare data pornind de la primul nod. Dar aceste operatii parcurg secvential intreaga lista, ceea ce reprezinta un consum de timp de care poate fi considerabil pentru listele de dimensiuni mari si de aceea memorarea acestor variabile in clasa IntSList maresc eficienta de executie a operatiilor cu listele simplu inlantuite.

Pentru fiecare clasa s-au definit constructori, destructor si functii membre care implementeaza operatii asupra listei. Clasa IntSList este declarata friend in clasa IntSListNode, pentru ca aceasta din urma sa poata accesa datele protejate ale clasei IntSList

class IntSListNode

~IntSListNode();

class IntSList

IntSList(int x);

IntSList(int* p, int n);

IntSList(const IntArray& array);

IntSList(IntSList& r)

int GetHead(); // citeste elem. din cap

int GetTail(); // citeste elem. din coada

void AddHead(int x); //adauga elem. in capul listei

void AddTail(int x); //adauga elem. in coada listei

int RemoveHead(); // extrage elem. din cap

int RemoveTail(); // extrage elem. din coada

int Lookup(int x) // cautare element x

void Display(); // afiseaza toate elem. listei

Constructorul de initializare al clasei IntSListNode construieste un nod al listei in care elementul primeste valoarea transmisa ca argument si pointerul de inlantuire nul (0).

Contructorul de inizializare cu un argument de tip intreg al clasei IntSList creaza o lista compusa dintr-un singur nod (element al listei) pe care il aloca dinamic in memoria heap folosind operatorul new

inline IntSList::IntSList(int x)

Constructorul de initializare cu doua argumente creaza o lista inlantuita in care elementele (pe care le creaza in memoria heap) sunt in ordinea din vectorul de numere intregi primit ca argument.

IntSList::IntSList(int* p, int n)

count = n;

Se mai poate defini un constructor avand ca argument o referinta (const) la un obiect din clasa IntArray, care contine un vector de numere intregi (Exercitiul 3.6):

IntSList::IntSList(const IntArray& array)

count = n;

Constructorul de copiere al clasei IntSList se defineste astfel

IntSList::IntSList(IntSList& r)

Destructorul clasei IntSListNode nu are de executat nici-o operatie utila, alta decat sa afiseze un mesaj care sa permita ulterior observarea compotarii acestei clase. Destructorul clasei IntSList parcurge lista inlantuita de noduri si le sterge succesiv din memorie folosind operatorul delete

~IntSListNode()

IntSList::~IntSList()

In Exercitiul 3.2 este propus si un alt mod de distrugere a obiectelor de clasa IntSListNode si IntSList.

Functia Display() a clasei IntSList afiseaza continutul unei liste incepand cu primul nod. O operatie asemanatoare se poate obtine prin supraincarcarea functiei operator << pentru clasa IntSList (Exercitiul 4. . )

void IntSList::Display()

cout << endl;

Fie urmatoarea functie fslist1()

void fslist1();

IntSList list1(val, sizeof(val)/sizeof(int));

list1.Display();

Obiectul list1 de clasa IntSList care se creaza la executia acestei functii este reprezentat in Fig. 3.4.

Fig. 3.4 Obiect (lista simpla inlantuita de numere intregi) din clasa IntSetList

Mesajele afisate la executia functiei fslist1() sunt:

Destructor nod v = 1

Destructor nod v = 2

Destructor nod v = 3

Destructor nod v = 4

Destructor nod v = 5

Operatiile de dictionar implementate pentru aceasta lista permit adaugarea unui nou element la inceputul sau sfarsitul listei (AddHead() si AddTail()) si extragerea (citire valoare si eliminare) unui element din capul sau coada listei RemoveHead() si RemoveTail()). In aceste operatii de adaugare si stergere element nu trateaza cazurile de eroare (eroare de alocare a unui nod nou la inserare sau eroarea de lista vida la extragere). Aceste situatii se vor trata ca exceptii (in sectiunea 8).

void IntSList::AddHead(int x)

void IntSList::AddTail(int x)

else

count++;

int IntSList::RemoveHead()

return v;

}

int IntSList::RemoveTail()

else p = p->link;

}

else

}

}

Alte functii membre ale clasei IntSList sunt functii de aflare a elementelor de inceput si de sfarsit ale liste, GetHead() si GetTail() si functia Lookup() care returneaza numarul de elemente cu o valoare data aflate in lista. Definitiile acestor functii sunt lasate ca un exercitiu simplu.

Lista simplu inlantuita definita prin clasele IntSListNode si IntSList se poate folosi pentru a implementa o stiva de numere intregi. Functia AddHead() este echivalenta operatiei push, iar functia RemoveHead() este echivalenta operatiei pop. Functia fslist2() evidentiaza acest lucru:

void fslist2()

De acemenea, aceasta lista se poate folosi pentru implementarea unei cozi de numere intregi. Functia AddTail() este echivalenta operatiei de inserare, iar functia RemoveHead() este echivalenta operatiei de extragere. De exemplu

void fslist3()

Lista dublu inlatuita de numere intregi

Pentru implementarea unei liste dublu inlantuite de numere intregi se folosesc doua clase: clasa IntDListNode, care reprezinta un nod al listei si clasa IntDList, care reprezinta lista dublu inlantuita. In clasa IntDListNode este memorat elementul listei (un numar intreg, variabila int v), pointerul next la nodul urmator si pointerul prev la nodul precedent. In clasa IntDList este memorat pointerul la primul nod al listei (first), pointerul la ultimul nod al listei (last) si numarul de elemente ale listei (count . Pentru fiecare clasa s-au definit constructori, destructor si functii membre care implementeaza operatii asupra listei. Clasa IntDList este declarata friend in clasa IntDListNode, pentru ca aceasta din urma sa poata accesa datele protejate ale clasei IntDList

class IntDListNode

~IntDListNode();

};

class IntDList

IntDList(int x);

IntDList(int* p, int n);

IntDList(const IntArray& array);

IntDList(IntDList& r);

~IntDList();

int GetCount()

void AddHead(int x);

void AddTail(int x);

int GetHead();

int GetTail();

int RemoveHead();

int RemoveTail();

void Display();

void ReverseDisplay();

};

Constructorul cu un argument de tip intreg al clasei IntDList se defineste astfel:

inline IntDList::IntDList(int x)

Ceilalti constructori se pot implementa mai simplu folosind una din functiile de inserare a unui element, AddHead() sau AddTail(). La inserarea unui element intr-o lista dublu inlantuita trebuie sa fie refacute legaturile intre nodul nou introdus si nodurile existente pentru ambele directii de inlantuire. In Fig. 3.5 sunt reprezentate modificarile de pointeri la inserarea unui element nou in fata primului element al listei (functia AddHead()

Definitiile functiilor de inserare elemente AddHead() si AddTail() sunt urmatoarele

void IntDList::AddHead(int x)

else

count++;

void IntDList::AddTail(int x)

else

count++;

Cazul particular al listei vide este tratat separat.

Ceilalti constructori, destructorii si functiile acestor clase sunt asemanatoare cu cele ale claselor IntSListNode si IntSList si sunt propuse ca un exercitiu simplu (Exercitiul 3.3). Fie functia:

void fdlist1();

IntDList list1(v, sizeof(v)/sizeof(int));

list1.Display();

list1.ReverseDisplay();

}

In aceasta functie se creaza lista dublu inlantuita de numere intregi list1, cu valori ale elementelor luate din vectorul v. Elementele listei sunt afisate in ordine directa (incepand cu primul element al listei) si in ordine inversa (incepand cu ultimul element al listei). La iesirea din functia fdlist1() obiectul list1 este distrus, iar la distrugerea acestuia sunt apelati pe rand destructorii nodurilor componente. Mesajele afisate la executia acestei functii sunt urmatoarele

Destructor nod v = 1

Destructor nod v = 2

Destructor nod v = 3

Destructor nod v = 4

Destructor nod v = 5

Lista dublu inlantuita implementata prin clasele IntDListNode si IntDList poate fi folosita ca stiva de numere intregi, (operatiile push si pop utilizand functiile AddHead() si, respectiv, RemoveHead()), sau ca o coada de numere intregi (operatiile de inserare si extragere utilizand functiile AddTail() si, respectiv, RemoveHead()). In functia fdlist2() sunt exemplificate ambele modalitati de functionare.

void fdlist2()

Avantajul principal al listei dublu inlantuite fata de lista simplu inlantuita este acela ca permite accesul la fel de rapid din ambele capete ale listei, fiind prin aceasta mult mai eficienta decat lista simplu inlantuita. De exemplu, implementarea functiei RemoveTail() din clasa IntSList (lista simplu inlantuita) este excesiv de ineficienta, datorita parcurgerii intregii liste pana la atingerea penultimului nod, al carui link trebuie trecut in 0. De aceea, este putin probabil ca o lista simplu inlantuita sa fie folosita in programe care necesita astfel de operatii.

Listele inlantuite sunt folosite in implementarea si a altor modele de date, cum sunt arborii n-ari, multimile, tabelele de dispersie (hash table), vectori asociativi.

Listele de elemente (implementate prin tablouri sau liste inlantuite), ca si alte modele de date (cum sunt arborii sau multimile) sunt in general reprezentate prin colectii de obiecte de un anumit tip. Exemplele prezentate pana acum au permis crearea unor colectii de obiecte de un singur tip (numere intregi). Pentru implementarea unor colectii de un tip de date oarecare se pot folosi mai multe metode

Se foloseste ca element al colectiei un pointer generic (void ) care este convertit in pointer la tipul de date dorit. Un astfel de exemplu va fi prezentat pentru structurile de tip arbore binar in subsectiunea urmatoare.

Elementele colectiei sunt obiecte ale unei clase derivate dintr-o clasa generica, pentru care sunt definite colectii de date (vectori, liste inlantuite, etc). Astfel de clase se numesc clase container; un exemplu de clasa container este prezentat in sectiunea 5.

Utilizarea claselor template pentru definirea colectiilor de obiecte de un tip oarecare de date; particularizarea tipului de date (predefinit sau definit de utilizator) asigura crearea de catre compilator a colectiei de date de tipul dorit. Reprezentarea unei astfel de colectii de date de tip vector asociativ folosind doua clase template este prezentata in sectiunea 7.

In colectiile definite in aceasta sectiune, inspectarea elementelor listelor s-a executat intr-un mod simplu, prin definirea unor functii de afisare (display()) care afiseaza la consola elementele colectiei exact in ordinea in care ele apar in lista.

Un mecanism mai evoluat de inspectare a colectiilor de date ordonate (de exemplu liste ordonate) il reprezinta iteratorii. Un iterator permite parcurgerea in ordinea dorita a elementelor, fara ca aceasta ordine sa depinda de modul de ordonare interna a elementelor colectiei. Iteratorii se pot implementa in mai multe moduri. Ei pot fi constituiti dintr-un grup de functii membre publice ale unei clase a colectiei (subsectiunea 3.3) sau pot fi definiti printr-o clasa diferita de clasele prin care se descrie colectia insasi, aceptata ca o clasa friend de catre acestea. In Exemplul 7.3 din sectiunea 7 este prezentata implementarea unui astfel iterator pentru parcurgerea unui vector asociativ.

Arbori

Definitii

Un arbore (tree) este un model de date care permite reprezentarea structurilor ierarhice si constitue una dintre cele mai importante structuri neliniar ce intervin in algoritmii pentru calculatoare.

Un arbore este compus dintr-o multime finita T de unul sau mai multe noduri (nodes) si o multime de muchii (edges), fiecare muchie conectand doua noduri intre ele. Un arbore are urmaroarele proprietati

Un nod este distinct si este se numeste radacina (root).

Fiecare nod c, cu exceptia radacinii este conectat printr-o muchie la un alt nod p, numit nodul parinte al lui c; nodul c se numeste nod fiu (child) al lui p

Un arbore este conectat, in sensul ca, pornind de la un nod oarecare n, diferit de nodul radacina, si mergand la parintele lui, apoi la parintele parintelui lui n, sa asa mai departe, se ajunge la nodul radacina.

Un nod poate avea zero sau mai multi fii, dar orice nod, cu exeptia radacinii, are un parinte. Nodurile care sunt fii ale aceluisi parinte se numesc frati.

O alta definitie care se poate da arborelui este o definitie recursiva un arbore este format dintr-o multime finita T de unul sau mai multe noduri, astfel incat

Exista un nod special numit radacina;

Toate celelate noduri cu exceptia radacinii sunt repartizate in m ³ multimi disjuncte T₁, T₂, T_m, fiecare multime fiind la randul ei un arbore.

In Fig. 3.6 este reprezentat grafic un arbore, conform acestei definitii recursive.

Din definitia recursiva a arborelui rezulta ca fiecare nod al unui arbore este radacina unui subarbore. Numarul subarborilor unui nod se numeste gradul nodului. Nodurile de grad zero se numesc noduri terminale sau noduri frunza. Nodurile care nu sunt terminale sau radacina se numesc noduri interioare sau intermediare. Nivelul unui nod se defineste fata de radacina: radacina are nivelul egal cu 0; fiii radacinii au nivelul egal cu 1; in general, nivelul unui nod este cu o unitate mai mare decat nivelul parintelui sau.

Un arbore etichetat (labeled) este un arbore in care oricarui nod ii este asociata o valoare (eticheta). Eticheta unui nod este informatia asociata cu acesta si poate fi un simplu numar sau o informatie complexa, de exemplu, un intreg document sau fisier.

Daca ordinea relativa a subarborilor T₁, T₂, T_m este importanta, se spune ca arborele este ordonat. Pentru un arbore ordonat cu m ³ , are sens sa fie numit T₁ primul subarbore, T₂ al doilea subarbore, etc. Arborii ordonati se mai numesc si arbori plani. Aceasta ordonare a arborilor se face, in general, in functie de etichetele nodurilor, de aceea pentru arborii ordonati etichetele nodurilor trebuie sa fie elemente ale unei multimi ordonabile liniar, la fel ca si in cazul listelor ordonate.

Reprezentarea arborilor

Arborii se pot reprezenta prin diferite tipuri de structuri de date, iar alegerea uneia dintre ele depinde de cerintele programului de aplicatie. La modul general, fiecare nod se reprezinta prin doua campuri: un camp care contine eticheta (informatia din nod) si un camp in care se memoreza o lista de pointeri (sau oricare alt fel de informatie de legatura) ai tuturor nodurilor fii. La randul ei, lista de pointeri poate fi reprezentata intr-unul din modurile obisnuite de reprezentare a listelor: prin vectori sau liste inlantuite.

Reprezentarea arborilor este posibila in orice limbaj procedural, prin definirea structurilor compuse din campurile corespunzatoare (eticheta nodului si pointerii la nodurile fii).

In modelarea orientata pe obiecte a arborilor se pot folosi una sau mai multe clase, in functie de cerintele de prelucrare. In orice situatie va exista o clasa care va modela un nod al arborelui. Aceasta clasa are ca date membre eticheta nodului (sau un pointer catre aceasta) si lista pointerilor catre nodurile fii, reprezentata ca vector sau lista simplu sau dublu inlantuita. Arborele insusi poate fi indicat prin pointerul la nodul radacina, restul nodurilor inlantuindu-se corespunzator pointerilor din fiecare nod.

La fel ca si in cazul listelor inlantuite, o astfel de reprezentare simpla are unele neajunsuri (de exemplu, nu se poate reprezenta un arbore vid) astfel ca, de cele mai multe ori, pentru modelarea unui arbore se mai defineste inca o clasa care mentine informatii despre arborele insusi (nodul radacina, criteriul de ordonare a nodurilor, etc).

Arbori binari

Un arbore binar este un arbore in care fiecare nod are cel mult doi fii, numiti fiul din stanga si fiul din dreapta. Fiecare nod dintr-un arbore binar se reprezinta de obicei printr-un camp al informatiei (eticheta) si doi pointeri catre noduri, pointerul catre nodul fiu din stanga si pointerul catre nodul fiu din dreapta. Daca unul sau amandoi fiii unui nod lipsesc, pointerii corespunzatori au valoarea zero. In Fig. 3.7 este reprezentat un arbore binar in care fiecare nod este descris printr-o structura care contine informatia (eticheta) si cei doi pointeri.

Parcurgerea unui arbore binar se poate realiza in trei moduri: parcurgerea in preordine, in inordine sau in postordine. Metodele de parcurgere sunt definite recursiv: un arbore binar vid este parcurs fara sa se intreprinda nimic; altfel, parcurgerea se executa astfel:

Un arbore binar ordonat (sau arbore binar de cautare - binary search tree) este un arbore binar etichetat in care se respecta urmatoarea proprietate pentru fiecare nod n: etichetele tuturor nodurilor subarborelui stang al nodului n au valori mai mici decat eticheta nodului n; etichetele tuturor nodurilor subarborelui drept a lui n sunt mai mari decat eticheta nodului n

Arborii binari ordonati se folosesc in implementarea colectiilor de date de tip dictionar, in care se pot insera, se pot sterge sau se pot cauta elementele dupa valoarea etichetei acestora.

Intr-un arbore binar ordonat se definesc aceste operatii de dictionar astfel ca dupa fiecare operatie de inserare sau de stergere, arborele sa pastreze proprietatea de arbore binar ordonat. Algoritmii generali ai acestor algoritmi se gasesc in bibliografia indicata [Aho], [Knuth], [Horowitz].

In continuare este prezentata implementarea obiectuala a unui arbore binar ordonat.

Implementarea unui arbore binar ordonat

Pentru implementarea unui arbore binar ordonat se definesc doua clase: clasa TNode, care reprezinta un nod in arbore si clasa BTree, care reprezinta arborele insusi. Deoarece se intentioneaza implementarea unui arbore ordonat pentru orice tip de date, informatia (eticheta) din fiecare nod este reprezentata printr-un pointer generic in clasa TNode (pointerul d de tip PDate, cu definitia typedef void* Pdate;). Relatia de precedenta pentru compararea etichetelor nodurilor este definita printr-o functie al carui pointer este transmis ca argument la constructia arborelui si memorata ca data membra in clasa BTree (pointerul COMPARE). De asemenea, functia care se executa la vizitarea unui nod este transmisa printr-un pointer ca argument la constructia arborelui si memorata in clasa BTree (pointerul EXECUTE). Astfel functii pecizate de utilizator pentru a fi executate in derularea unui program oarecare se numesc functii callback

Tipul de date al informatiei din nodurile arborelui poate fi un tip predefinit sau, asa cum este in implementarea descrisa in continuare, un tip definit de utilizator. Exemplificarea este data pentru o clasa de obiecte, clasa info, care poate fi inlocuita cu orice clasa in aplicatia dorita. Aceste trei clase, clasa info, clasa TNode si clasa BTree sunt definite astfel:

typedef void* Pdate;

typedef int (*COMPARE) (Pdate d1, Pdate d2);

typedef void (*EXECUTE) (Pdate d);

class info

info(int x)

int get()

};

int comp(Pdate i1, Pdate i2)

void execute(Pdate i)

class TNode

~TNode()

};

class BTree

int getcount()

void insert(Pdate data);

int search(Pdate data);

void remove(Pdate data);

void inorder();

void preorder();

void postorder();

~BTree();

};

Constructorul clasei TNode creaza un nod care contine informatia data ca argument prin pointerul la aceasta si cu cei doi pointeri la nodurile fii (left si right) de valoare zero. Constructorul clasei BTree construieste un arbore vid (cu pointerul la radacina root de valoare zero) si memoreza in obiectul creat pointerii la functiile de comparatie si de executie primiti ca argumente.

In clasa BTree sunt definite trei operatii de dictionar, inserare, cautare si stergere element (functiile publice insert() search() si remove()) si trei functii de parcurgere a arborelui in preordine, inordine si postordine (functiile publice preorder() inorder() postorder()

Functia insert() introduce un nou nod in arbore, cu informatia data printr-un pointer. Algoritmul de inserare a unui element x intr-un arbore T este un algoritm recursiv definit astfel

daca T este arbore vid, se inlocuieste T printr-un nod nou creat care primeste informatia x

daca T nu este vid si radacina lui contine informatia x, atunci x este deja in dictionar si nu mai trebuie sa fie inserat

daca T nu este vid si radacina lui nu contine informatia x, atunci se insereaza x in subarborele stanga daca x este mai mic decat eticheta radacinii, sau se insereaza x in subarborele din dreapta daca x este mai mare decat eticheta radacinii.

Functia publica insert() a clasei BTree implementeaza acest algoritm de inserare folosind o functie private a clasei, functia insert1() astfel:

TNode* BTree::insert1(TNode *root, TNode *r, Pdate data)

if (f(data, r->d) == 0) return 0;

if (f(data, r->d) < 0)

return insert1(r, r->left, data);

else return insert1(r, r->right, data);

}

void BTree::insert(Pdate data)

Functia de parcurgere in inordine a clasei BTree este

void BTree::inorder1(TNode *root)

void BTree::inorder()

Daca un arbore a fost creat ordonat, (folosind functia insert()), atunci functia de parcurgere inorder() afiseaza etichetele nodurilor ordonate. De exemplu

void ft1()

tree.inorder();

}

La executia acestei functii se genereaza 10 obiecte din clasa info fiecare dintre acestea continand ca informatie un numar intreg generat in mod aleator. Fiecare obiect creat este inserat in arborele binar ordonat tree, folosind functia insert(). La parcurgerea in inordine a acestui arbore se afiseaza numerele ordonate.

Implementarea celorlalte functii ale clasei BTree este lasata ca exercitiu (Exercitiul 3.4).

Aceasta reprezentare a unui arbore binar sortat, chiar daca permite generalizarea tipului de informatie din nodul arborelui prin utilizarea unui pointer generic, este destul de incomoda (necesita conversii explicite de la pointerul la tipul de date dorit la pointer generic si invers) si este nesigura tocmai datorita faptului ca prin conversiile explicite se ocoleste mecanismul de verificare a tipului datelor specific limbajelor orientate pe obiecte. Mai mult, sunt necesare functii callback pentru definirea relatiei de precedenta sau al prelucrarilor necesare pentru fiecare tip de date. Daca pentru aplicatii mici se pot accepta si astfel de implementari, pentru programe de dimensiuni mari este recomandata folosirea unor clase de colectie "sigure", in care diversitatea tipurilor de date din care se compun colectiile respective se obtine prin derivare sau prin clase template, nu prin conversii explicite de pointeri. Astfel de reprezentari ale colectiilor de date prin clase de colectii sigure sunt prezentate in sectiunea 5 (clase derivate) si sectiunea 7 (clase template).

Multimi

Cea mai obisnuita definitie a multimii (set) este aceea prin a specifica daca un obiect apartine sau nu unei multimi date, adica:

x I S, inseamna ca x apartine multimii S

Daca x₁, x₂, x_n sunt toate elementele unei multimi S, se poate scrie: S = . Acest mod de a defini o multime prin elementele ei componente nu inseamna ca elementele multimii sunt ordonate, adica putem scrie si S =

Nu exista elemente duplicat in multimi.

Aceste particularitati deosebesc multimile de liste, in care ordinea elementelor este esentiala si pot exista elemente duplicat.

Pentru reprezentarea in programe a multimilor se utilizeaza diferite tipuri de colectii de date (vectori, liste, arbori), cu conditia ca la operatia de inserare a unui nou element sa se verifice daca mai exita un element identic cu noul element si nu se mai insereaza elementul daca el exista deja in multimea data. Acest lucru inseamna ca la inserare trebuie sa fie testate toate elementelor multimii, pentru a nu se permite multipliciatea elementelor in lista. O alta operatie care se defineste intr-o multime este operatia de cautare a unui element. Fiind data o multime S, trebuie aflat daca un element oarecare x apartine sau nu multimii.

Pentru a se implementa mai eficient aceste operatii, cea mai buna metoda este de a mentine elementele multimii intr-o colectie (arbore sau lista) ordonata. Astfel se ajunge la situatia ca, desi o multime nu presupune ordonarea elementelor sale, pentru accelerarea operatiilor in multimi, se folosesc colectii ordonate, ca de exemplu liste ordonate, implementate ca vectori sau liste inlantuite, sau arbori binari ordonati.

Implementarea prin liste a multimilor

O multime, reprezentata ca o lista ordonata de elemente, se poate implementa ca un vector (tablou unidimensional), sau ca o lista inlantuita.

De exemplu, pentru implementarea ca vector a unei multimi de numere intregi, se defineste clasa IntSet care pasteaza elementele multimii intr-un vector alocat dinamic in memorie

class IntSet

~IntSet()

int insert(int t);

int remove(int t);

int lookup(int t) const;

// functii iterator

void start(int& x)const

int inside(int& x) const

int next(int& x) const

};

Constructorul clasei IntSet aloca un vector de dimensiune data ca argument in memoria libera si destructorul dezaloca acest spatiu de memorie.

Elementele multimii stocate in vectorul set sunt mentinute ordonate crescator, ceea ce permite accelerarea operatiilor de inserare si cautare a elementelor in multime. Operatiile de baza intr-o multime sunt operatia de inserare a unui nou element intr-o multime data, implementata prin functia insert(), operatia de stergere a unui element din multime, implementata prin functia remove() si operatia de cautare a unui element, implementata prin functia lookup()

Numerele sunt inserate sau sterse din multime astfel incat ele sa fie mentinute in ordine crescatoare

int IntSet::insert(int t)

while(i>0 && t<set[i-1])

set[i] = t;

count++;

return 0;

}

int IntSet::remove(int t)

return l;

}

}

return -1; // nu este gasit

}

Operatia de aflare daca un membru apartine multimii foloseste un algoritm de cautare binara, la fel ca si operatia de stergere:

int IntSet::lookup(int t)const

return 0; // nu este gasit

}

Pentru parcurgerea elementelor multimii in scopul de a fi utilizate (de exemplu, afisate la consola) se defineste un mecanism care itereaza prin multimea data in ordinea dorita. Cel mai simplu mod de a defini un iterator este prin intermediul unor functii publice ale clasei IntSet, care stabileste punctul de pornire al iteratiei si ordinea in care sunt parcurse elementele multimii. Un astfel de mecanism ascunde utilizatorului modul de organizare interna a datelor clasei IntSet, si poate fi utilizat si daca se modifica modul de implementare a multimii, de exemplu se poate folosi o lista inlantuita sau arbore de cautare binara.

Un iterator simplu pentru multimea definita prin clasa IntSet se implementeaza prin intermediul a trei functii publice: functia start() care stabileste punctul de pornire a parcurgerii, functia next() care pozitioneaza iteratorul pe elementul urmator si functia inside() care returneaza 0 daca pozitia de iterare a depasit dimensiunea multimii.

Pentru testarea multimilor modelate de clasa IntSet se genereaza in mod aleator o secvente de numere intregi folosind functia rand() din biblioteca standard stdlib si se insereaza intr-o multime data. Continutul listei se afiseaza in ordine crescatoare folosind functiile de iteratie ale clasei si o variabila locala pos, prin care se controleaza parurgerea multimii:

void fset1()

O alta modalitate de a defini un iterator pentru multimi din clasa IntSet este prin definirea unei clase diferite care memoreaza si actualizeaza pozitia de parcurgere a unei multime date. O astfel de clasa, clasa SetIter se declara clasa friend in clasa IntSet si se defineste in felul urmator

class SetIter

void start()

int next()

else return 0;

}

int elem()

};

Un iterator se construieste pentru un obiect din clasa IntSet, al carui pointer il primeste ca argument al constructorului si-l memoreaza in variabila protejata s. La constructie, sau la apelul functiei start() se initializeaza pozitia de inceput a parcurgerii, pos = 0. Functia membra next() avanseaza cu o pozitie in multime; functia elem() returneaza valoarea elementului din pozitia curenta a iteratiei.

Se poate parcurge o multime folosind un iterator din clasa SetIter astfel

void fset2()

Operatiile cu multimi, cum sunt reuniunea, intersectia, diferenta a doua multimi, se pot implementa prin functii membre ale clasei care modeleaza multimea data (Exemplul 3.). Ca si operatia de cautare, aceste operatii beneficiaza de faptul ca multimea de elemente este reprezentata sortata.

De exemplu, operatia de reuniune a doua multimi se poate implementa printr-un algoritm de combinare (merge), daca multimile sunt reprezentate ca liste ordonate. Singura diferenta fata de un operatia de combinare este ca in multimea rezultat se insereaza o singura copie a unui element comun in cele doua multimi, in loc de doua copii cum este in cazul recombinarii, si nici o copie daca elementul respectiv nu este comun celor doua multimi.

Exemplul de mai sus, care foloseste un vector pentru reprezentarea listei ordonate a elementelor multimii, a ilustrat in principal modul de reprezentare a multimilor, dar nu este cea mai eficienta reprezentare a acestora. Chiar daca operatia de cautare este rapida (se poate executa cautare binara, care este in ordinul lui log n, pentru n elemente ale multimii - in O(log n) ), operatiile de inserare si de stergere sunt foarte ineficiente, datorita necesitatii deplasarii unor elemente pentru mentinerea ordonarii.

De aceea, cel mai frecvent, multimile se implementeaza prin liste inlantuite, in care elementele se mentin de asemenea ordonate. Operatia de cautare a unui element nu se mai poate efectua prin cautare binara (deoarece nu exista posibilitatea de a accesa noduri interne ale listei fara ca aceasta sa fie parcursa), de aceea se foloseste cautarea secventiala, care este in ordinul lui n pentru n elemente ale listei (in O(n)). In schimb, operatiile de inserare si stergere a unui element sunt nult mai eficiente deoarece nu necesita deplasari pentru mentinerea ordonarii listei.

Implementarea prin arbori binari ordonati a multimilor

Un arbore binar ordonat poate fi folosit pentru a implementa o multime de elemente de un anumit tip (predefinit sau definit de utilizator). Intr-o astfel de reprezentare, operatiile de inserare, stergere si cautare a unui element intr-o multime sunt executate eficient (in ordinul lui log n pentru n elemente ale multimii). In schimb, operatiile cu multimi (reuniunea, intersectia, diferenta) pot sa nu fie la fel de eficiente datorita apelurilor recursive ale functiei de parcurgere in ordine crescatoare a elementelor (inorder()

Pentru implementarea multimilor se mai pot folosi si 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 multimi depinde, evident, de cerintele aplicatiei in care este folosita aceasta.

Exercitii

E3.1  Se defineste clasa IntNode care reprezinta un nod al unei liste simplu inlantuite de numere intregi.

class IntNode

~IntNode();

IntNode* AddHead(int x);

int GetHead()

IntNode *RemoveHead();

void Display();

};

Se poate admite ca o lista inlantuita sa fie reprezentata printr-un pointer la primul nod de tip IntNode, care le inlantuie pe urmatoarele, si atunci se pot defini functiile AddHead() si RemoveHead() pentru adaugarea si stergerea unui element din lista. Se cere sa se defineasca functiile declarate in clasa IntNode()

O astfel de lista poate implementa direct o stiva de numere intregi

void fnode()

Care sunt dezavantajele acestei implementari a listei inlantuite

E3.2 Sa se defineasca destructorii claselor IntSListNode si IntSList astfel incat destructorul clasei IntSListNode sa stearga elementul urmator din lista, daca acesta exista. Cum se explica faptul ca se modifica mesajele afisate la executia functiei fslist1() dupa aceast modificare

E3.3 Sa se defineasca constructorii, destructorii si celelalte functii ale claselor IntDListNode si IntDList. Pentru definirea constructorilor se vor testa doua modalitati de implementare: folosind functia AddTail() sau folosind functia AddHead().

E3.4 Sa se defineasca o lista dublu inlantuita de elemente de un tip oarecare definit de utilizator, folosind ca element al listei un pointer la obiectele de tipul respectiv.

E3.5 Se se defineasca o lista dublu inlantuita ordonata de numere intregi. Pentru inserarea unui numar in lista, se va folosi un algoritm de cautare binara.

E3.6 Sa se defineasca destructorul si functiile clasei BTree

E3.6 Fie urmatoarea definitie a claselor GenListNode si GenList, care implementeaza o lista dublu inlantuita generalizata:

typedef void* Pdate;

class GenListNode

~GenListNode();

};

class GenList

GenList(Pdate p);

~GenList();

int GetCount()

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

};

Sa se completeze definitia clasei GenList si sa se defineasca functiile membre ale acestei clasei, astfel incat sa implementeze o multime de obiecte de un tip oarecare predefinit sau dat printr-o clasa.

Sa se testeze aceasta clasa pentru tipul de date sir de caractere si sa se utilizeze pentru afisarea in ordine lexicografica a unor cuvinte introduse aleator in multime.

E3.  Sa se defineasca o clasa care sa reprezinte conceptul de multime de numere intregi, clasa IntSet. Pentru aceasta clasa sa se implementeze urmatoarele functii

constructori, destructor;

functie de introducere a unui numar in multimea respectiva;

functie de aflare daca un numar dat apartine sau nu multimii;

operatii cu multimi (reuniunea, intersectia, diferenta).