Î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ă (map) este o structură de date abstractă care stochează perechi de elemente cheie-valoare, 
într-o ordine arbitrară stabilită de structură, astfel încât nu pot exista două perechi cu aceeași cheie în map.

Î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 map 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 cheie 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 pentru map, 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 map-ului este 0, se alocă memorie pentru un nod nou newNode în care:
- pair.key va lua valoarea lui key
- pair.value va lua valoarea lui value
- parent, left și right vor lua valoarea NULL.
Câmpul root ia valoarea newNode, 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âmpului root.
Într-o buclă infinită se realizează următorii pași:
1. Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este 0 (elementele sunt egale), tmpNode->pair.key ia valoarea key, tmpNode->pair.value ia valoarea value și funcția se încheie.
2. Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este mai mare ca 0 și tmpNode->left este diferit de NULL, atunci tmpNode ia valoarea tmpNode->left.
3. Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este mai mare ca 0 și tmpNode->left este egal cu NULL, atunci se alocă memorie pentru un nod newNode nou după regula de la 1, newNode->parent ia valoarea lui tmpNode, tmpNode->left ia valoarea lui newNode, size se incrementează cu 1 și funcția se încheie.
4. Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este mai mică ca 0 și tmpNode->right este diferit de NULL, atunci tmpNode ia valoarea tmpNode->right.
5. Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este mai mică ca 0 și tmpNode->right este egal cu NULL, atunci se alocă memorie pentru un nod newNode nou după regula de la 1, newNode->parent ia valoarea lui tmpNode, tmpNode->right ia valoarea lui newNode, size se incrementează cu 1 și funcția se încheie.

