În acest laborator se vor implementa mulțimi cu funcții hash și arbori binari.

Mulțimea

Mulțimea este o structură de date abstractă care stochează o colecție de elemente unice în care ordinea nu contează.

Mulțimea 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.
Mulțimea poate conține doar elemente unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două elemente sunt egale din punctul de vedere al mulțimii, ele nu pot fi ambele conținute de mulțime.

Mulțimea suportă următoarele operații de bază:

Interogarea numărului de elemente din mulțime.
Verificarea dacă mulțimea este goală.
Adăugarea unui element în mulțime (put).
Verificarea dacă un element există în mulțime (contains).
Eliminarea unui element din mulțime (remove).

Pentru a verifica egalitatea a două elemente vom defini o funcție equals care va întoarce 1 dacă cele două argumente sunt egale și 0 dacă nu. Această funcție trebuie să existe pentru orice implementare de mulțime, atunci când elementele nu sunt valori ce pot fi comparate cu operatorul implicit ==:

/**
 * Functia verifica daca valorile value1 si value2 sunt egale.
 * @param value1 prima valoare de comparat.
 * @param value2 a doua valoare de comparat.
 * @return 1 daca cele doua valori sunt egale si 0 in rest.
 */
char equals(T value1, T value2);

Implementarea de mulțimi cu funcții hash

O funcție hash este o funcție care ia ca argument un șir de bytes de orice dimensiune și întoarce un șir de bytes 
de dimensiune fixă ce poartă numele de valoare de hash, cod hash sau pur și simplu hash.

Definiția unei funcții hash este strâns legată de definiția funcției equals astfel încât dacă două elemente e1 și e2 sunt considerate egale (equals(e1, e1) == 1), atunci obligatoriu hash(e1) == hash(e2).

Tipul de date și funcțiile de bază

În continuare vom prezenta un exemplu de mulțime pentru elemente de tip "persoană" 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 struct Person, avem întâi nevoie să definim operația de egalitate. O persoană își poate schimba numele, buletinul și adresa, și pot exista mai multe persoane cu aceeași dată de naștere, dar ceea ce identifică clar o persoană este codul numeric personal (CNP). Deci vom defini funcția equals să întoarcă 1 dacă cnp-urile celor două argumente de tip struct Person sunt identice:

/**
 * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
 * @param person1 prima persoana de comparat.
 * @param person2 a doua persoana de comparat.
 * @return 1 daca CNP-urile celor doua persoane sunt identice.
 */
char equals(struct Person person1, struct Person person2);

Mai departe definim funcția hash pentru o Persoană.

Pentru a putea implementa o mulțime 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 structurile de tip Person.
 * @param person peroana pentru care se doreste codul hash.
 * @return codul hash al persoanei person
 */
unsigned hash(struct Person person);

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

Structura `HashSet`

Pentru stocarea datelor necesare mulțimii, definim următoarea structură:

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

Crearea unui `HashSet`

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

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

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

Se alocă memorie pentru un element de tip struct HashSet 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 HashSet.

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

Interogarea numărului de elemente din mulțime

Pentru interogarea numărului de elemente din mulțime definim:

/**
 * Functia intoarce numarul de elemente din multime.
 * @param set multimea a carei dimensiuni este ceruta.
 * @return numarul de elemente din multime.
 */
unsigned hashSetSize(struct HashSet * set);

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ă mulțimea este goală definim:

/**
 * 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 hashSetIsEmpty(struct HashSet * set);

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 mulțime

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

/**
 * 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 person elementul ce trebuie adaugta.
 */
void hashSetPut(struct HashSet * set, struct Person person);

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

Se aplică funcția hash pe variabila person.
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ă (funcția linkedListSearch trebuie re-implementată pentru a se folosi de funcția equals pentru compararea elementelor).
Dacă valoarea întoarsă este -1 atunci person se adaugă în listă și size se incrementează 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)

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

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 person elementul ce trebuie eliminat.
 */
void hashSetRemove(struct HashSet * set, struct Person person);

Eliminarea se realizează în felul următor:

Se aplică funcția hash pe variabila person.
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ă 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 person elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
char hashSetContains(struct HashSet * set, struct Person person);

Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:

Se aplică funcția hash pe variabila person.
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 î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)

Ștergerea unui `HashSet`

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

/**
 * Functia sterge hash set-ul specificat.
 * @param set hash set-ul ce trebuie sters.
 */
void deleteHashSet(struct HashSet * set);

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

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

Implementarea mulțimilor cu arbori binari de căutare (Binary Search Trees - BST)

Pentru a putea plasa elemente într-o mulțime implementată cu arbori binari de căutare, pe mulțimea acestor elemente 
trebuie să existe definită o relație de ordine.

Mulțimile implementate cu arbori binari de căutare, în plus față proprietățile mulțimilor definite mai sus, garantează 
faptul că elementele sunt plasate în ordine în mulțime (Ordered Set).

Din acest motiv trebuie definită o funcție care să compare două elemente. 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(T value1, T value2);

Tipul de date și funcțiile de bază

În continuare vom prezenta un exemplu de mulțime 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;
};

Pentru a implementa o mulțime de servere folosind BST, avem întâi nevoie să definim funcția de comparare a două servere. Vom considera că din toate datele definite în structura de mai sus, cea care se schimbă cel mai greu este adresa fizică (hardware) a adaptorului de rețea care de cele mai multe ori este plasat pe placa de bază. Astfel, vom defini funcția compare astfel încât să compare cele două hardwareAddress:

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

Structurile `TreeSet` și `TreeNode`

Pentru stocarea datelor necesare mulțimii, definim următoarele structuri:

