SDA Lucrarea 6
În acest laborator se vor implementa structuri de date asociative (map) cu arbori binari și funcții hash.
Structura de date asociativă - Map
Structura de date asociativă este o structură de date abstractă care stochează perechi de elemente cheie-valoare, astfel încât nu pot exista două perechi cu aceeași cheie, într-o ordine arbitrară stabilită de structură.
În esență, un map este o mulțime (set) de chei care este întotdeauna stocată împreună cu o valoare.
Map-ul are următoarele proprietăți:
- Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
- Numărul de elemente ce poate fi stocat de structură este nelimitat.
- Elementele stocate în mulțime sunt de același fel.
- Tipul de date al cheii și tipul de date al valorii pot fi diferite.
- Map-ul poate conține doar chei unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două chei sunt egale din punctul de vedere al map-ului, ele nu pot fi ambele prezente în perechi cheie-valoare în map.
Map-ul suportă următoarele operații de bază:
- Interogarea numărului de elemente din map.
- Verificarea dacă map-ul este gol.
- Adăugarea perechi cheie-valoare (put) - dacă cheia există deja în map, perechea respectivă este înlocuită de noua valoare.
- Verificarea dacă o chieie există în map (hasKey).
- Căutarea unei valori după o cheie dată (get);
- Eliminarea unei chei din map (remove).
Implementarea map-urilor cu arbori binari de căutare (Binary Search Trees - BST)
Pentru a putea plasa elemente într-un map implementat cu arbori binari de căutare, pe mulțimea cheilor trebuie să existe definită o relație de ordine.
Map-urile implementate cu arbori binari de căutare, în plus față proprietățile map-urilor definite mai sus, garantează faptul că elementele sunt plasate în ordinea cheilor în structură (Ordered Map).
Din acest motiv trebuie definită o funcție care să compare două chei. Vom numi această funcție compare
și se ca comporta similar cu funcția strcmp
: va întoarce o valoare pozitivă dacă primul element e mai mare, o valoare negativă dacă al doilea element e mai mare și 0 dacă elementele sunt egale:
/**
* Compara value1 cu value2 si intoarce o valoare corespunzătoare.
* @param value1 prima valoare de comparat.
* @param value2 a doua valoare de comparat.
* @return o valoare pozitivă dacă primul element e mai mare, o
* valoare negativă dacă al doilea element e mai mare și 0 dacă
* elementele sunt egale.
*/
int compare(K value1, K value2);
Tipul de date și funcțiile de bază
În continuare vom prezenta un exemplu de map pentru elemente de tip "server" implementată cu arbori binari de căutare. În primul rând vom defini structura ce memorează datele legate de un server:
struct Server {
/* Numele server-ului in retea - sir de caractere */
char hostname[30];
/* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */
unsigned char ipv4[4];
/* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */
char hardwareAddress[6];
/* Tipul procesorului - sir de caractere. */
char cpuType[10];
/* Frecventa procesorului in Gigahertz. */
float cpuFrequencyGhz;
/* Cantitatea de memorie RAM, in Gigabytes. */
float ramMemoryGigaBytes;
/* Capacitatea discului, in Terabytes. */
float diskCapacityTeraBytes;
};
Vom folosi pe post de cheie în map hostname-ul server-ului, prin urmare definim:
- tipul de date al cheii este char *;
- tipul de date al valorii este struct Server;
Pentru a implementa un map de servere folosind BST, avem întâi nevoie să definim funcția de comparare a două chei:
/**
* Compara name1 cu name2 si intoarce o valoare corespunzătoare.
* @param name1 primul nume de comparat.
* @param name2 al doilea nume de comparat.
* @return o valoare pozitivă dacă primul nume este mai mare, o
* valoare negativă dacă al doilea nume este mai mare și 0 dacă
* numele sunt egale.
*/
int compare(char * name1, char * name2);
Structurile TreeMap
, TreeNode
și Pair
Pentru stocarea datelor necesare mulțimii, definim următoarele structuri:
struct Pair {
char * key;
struct Server value;
};
struct TreeNode {
struct TreeNode * parent;
struct TreeNode * left;
struct TreeNode * right;
struct Pair pair;
};
struct TreeMap {
struct TreeNode * root;
unsigned size;
};
Crearea unui TreeMap
Pentru a crea un TreeMap
, definim următoarea funcție:
/**
* Functia aloca memorie si intoarce un pointer la un nou TreeMap.
* @return adresa noului TreeMap.
*/
struct TreeMap * createTreeMap();
Funcția trebuie să realizeze următorii pași:
- Se alocă memorie pentru un nou
struct TreeMap
ce trebuie inițializată automat cu 0. - Se întoarce adresa alocată.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(1)
Interogarea numărului de elemente din map
Pentru interogarea numărului de elemente din map definim:
/**
* Functia intoarce numarul de elemente din map.
* @param map map-ul pentru care se cere dimensiunea.
* @return numarul de elemente din map.
*/
unsigned treeMapSize(struct TreeMap * map);
Funcția va întoarce valoarea din câmpul size
din structură.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(1)
Pentru a afla dacă map-ul este gol definim:
/**
* Functia intoarce 1 dacă map-ul nu conține nici un element.
* @param map map-ul de interes.
* @return 1 dacă map-ul este gol, 0 în rest.
*/
char treeMapIsEmpty(struct TreeMap * map);
Funcția va întoarce 1 dacă valoarea din câmpul size
este 0.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(1)
Adăugarea unui element în map
Pentru operația de adăugare se definește următoarea funcție:
/**
* Functia adauga elementul dat in map. Daca
* cheia exista deja, perechea existenta este suprascrisa.
* @param map map-ul in care trebuie adaugat elementul.
* @param key cheia din map (numele server-ului)
* @param value server-ul ce trebuie adaugat.
*/
void treeMapPut(struct TreeMap * map, char * key, struct Server value);
Adăugarea se realizează în felul următor:
- Dacă dimensiunea mulțimii este 0, se alocă memorie pentru un nod nou
newNode
în care:pair.key
va lua valoarea luikey
pair.value
va lua valoarea luivalue
parent
,left
șiright
vor lua valoareaNULL
.
- Câmpul
root
ia valoareanewNode
,size
se incrementează și funcția se încheie. - Altfel, se definește o variabilă de tip nod numită
tmpNode
care se inițializează cu valoarea câmpuluiroot
. - Într-o buclă infinită se realizează următorii pași:
- Dacă rezultatul funcției
compare
cu argumenteletmpNode->pair.key
șikey
este 0 (elementele sunt egale),tmpNode->pair.key
ia valoareakey
,tmpNode->pair.value
ia valoareavalue
și funcția se încheie. - Dacă rezultatul funcției
compare
cu argumenteletmpNode->pair.key
șikey
este mai mare ca 0 șitmpNode->left
este diferit deNULL
, atuncitmpNode
ia valoareatmpNode->left
. - Dacă rezultatul funcției
compare
cu argumenteletmpNode->pair.key
șikey
este mai mare ca 0 șitmpNode->left
este egal cuNULL
, atunci se alocă memorie pentru un nodnewNode
nou după regula de la 1,newNode->parent
ia valoarea luitmpNode
,tmpNode->left
ia valoarea luinewNode
,size
se incrementează cu 1 și funcția se încheie. - Dacă rezultatul funcției
compare
cu argumenteletmpNode->pair.key
șikey
este mai mică ca 0 șitmpNode->right
este diferit deNULL
, atuncitmpNode
ia valoareatmpNode->right
. - Dacă rezultatul funcției
compare
cu argumenteletmpNode->pair.key
șikey
este mai mică ca 0 șitmpNode->right
este egal cuNULL
, atunci se alocă memorie pentru un nodnewNode
nou după regula de la 1,newNode->parent
ia valoarea luitmpNode
,tmpNode->right
ia valoarea luinewNode
,size
se incrementează cu 1 și funcția se încheie.
- Dacă rezultatul funcției
- Complexitate în timp: O(1) best case (element adăugat imediat sub rădăcină), O(log2n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
- Complexitate în spațiu: O(1)
Eliminarea unui element din mulțime
Pentru operația de eliminare se definește următoarea funcție:
/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param server elementul ce trebuie eliminat.
*/
void treeSetRemove(struct TreeSet * set, struct Server server);
Eliminarea se realizează în felul următor (o descriere în imagini poate fi găsită aici - nu încercați să folosiți codul de pe acea pagină deoarece structurile din platformă diferă și în plus limbajul este C++ și nu va compila):
- Folosind un pointer la nod
tmpNode
, se folosește tehnica de la căutarea unui element în mulțime pentru a identifica nodul care memorează serverulserver
. Dacă funcția ajunge la frunze fără a găsi server-ul căutat, funcția se încheie (server-ul nu există în mulțime). Altfel,tmpNode
va fi pointer la nodul ce trebuie eliminat. În plus, se va defini o variabilă de tip chardirection
care la fiecare avansare în arbore va lua valoarea -1 dacă avansarea s-a făcut spre stânga și 1 dacă s-a făcut spre dreapta, astfel încât atunci cândtmpNode
este pointer la nodul ce trebuie șters,direction
va fi 1 sau -1 în funcție de poziția noduluitmpNode
față de nodul părinte. - Dacă
tmpNode->left
șitmpNode->right
sunt ambeleNULL
(nodul ce trebuie șters este frunză), atunci, dacădirection
este -1,tmpNode->parent->left
ia valoareaNULL
, altfeltmpNode->parent->right
ia valoareaNULL
, nodultmpNode
este dezalocat,size
se decrementează și funcția se încheie. - Dacă
tmpNode->left
esteNULL
șitmpNode->right
este diferit deNULL
(nodul are un singur copil), atunci, dacădirection
este -1,tmpNode->parent->left
ia valoareatmpNode->right
, altfeltmpNode->parent->right
ia valoareatmpNode->right
, nodultmpNode
este dezalocat,size
se decrementează și funcția se încheie. - Dacă
tmpNode->left
este diferit deNULL
șitmpNode->right
esteNULL
(nodul are un singur copil), atunci, dacădirection
este -1,tmpNode->parent->left
ia valoareatmpNode->left
, altfeltmpNode->parent->right
ia valoareatmpNode->left
, nodultmpNode
este dezalocat,size
se decrementează și funcția se încheie. - Dacă
tmpNode->left
șitmpNode->right
sunt ambele diferite deNULL
(nodul ce trebuie șters are doi copii), atunci:- Se foloște un al doilea pointer la nod numit
minSubtreeNode
cu care se caută cea mai mică valoare din subarborele din dreapta noduluitmpNode
. tmpNode->value
ia valoareaminSubtreeNode->value
apoi se ștergeminSubtreeNode
după aceleași reguli de mai sus.
- Se foloște un al doilea pointer la nod numit
- Complexitate în timp: O(1) best case (element găsit imediat sub rădăcină), O(log2n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
- Complexitate în spațiu: O(1)
Verificarea dacă un element există în mulțime
Pentru a verifica dacă un element există în mulțime, se definește următoarea funcție:
/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param server elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/
char treeSetContains(struct TreeSet * set, struct Server server);
Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:
- Se definește un pointer la nod numit
tmpNode
care se inițializează cu valoarea luiroot
. - Cât timp
tmpNode
este diferit deNULL
:- Dacă rezultatul funcției
compare
cu argumenteletmpNode->value
șiserver
este 0, se întoarce valoarea 1 (elementul a fost găsit). - Dacă rezultatul funcției
compare
cu argumenteletmpNode->value
șiserver
este pozitiv,tmpNode
ia valoarea luitmpNode->left
. - Dacă rezultatul funcției
compare
cu argumenteletmpNode->value
șiserver
este negativ,tmpNode
ia valoarea luitmpNode->right
.
- Dacă rezultatul funcției
- Când s-a ieșit din buclă, se întoarce 0 (elementul nu a fost găsit).
- Complexitate în timp: O(1) best case (element găsit în rădăcină), O(log2n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
- Complexitate în spațiu: O(1)
Ștergerea unui TreeSet
Pentru dezalocarea unui TreeSet
, se definește următoarea funcție:
/**
* Functia sterge tree set-ul specificat.
* @param set tree set-ul ce trebuie sters.
*/
void deleteTreeSet(struct TreeSet * set);
Pentru ștergerea unui TreeSet
se urmează următorii pași:
- Se realizează o parcurgere în post-ordine (stânga-dreapta-rădăcină) și se șterg toate nodurile din arbore.
- Se șterge memoria alocată pentru structura de tip
TreeSet
.
- Complexitate în timp: O(n)
- Complexitate în spațiu: O(1)
Exerciții
Săptămâna 1
- Dându-se header-ele
treeMap.h
șiserver.h
de mai jos, implementați toate funcțiile definite în două fișiere sursă numiteserver.c
șitreeMap.c
:-
server.h
:#ifndef SERVER_H #define SERVER_H struct Server { /* Numele server-ului in retea - sir de caractere */ char hostname[30]; /* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */ unsigned char ipv4[4]; /* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */ char hardwareAddress[6]; /* Tipul procesorului - sir de caractere. */ char cpuType[10]; /* Frecventa procesorului in Gigahertz. */ float cpuFrequencyGhz; /* Cantitatea de memorie RAM, in Gigabytes. */ float ramMemoryGigaBytes; /* Capacitatea discului, in Terabytes. */ float diskCapacityTeraBytes; }; /** * Compara server1 cu server2 si intoarce o valoare corespunzătoare. * @param server1 primul server de comparat. * @param server2 al doilea server de comparat. * @return o valoare pozitivă dacă primul server are o adresa hardware mai mare, o * valoare negativă dacă al doilea server are o adresa hardware mai mare și 0 dacă * adresele hardware sunt egale. */ int compare(struct Server server1, struct Server server1); #endif
-
treeSet.h
:#ifndef TREE_SET_H #define TREE_SET_H #include "server.h" struct TreeNode { struct TreeNode * parent; struct TreeNode * left; struct TreeNode * right; struct Server value; }; struct TreeSet { struct TreeNode * root; unsigned size; }; /** * Functia aloca memorie si intoarce un pointer la un nou TreeSet. * @return adresa noului TreeSet. */ struct TreeSet * createTreeSet(); /** * Functia intoarce numarul de elemente din multime. * @param set multimea a carei dimensiuni este ceruta. * @return numarul de elemente din multime. */ unsigned treeSetSize(struct TreeSet * set); /** * Functia intoarce 1 dacă mulțimea nu conține nici un element. * @param set multimea de interes. * @return 1 dacă mulțimea este goală, 0 în rest. */ char treeSetIsEmpty(struct TreeSet * set); /** * Functia adauga elementul dat in multime daca acesta nu exista. Daca * exista deja, functia nu are nici un efect. * @param set multimea in care trebuie adaugat elementul. * @param server elementul ce trebuie adaugat. */ void treeSetPut(struct TreeSet * set, struct Server server); /** * Functia elimina elementul dat din multime daca acesta exista. Daca * nu exista, functia nu are nici un efect. * @param set multimea din care trebuie eliminat elementul. * @param server elementul ce trebuie eliminat. */ void treeSetRemove(struct TreeSet * set, struct Server server); /** * Functia intoarce 1 daca elementul specificat exista in multime. * @param set multimea in care se cauta elementul. * @param server elementul cautat. * @return 1 daca elementul exista in multime, 0 daca nu. */ char treeSetContains(struct TreeSet * set, struct Server server); /** * Functia sterge tree set-ul specificat. * @param set tree set-ul ce trebuie sters. */ void deleteTreeSet(struct TreeSet * set); #endif
-
- Scrieți o altă sursă
main.c
în care să definiți o funcțiestruct Server readFromKeyboard()
și o altă funcțiemain
care să citească informații legate de servere de la tastatură până când hostname-ul introdus este egal cu "-" și care să afișeze câte servere diferite au fost introduse.