Complexitate în timp: O(1) best case (element adăugat imediat sub rădăcină), O(log₂n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
Complexitate în spațiu: O(1)

Verificarea dacă o cheie există în map

Pentru operația de căutare a unei chei se definește următoarea funcție:

/**
 * Functia cauta cheia data în map.
 * @param key cheia de cautat
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
char treeMapHasKey(struct TreeMap * map, char * key);

Căutarea unei chei într-un map se realizează în felul următor:

Se definește un pointer la nod numit tmpNode care se inițializează cu valoarea lui root.
Cât timp tmpNode este diferit de NULL:
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este 0, se întoarce valoarea 1 (elementul a fost găsit).
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este pozitiv, tmpNode ia valoarea lui tmpNode->left.
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este negativ, tmpNode ia valoarea lui tmpNode->right.
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(log₂n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
Complexitate în spațiu: O(1)

Căutarea unei valori după o cheie dată

Pentru operația de căutare a unei valori după o cheie dată se definește următoarea funcție:

/**
 * Functia cauta o valoarea dupa cheia data în map.
 * @param key cheia de cautat
 * @return valoarea asociată cheii sau o structura goala daca cheia nu exista in map.
 */
struct Server treeMapGet(struct TreeMap * map, char * key);

Căutarea unei valori după o cheie într-un map se realizează în felul următor:

Se definește un pointer la nod numit tmpNode care se inițializează cu valoarea lui root.
Cât timp tmpNode este diferit de NULL:
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este 0, se întoarce tmpNode->pair.value (elementul a fost găsit).
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este pozitiv, tmpNode ia valoarea lui tmpNode->left.
- Dacă rezultatul funcției compare cu argumentele tmpNode->pair.key și key este negativ, tmpNode ia valoarea lui tmpNode->right.
Când s-a ieșit din buclă, se întoarce valoarea unei structuri de tip Server fără conținut (elementul nu a fost găsit).

Complexitate în timp: O(1) best case (element găsit în rădăcină), O(log₂n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
Complexitate în spațiu: O(1)

Eliminarea unui element din map

Pentru operația de eliminare se definește următoarea funcție:

/**
 * Functia elimina perechea cu cheia dată din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param map map-ul din care trebuie eliminat elementul.
 * @param key cheia perechii ce trebuie eliminată.
 */
void treeMapRemove(struct TreeMap * map, char * key);

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 chei în map pentru a identifica nodul care memorează cheia key. Dacă funcția ajunge la frunze fără a găsi server-ul căutat, funcția se încheie (cheia nu există în map). Altfel, tmpNode va fi pointer la nodul ce trebuie eliminat. În plus, se va defini o variabilă de tip char direction 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ând tmpNode este pointer la nodul ce trebuie șters, direction va fi 1 sau -1 în funcție de poziția nodului tmpNode față de nodul părinte.
Dacă tmpNode->left și tmpNode->right sunt ambele NULL (nodul ce trebuie șters este frunză), atunci, dacă direction este -1, tmpNode->parent->left ia valoarea NULL, altfel tmpNode->parent->right ia valoarea NULL, nodul tmpNode este dezalocat, size se decrementează și funcția se încheie.
Dacă tmpNode->left este NULL și tmpNode->right este diferit de NULL (nodul are un singur copil), atunci, dacă direction este -1, tmpNode->parent->left ia valoarea tmpNode->right, altfel tmpNode->parent->right ia valoarea tmpNode->right, nodul tmpNode este dezalocat, size se decrementează și funcția se încheie.
Dacă tmpNode->left este diferit de NULL și tmpNode->right este NULL (nodul are un singur copil), atunci, dacă direction este -1, tmpNode->parent->left ia valoarea tmpNode->left, altfel tmpNode->parent->right ia valoarea tmpNode->left, nodul tmpNode este dezalocat, size se decrementează și funcția se încheie.
Dacă tmpNode->left și tmpNode->right sunt ambele diferite de NULL (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ă cheie din subarborele din dreapta nodului tmpNode.
- tmpNode->pair ia valoarea minSubtreeNode->pair apoi se șterge minSubtreeNode după aceleași reguli de mai sus.

Complexitate în timp: O(1) best case (element găsit imediat sub rădăcină), O(log₂n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
Complexitate în spațiu: O(1)

Ștergerea unui `TreeMap`

Pentru dezalocarea unui TreeMap, se definește următoarea funcție:

/**
 * Functia sterge tree map-ul specificat.
 * @param map tree map-ul ce trebuie sters.
 */
void deleteTreeMap(struct TreeMap * map);

Pentru ștergerea unui TreeMap 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 TreeMap.

Complexitate în timp: O(n)
Complexitate în spațiu: O(1)

Implementarea de structuri asociative cu funcții hash

Definirea funcțiilor hash și a proprietăților lor s-a făcut în laboratorul 5 (SDA Lucrarea 5#Implementarea de mulțimi cu funcții hash).

Tipul de date și funcțiile de bază

În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip "persoană" (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:

struct Person {
    char firstName[30];
    char lastName[30];
    char idNumber[9]; // seria si numarul de buletin
    char address[255];
    char birthday[11];
    char cnp[14];
};

Pentru a implementa o funcție hash pentru variabilele de tip char * (cheia este CNP-ul care este stocat ca un șir de caractere), avem întâi nevoie să definim operația de egalitate:

/**
 * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
 * @param cnp1 primul CNP de comparat.
 * @param cnp2 al doilea CNP de comparat.
 * @return 1 daca CNP-urile celor doua persoane sunt identice.
 */
char equals(char * cnp1, char * cnp2);

Mai departe definim funcția hash pentru un CNP.

Pentru a putea implementa un map cu funcții hash trebuie ca hash-ul maxim să fie o valoare rezonabilă pentru a putea aloca memorie cu dimensiunea valorii respective.

Din motivul de mai sus, și pentru a micșora posibilitatea unei coliziuni de hash ce va micșora performanța structurii, ieșirea funcției hash va fi un număr între 0 și 999999 obținut din ultimele 6 cifre ale CNP-ului convertite din text în număr (pentru conversie puteți folosi funcția atoi):

/**
 * Functie hash pentru un CNP stocat ca string.
 * @param cnp CNP-ul pentru care se doreste codul hash.
 * @return codul hash al CNP-ului.
 */
unsigned hash(char * cnp);

În continuare vom utiliza pentru implementarea unui Hash Map o structură de date de tip secvență împlementată cu liste (LinkedList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:

Elementul stocat în listă este un element de tip Pair care stochează împreună o cheie cu o valoare:

struct Pair {
    char * key; /* CNP-ul */
    struct Person value; /* Persoana */
};

Structura `HashMap`

Pentru stocarea datelor necesare map-ului, definim următoarea structură:

#define MAX_HASH 1000000
struct HashMap {
    struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
    unsigned size; // numarul de elemente din map
};

Crearea unui `HashMap`

Pentru crearea unui HashMap, se definește următoarea funcție:

/**
 * Functia creeaza un hashMap nou si intoarce adresa de memorie alocata.
 * @return un pointer la o structura de tip HashMap.
 */
struct HashMap * createHashMap();

Pentru crearea unui HashMap se urmează următorii pași:

Se alocă memorie pentru un element de tip struct HashMap folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0).
Se inițializează size cu 0.
Se întoarce adresa elementului de tip struct HashMap.

Complexitate în timp: O(1)
Complexitate în spațiu: O(MAX_HASH)

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 hashMapSize(struct HashMap * 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 hashMapIsEmpty(struct HashMap * 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 unei perechi cheie-valoare în map

Pentru operația de adăugare se definește următoarea funcție:

/**
 * Functia adauga perechea data in map daca cheia nu exista. Daca
 *  cheia exista deja, valoarea si cheia sunt actualizate.
 * @param map map-ul in care trebuie adaugata perechea.
 * @param key cnp-ul folosit pe post de cheie.
 * @param value persoana asociata CNP-ului.
 */
void hashMapPut(struct HashMap * map, char * key, struct Person value);

Adăugarea se realizează în felul următor:

Se aplică funcția hash pe variabila key.
Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
Se iterează peste nodurile listei căutând cheia key în pereche, folosind funcția equals. Dacă cheia este găsită, atunci cheia și valoarea din pereche sunt actualizate cu valorile argumentelor key și value și funcția se încheie; altfel, se crează un nod nou care se adaugă listei care va conține perechea key - value, dimensiunea listei și dimensiunea map-ului se incrementează.

Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
Complexitate în spațiu: O(1)

Atenție: Deoarece vectorul array conține variabile de tip struct LinkedList și nu pointeri, pentru a folosi funcțiile definite în hashMapLinkedList.h e necesară obținerea adresei variabilei de tip struct LinkedList folosind operatorul &.

Eliminarea unei chei din map

Pentru operația de eliminare se definește următoarea funcție:

/**
 * Functia elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param map map-ul din care trebuie eliminat elementul.
 * @param key cheia (CNP-ul) ce trebuie eliminata.
 */
void hashMapRemove(struct HashMap * map, char * key);

Eliminarea se realizează în felul următor:

Se aplică funcția hash pe variabila key.
Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
Se folosește funcția linkedListSearch pentru a verifica dacă person există în listă.
Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția linkedListDelete pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.

Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
Complexitate în spațiu: O(1)

Verificarea dacă o cheie există în map

Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:

/**
 * Functia intoarce 1 daca cheia specificata exista in map.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
char hashMapHasKey(struct HashMap * map, char * key);

Verificarea unei chei dacă este sau nu în map se realizează în felul următor:

Se aplică funcția hash pe variabila key.
Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
Se folosește funcția linkedListSearch pentru a verifica dacă key există în listă.
Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.

Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
Complexitate în spațiu: O(1)

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definește urmtoarea funcție:

/**
 * Functia intoarce valoarea asociată cheii key.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return valoarea asociată cheii.
 */
struct Person hashMapGet(struct HashMap * map, char * key);

Căutarea unei valori după cheie se realizează în felul următor:

Se aplică funcția hash pe variabila key.
Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
Se iterează peste nodurile din listă și se caută cheia folosind funcția equals.
Dacă cheia a fost găsită, se întoarce valoarea asociată; dacă s-a ajuns la sfârșitul listei fără a se găsi cheia, se întoarce o structură de tip Person, indiferent cu ce valori (comportament nedefinit).

Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
Complexitate în spațiu: O(1)

Ștergerea unui `HashMap`

Pentru dezalocarea unui HashMap, se definește următoarea funcție:

/**
 * Functia sterge hash map-ul specificat.
 * @param map hash map-ul ce trebuie sters.
 */
void deleteHashMap(struct HashMap * map);

Pentru ștergerea unui HashMap se urmează următorii pași:

Se iterează peste tot array-ul, ștergându-se toate nodurile din toate listele.
Se șterge memoria alocată pentru structura de tip HashMap.

Complexitate în timp: O(MAX_HASH)
Complexitate în spațiu: O(1)

Exerciții

Săptămâna 1

Dându-se header-ele treeMap.h și server.h de mai jos, implementați toate funcțiile definite în două fișiere sursă numite server.c și treeMap.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 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);

#endif

treeMap.h:

#ifndef TREE_MAP_H
#define TREE_MAP_H

#include "server.h"

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

/**
 * Functia aloca memorie si intoarce un pointer la un nou TreeMap.
 * @return adresa noului TreeMap.
 */
struct TreeMap * createTreeMap();

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

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

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

/**
 * Functia cauta cheia data în map.
 * @param key cheia de cautat
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
char treeMapHasKey(struct TreeMap * map, char * key);

/**
 * Functia cauta o valoarea dupa cheia data în map.
 * @param key cheia de cautat
 * @return valoarea asociată cheii sau o structura goala daca cheia nu exista in map.
 */
struct Server treeMapGet(struct TreeMap * map, char * key);

/**
 * Functia elimina perechea cu cheia dată din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param map map-ul din care trebuie eliminat elementul.
 * @param key cheia perechii ce trebuie eliminată.
 */
void treeMapRemove(struct TreeMap * map, char * key);

/**
 * Functia sterge tree map-ul specificat.
 * @param map tree map-ul ce trebuie sters.
 */
void deleteTreeMap(struct TreeMap * map);
 
#endif

Scrieți o altă sursă main.c în care să definiți o funcție struct Server readFromKeyboard() și o altă funcție main care să citească informații legate de servere de la tastatură până când hostname-ul introdus este egal cu "-". Scrieți apoi o buclă care să citească nume de la tastatură, să caute server-ul în map și dacă nu este să afișeze un mesaj iar dacă este, să afișeze informații despre el. Programul se încheie când se introduce din nou "-".

Săptămâna 2

Dându-se fișierele Fișier:HashMapLinkedList.h, Fișier:HashMapLinkedList.c și header-ele hashMap.h și person.h de mai jos, implementați toate funcțiile definite în două fișiere sursă numite person.c și hashMap.c:

person.h:

#ifndef PERSON_H
#define PERSON_H

struct Person {
    char firstName[30];
    char lastName[30];
    char idNumber[9]; // seria si numarul de buletin
    char address[255];
    char birthday[11];
    char cnp[14];
};

struct Pair {
    char * key;
    struct Person value;
};

/**
 * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
 * @param cnp1 primul CNP de comparat.
 * @param cnp2 al doilea CNP de comparat.
 * @return 1 daca CNP-urile celor doua persoane sunt identice.
 */
char equals(char * cnp1, char * cnp2);

/**
 * Functie hash pentru un CNP stocat ca string.
 * @param cnp CNP-ul pentru care se doreste codul hash.
 * @return codul hash al CNP-ului.
 */
unsigned hash(char * cnp);

#endif

hashMap.h:

#ifndef HASH_MAP_H
#define HASH_MAP_H

#include "hashMapLinkedList.h"
#include "person.h"

#define MAX_HASH 1000000
struct HashMap {
    struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
    unsigned size; // numarul de elemente din map
};
 
/**
 * Functia creeaza un hashMap nou si intoarce adresa de memorie alocata.
 * @return un pointer la o structura de tip HashMap.
 */
struct HashMap * createHashMap();
 
/**
 * Functia intoarce numarul de elemente din map.
 * @param map map-ul pentru care se cere dimensiunea.
 * @return numarul de elemente din map.
 */
unsigned hashMapSize(struct HashMap * map);
 
/**
 * 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 hashMapIsEmpty(struct HashMap * map);
 
/**
 * Functia adauga perechea data in map daca cheia nu exista. Daca
 *  cheia exista deja, valoarea si cheia sunt actualizate.
 * @param map map-ul in care trebuie adaugata perechea.
 * @param key cnp-ul folosit pe post de cheie.
 * @param value persoana asociata CNP-ului.
 */
void hashMapPut(struct HashMap * map, char * key, struct Person value);
 
/**
 * Functia elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param map map-ul din care trebuie eliminat elementul.
 * @param key cheia (CNP-ul) ce trebuie eliminata.
 */
void hashMapRemove(struct HashMap * map, char * key);
 
/**
 * Functia intoarce 1 daca cheia specificata exista in map.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
char hashMapHasKey(struct HashMap * map, char * key);
 
/**
 * Functia intoarce valoarea asociată cheii key.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return valoarea asociată cheii.
 */
struct Person hashMapGet(struct HashMap * map, char * key);

/**
 * Functia sterge hash map-ul specificat.
 * @param map hash map-ul ce trebuie sters.
 */
void deleteHashMap(struct HashMap * map);
 
#endif

Scrieți o altă sursă main.c în care să definiți o funcție struct Person readFromKeyboard() și o altă funcție main care să citească persoane de la tastatură până când numele introdus este egal cu "-" și care să afișeze câte persoane diferite au fost introduse.

SDA Lucrarea 6

Cuprins

Structura de date asociativă - Map

Implementarea map-urilor cu arbori binari de căutare (Binary Search Trees - BST)

Tipul de date și funcțiile de bază

Structurile `TreeMap`, `TreeNode` și `Pair`

Crearea unui `TreeMap`

Interogarea numărului de elemente din map

Adăugarea unui element în map

Verificarea dacă o cheie există în map

Căutarea unei valori după o cheie dată

Eliminarea unui element din map

Ștergerea unui `TreeMap`

Implementarea de structuri asociative cu funcții hash

Tipul de date și funcțiile de bază

Structura `HashMap`

Crearea unui `HashMap`

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Ștergerea unui `HashMap`

Exerciții

Săptămâna 1

Săptămâna 2

Meniu de navigare

Page actions

Page actions

Unelte personale

Navigare

Căutare

Unelte

SDA Lucrarea 6

Structura de date asociativă - Map

Implementarea map-urilor cu arbori binari de căutare (Binary Search Trees - BST)

Tipul de date și funcțiile de bază

Structurile TreeMap, TreeNode și Pair

Crearea unui TreeMap

Interogarea numărului de elemente din map

Adăugarea unui element în map

Verificarea dacă o cheie există în map

Căutarea unei valori după o cheie dată

Eliminarea unui element din map

Ștergerea unui TreeMap

Implementarea de structuri asociative cu funcții hash

Tipul de date și funcțiile de bază

Structura HashMap

Crearea unui HashMap

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Ștergerea unui HashMap

Exerciții

Săptămâna 1

Săptămâna 2

Meniu de navigare

Căutare

Structurile `TreeMap`, `TreeNode` și `Pair`

Crearea unui `TreeMap`

Ștergerea unui `TreeMap`

Structura `HashMap`

Crearea unui `HashMap`

Ștergerea unui `HashMap`