struct TreeNode {
    struct TreeNode * parent;
    struct TreeNode * left;
    struct TreeNode * right;
    struct Server value;
};

struct TreeSet {
    struct TreeNode * root;
    unsigned size;
};

Crearea unui `TreeSet`

Pentru a crea un TreeSet, definim următoarea funcție:

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

Funcția trebuie să realizeze următorii pași:

Se alocă memorie pentru un nou struct TreeSet 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 mulțime

Pentru interogarea numărului de elemente din mulțime definim:

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

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ă mulțimea este goală definim:

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

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 mulțime

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

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

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

Dacă dimensiunea mulțimii este 0, se alocă memorie pentru un nod nou newNode în care:
- value va lua valoarea lui server
- 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->value și server este 0 (elementele sunt egale), funcția se încheie.
2. Dacă rezultatul funcției compare cu argumentele tmpNode->value și server 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->value și server 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->value și server 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->value și server 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)

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ă serverul server. 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 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ă valoare din subarborele din dreapta nodului tmpNode.
- tmpNode->value ia valoarea minSubtreeNode->value 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)

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 lui root.
Cât timp tmpNode este diferit de NULL:
- Dacă rezultatul funcției compare cu argumentele tmpNode->value și server este 0, se întoarce valoarea 1 (elementul a fost găsit).
- Dacă rezultatul funcției compare cu argumentele tmpNode->value și server este pozitiv, tmpNode ia valoarea lui tmpNode->left.
- Dacă rezultatul funcției compare cu argumentele tmpNode->value și server 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)

Ș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 fișierele Fișier:LinkedList.h, Fișier:LinkedList.c și header-ele hashSet.h și person.h de mai jos, implementați toate funcțiile definite în două fișiere sursă numite person.c și hashSet.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];
};

/**
 * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
 * @param person1 prima persoana de comparat.
 * @param person2 a doua persoana de comparat.
 * @return 1 daca CNP-urile celor doua persoane sunt identice.
 */
char equals(struct Person person1, struct Person person2);

/**
 * Functie hash pentru structurile de tip Person.
 * @param person peroana pentru care se doreste codul hash.
 * @return codul hash al persoanei person
 */
unsigned hash(struct Person person);

#define T struct Person

#endif

hashset.h:

#ifndef HASH_SET_H
#define HASH_SET_H

#include "linkedList.h"
#include "person.h"

#define MAX_HASH 1000000

struct HashSet {
    struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
    unsigned size; // numarul de elemente din multime
};
 
/**
 * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
 * @return un pointer la o structura de tip HashSet.
 */
struct HashSet * createHashSet();
 
/**
 * Functia intoarce numarul de elemente din multime.
 * @param set multimea a carei dimensiuni este ceruta.
 * @return numarul de elemente din multime.
 */
unsigned hashSetSize(struct HashSet * 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 hashSetIsEmpty(struct HashSet * 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 person elementul ce trebuie adaugta.
 */
void hashSetPut(struct HashSet * set, struct Person person);
 
/**
 * 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 person elementul ce trebuie eliminat.
 */
void hashSetRemove(struct HashSet * set, struct Person person);
 
/**
 * Functia intoarce 1 daca elementul specificat exista in multime.
 * @param set multimea in care se cauta elementul.
 * @param person elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
char hashSetContains(struct HashSet * set, struct Person person);
 
/**
 * Functia sterge hash set-ul specificat.
 * @param set hash set-ul ce trebuie sters.
 */
void deleteHashSet(struct HashSet * set);
 
#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.

Săptămâna 2

Dându-se header-ele treeSet.h și server.h de mai jos, implementați toate funcțiile definite în două fișiere sursă numite server.c și treeSet.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ț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 "-" și care să afișeze câte servere diferite au fost introduse.

SDA Lucrarea 6

Cuprins

Mulțimea

Implementarea de mulțimi cu funcții hash

Tipul de date și funcțiile de bază

Structura `HashSet`

Crearea unui `HashSet`

Interogarea numărului de elemente din mulțime

Adăugarea unui element în mulțime

Eliminarea unui element din mulțime

Verificarea dacă un element există în mulțime

Ștergerea unui `HashSet`

Implementarea mulțimilor cu arbori binari de căutare (Binary Search Trees - BST)

Tipul de date și funcțiile de bază

Structurile `TreeSet` și `TreeNode`

Crearea unui `TreeSet`

Interogarea numărului de elemente din mulțime

Adăugarea unui element în mulțime

Eliminarea unui element din mulțime

Verificarea dacă un element există în mulțime

Ștergerea unui `TreeSet`

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

Mulțimea

Implementarea de mulțimi cu funcții hash

Tipul de date și funcțiile de bază

Structura HashSet

Crearea unui HashSet

Interogarea numărului de elemente din mulțime

Adăugarea unui element în mulțime

Eliminarea unui element din mulțime

Verificarea dacă un element există în mulțime

Ștergerea unui HashSet

Implementarea mulțimilor cu arbori binari de căutare (Binary Search Trees - BST)

Tipul de date și funcțiile de bază

Structurile TreeSet și TreeNode

Crearea unui TreeSet

Interogarea numărului de elemente din mulțime

Adăugarea unui element în mulțime

Eliminarea unui element din mulțime

Verificarea dacă un element există în mulțime

Ștergerea unui TreeSet

Exerciții

Săptămâna 1

Săptămâna 2

Meniu de navigare

Căutare

Structura `HashSet`

Crearea unui `HashSet`

Ștergerea unui `HashSet`

Structurile `TreeSet` și `TreeNode`

Crearea unui `TreeSet`

Ștergerea unui `TreeSet`