Diferență între revizuiri ale paginii „SDA Lucrarea 5”

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 63 de versiuni intermediare efectuate de alți 2 utilizatori)
Linia 1: Linia 1:
În acest laborator se vor implementa mulțimi cu funcții hash și arbori binari.
+
În acest laborator se vor utiliza mulțimi cu funcții hash și arbori binari.
 +
 
 +
= Șiruri de caractere în C++ - clasa <code>std::string</code> =
 +
 
 +
Ca să putem folosi cu ușurință structurile de date definite în STL pentru a stoca șiruri de caractere, introducem clasa <code>std::string</code> definită în header-ul <code>string</code> (a nu se confunda cu <code>cstring</code> unde sunt definite funcțiile de manipulare de stringuri din C).
 +
 
 +
== Crearea unui <code>std::string</code> ==
 +
 
 +
Pentru a instanția un obiect de tip <code>std::string</code>, există mai multe variante:
 +
 
 +
<ol>
 +
<li>Utilizarea constructorului:
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string sentence("This is a sentence represented by a string object");
 +
 
 +
    printf("%s\n", sentence.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
</li>
 +
 
 +
<li>Utilizarea operatorului de atribuire:
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string sentence = "This is a sentence represented by a string object";
 +
 
 +
    printf("%s\n", sentence.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
</li>
 +
</ol>
 +
 
 +
== Citirea unui <code>std::string</code> ==
 +
 
 +
Pentru a citi dintr-un stream un șir de caractere cu funcția <code>scanf</code>, va fi nevoie în continuare de un array de caractere, dar acesta va fi folosit pentru apelul constructorului clasei <code>std::string</code>.
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    char buffer[128];
 +
    scanf("%[^\n]", buffer);
 +
    string line(buffer);
 +
 
 +
    printf("This is the line from the keyboard: '%s'\n", line.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
 
 +
== Copierea unui <code>std::string</code> ==
 +
 
 +
Un obiect de tip <code>std::string</code> se copiază foarte simplu, fără a fi nevoie de utilizarea funcției <code>strcpy</code>:
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string sentence = "This is a sentence represented by a string object";
 +
    string copy = sentence;
 +
 
 +
    printf("This is the sentence: '%s' and this is the copy: '%s'\n", sentence.c_str(), copy.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Afișarea unui <code>std::string</code> ==
 +
 
 +
Pentru a afișa un șir de caractere cu funcția <code>printf</code>, va fi nevoie să obținem din obiectul de tip <code>std::string</code> de șirul de caractere în format <code>char*</code>. Acest lucru se realizează cu metoda <code>c_str()</code>:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string line = "This is some line!";
 +
 
 +
    printf("This is the line: '%s'\n", line.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Compararea a două obiecte de tip <code>std::string</code> ==
 +
 
 +
Compararea se poate realiza simplu, fără a utiliza funcția <code>strcmp</code>, ci folosind operatorii <code>==</code>, <code>!=</code>, <code><</code>, <code>></code>, etc:
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string text1 = "Some text";
 +
    string text2 = "Some text";
 +
 
 +
    if(text1 == text2) {
 +
        printf("The texts are identical\n");
 +
    } else {
 +
        printf("The texts are NOT identical\n");
 +
    }
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Modificarea obiectelor de tip <code>std::string</code> ==
 +
 
 +
Pentru a accesa caracterele individuale dintr-un obiect de tip <code>std::string</code>, se poate utiliza, ca și în cazul clasei <code>std::vector</code>, operatorul <code>[]</code>:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#include <string>
 +
#include <cstdio>
 +
 
 +
using std::string;
 +
 
 +
int main() {
 +
    string text1 = "Ana are un mar";
 +
    text1[11] = 'c';
 +
    text1[13] = 'l';
 +
 
 +
    printf("Textul modificat: %s\n", text1.c_str());
 +
 
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
 
= Mulțimea =
 
= Mulțimea =
Linia 16: Linia 157:
 
# Interogarea numărului de elemente din mulțime.
 
# Interogarea numărului de elemente din mulțime.
 
# Verificarea dacă mulțimea este goală.
 
# Verificarea dacă mulțimea este goală.
# Adăugarea unui element în mulțime (''put'').
+
# Adăugarea unui element în mulțime (''insert'').
# Verificarea dacă un element există în mulțime (''contains'').
+
# Verificarea dacă un element există în mulțime (''count'').
# Eliminarea unui element din mulțime (''remove'').
+
# Eliminarea unui element din mulțime (''erase'').
  
Pentru a verifica egalitatea a două elemente vom defini o funcție <code>equals</code> 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 ==:
+
Pentru a verifica egalitatea a două elemente vom specializa o structură <code>equal_to</code> care va întoarce <code>true</code> dacă cele două argumente sunt egale și <code>false</code> 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 ==:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
/**
+
namespace std {
* Functia verifica daca valorile value1 si value2 sunt egale.
+
    template <class T>
* @param value1 prima valoare de comparat.
+
    struct equal_to {
* @param value2 a doua valoare de comparat.
+
        /**
* @return 1 daca cele doua valori sunt egale si 0 in rest.
+
        * Functia verifica daca valorile value1 si value2 sunt egale.
*/
+
        * @param value1 prima valoare de comparat.
char equals(T value1, T value2);
+
        * @param value2 a doua valoare de comparat.
 +
        * @return true daca cele doua valori sunt egale si false in rest.
 +
        */
 +
        bool equal_to(const T& value1, const T& value2) const;
 +
    }
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
Atenție, pentru a putea fi folosită de clasele de tip mulțime din STL, această structură trebuie declarată în interiorul namespace-ului <code>std</code>.
  
 
== Implementarea de mulțimi cu funcții hash  ==
 
== Implementarea de mulțimi cu funcții hash  ==
Linia 37: Linia 185:
 
  de dimensiune fixă ce poartă numele de valoare de hash, cod hash sau pur și simplu hash.
 
  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 <code>equals</code> astfel încât dacă două elemente e1 și e2 sunt considerate egale (<code>equals(e1, e1) == 1</code>), atunci obligatoriu <code>hash(e1) == hash(e2)</code>.
+
Definiția unei funcții hash este strâns legată de definiția funcției <code>equal_to</code> astfel încât dacă două elemente e1 și e2 sunt considerate egale (<code>equal_to(e1, e1) == true</code>), atunci obligatoriu <code>hash(e1) == hash(e2)</code>:
  
=== Tipul de date și funcțiile de bază ===
+
<syntaxhighlight lang="cpp">
 +
namespace std {
 +
    template<class T>
 +
    struct hash {
 +
        /**
 +
        * Metoda calculeaza un hashcode pentru elementul element.
 +
        * @param element referinta la un element de tip T pentru care se calculeaza hash-ul
 +
        * @return hashcode-ul calculat.
 +
        */
 +
        std::size_t operator()(T const& element) const;
 +
    };
 +
}
 +
</syntaxhighlight>
 +
 
 +
Să definim noile elemente de sintaxă:
 +
# <code>std::size_t</code> este un tip de dată ce reprezintă o dimensiune (deci este un număr întreg fără semn), iar dimensiunea lui în biți depinde de compilator (poate fi sinonim cu <code>uint32_t</code> sau cu <code>uint64_t</code>); un cod hash este reprezentat ca o valoare de tip <code>std::size_t</code>
 +
# <code>operator()</code> este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa <code>hash<SomeType>(someValueOfSomeType)</code> pentru a apela metoda <code>operator()</code> din structura <code>hash<T></code>
 +
# <code>T const &element</code> conține două elemente de noutate:
 +
#* cuvântul cheie <code>const</code> face ca elementul să nu poată fi modificat de metodă (ci doar citit)
 +
#* operatorul <code>&</code> se numește ''referință'', similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila <code>element</code> fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
 +
# cuvântul cheie <code>const</code> de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).
 +
 
 +
=== Clasa <code>std::unordered_set</code> ===
  
Î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ă:
+
Clasa din STL care implementează mulțimi folosind funcții hash poartă numele de [http://en.cppreference.com/w/cpp/container/unordered_set std::unordered_set] și este definită în header-ul <code>unordered_set</code>. Mai departe vom exemplifica definirea funcțiilor de egalitate și hash pentru utilizarea unui <code>std::unordered_set</code> în scopul stocării unor elemente de tip <code>struct Person</code>:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
struct Person {
 
struct Person {
 
     char firstName[30];
 
     char firstName[30];
Linia 54: Linia 224:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Pentru a implementa o funcție hash pentru variabilele de tip <code>struct Person</code>, 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 <code>equals</code> să întoarcă 1 dacă cnp-urile celor două argumente de tip <code>struct Person</code> sunt identice:
+
Pentru a implementa o funcție hash pentru variabilele de tip <code>struct Person</code>, 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 <code>equal</code> să întoarcă 1 dacă cnp-urile celor două argumente de tip <code>struct Person</code> sunt identice:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
/**
+
namespace std {
* Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
+
    template<>
* @param person1 prima persoana de comparat.
+
    struct equal_to<Person> {
* @param person2 a doua persoana de comparat.
+
        /**
* @return 1 daca CNP-urile celor doua persoane sunt identice.
+
        * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
*/
+
        * @param person1 prima persoana de comparat.
char equals(struct Person person1, struct Person person2);
+
        * @param person2 a doua persoana de comparat.
 +
        * @return true daca CNP-urile celor doua persoane sunt identice.
 +
        */
 +
        bool operator()(const Person &person1, const Person &person2) const {
 +
            return strcmp(person1.cnp, person2.cnp) == 0;
 +
        }
 +
    };
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Linia 72: Linia 248:
 
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 [http://www.cplusplus.com/reference/cstdlib/atoi/ atoi]):
 
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 [http://www.cplusplus.com/reference/cstdlib/atoi/ atoi]):
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 +
namespace std {
 +
    template<>
 +
    struct hash<Person> {
 +
        /**
 +
        * Functie hash pentru structurile de tip Person.
 +
        * @param person peroana pentru care se doreste codul hash.
 +
        * @return codul hash al persoanei person
 +
        */
 +
        size_t operator()(Person const & person) const {
 +
            return (size_t) atoi(person.cnp + 7);
 +
        }
 +
    };
 +
   
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Crearea unui <code>std::unordered_set</code> ===
 +
 
 +
Pentru instanțierea unui obiect de tip <code>std::unordered_set</code>, se folosește constructorul fără argumente:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="5">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<int> mySet;
 +
    printf("My set is empty: %d\n", mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Interogarea numărului de elemente din mulțime ===
 +
 
 +
Pentru interogarea numărului de elemente din mulțime sunt definite:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce numarul de elemente din multime.
 +
* @return numarul de elemente din multime.
 +
*/
 +
size_t size();
 +
 
 +
/**
 +
* Metoda intoarce true daca multimea e goala.
 +
* @return true daca multimea e goala
 +
*/
 +
bool empty();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="10">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Adăugarea unui element în mulțime ===
 +
 
 +
Pentru operația de adăugare se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 +
*  exista deja, functia nu are nici un efect.
 +
* @param element elementul ce trebuie adaugat.
 +
*/
 +
void insert(T element);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="6-8">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Eliminarea unui element din mulțime ===
 +
 
 +
Pentru operația de eliminare se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda elimina elementul dat din multime daca acesta exista. Daca
 +
*  nu exista, functia nu are nici un efect.
 +
* @param element elementul ce trebuie eliminat.
 +
*/
 +
void erase(T element);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="12">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
 
 +
    mySet.erase(1);
 +
 
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
 
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Verificarea dacă un element există în mulțime ===
 +
 
 +
Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 +
* @param element elementul cautat.
 +
* @return 1 daca elementul exista in multime, 0 daca nu.
 +
*/
 +
size_t count(T element);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="10,11">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 
 +
    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
 +
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Iterarea peste elementele mulțimii ===
 +
 
 +
Pentru a itera peste elementele din mulțime se folosesc iteratori:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="12">
 +
#include<unordered_set>
 +
#include<cstdio>
 +
 
 +
int main() {
 +
    std::unordered_set<int> mySet;
 +
    mySet.insert(10);
 +
    mySet.insert(13);
 +
    mySet.insert(-5);
 +
    mySet.insert(-5);
 +
    mySet.insert(0);
 +
 
 +
    for(std::unordered_set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
 +
        printf("%d ", *it);
 +
    }
 +
    printf("\n");
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
 
 +
<!--
 +
== 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 <code>compare</code> și se ca comporta similar cu funcția <code>strcmp</code>: 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:
 +
 
 +
<syntaxhighlight lang="c">
 
/**
 
/**
  * Functie hash pentru structurile de tip Person.
+
  * Compara value1 cu value2 si intoarce o valoare corespunzătoare.
  * @param person peroana pentru care se doreste codul hash.
+
* @param value1 prima valoare de comparat.
  * @return codul hash al persoanei person
+
  * @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.
 
  */
 
  */
unsigned hash(struct Person person);
+
int compare(T value1, T value2);
 +
</syntaxhighlight>
 +
 
 +
=== 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:
 +
<syntaxhighlight lang="c">
 +
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;
 +
};
 
</syntaxhighlight>
 
</syntaxhighlight>
  
În continuare vom utiliza pentru implementarea unui Hash Set o structură de date de tip secvență împlementată cu liste (ArrayList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:
+
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ă <code>hardwareAddress</code>:
* [[Fișier:arrayList.h]]
+
<syntaxhighlight lang="c">
* [[Fișier:arrayList.c]]
+
/**
 +
* 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);
 +
</syntaxhighlight>
  
=== Structura <code>HashSet</code> ===
+
=== Structurile <code>TreeSet</code> și <code>TreeNode</code> ===
  
Pentru stocarea datelor necesare mulțimii, definim următoarea structură:
+
Pentru stocarea datelor necesare mulțimii, definim următoarele structuri:
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 +
struct TreeNode {
 +
    struct TreeNode * parent;
 +
    struct TreeNode * left;
 +
    struct TreeNode * right;
 +
    struct Server value;
 +
};
  
#define MAX_HASH 1000000
+
struct TreeSet {
struct HashSet {
+
     struct TreeNode * root;
     struct ArrayList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
+
     unsigned size;
     unsigned size; // numarul de elemente din multime
 
 
};
 
};
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=== Crearea unui <code>HashSet</code>===
+
=== Crearea unui <code>TreeSet</code> ===
 +
 
 +
Pentru a crea un <code>TreeSet</code>, definim următoarea funcție:
  
Pentru crearea unui <code>HashSet</code>, se definește următoarea funcție:
 
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 
/**
 
/**
  * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
+
  * Functia aloca memorie si intoarce un pointer la un nou TreeSet.
  * @return un pointer la o structura de tip HashSet.
+
  * @return adresa noului TreeSet.
 
  */
 
  */
struct HashSet * createHashSet();
+
struct TreeSet * createTreeSet();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Pentru crearea unui <code>HashSet</code> se urmează următorii pași:
+
Funcția trebuie să realizeze următorii pași:
# Se alocă memorie pentru un element de tip <code>struct HashSet</code> folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0).
+
# Se alocă memorie pentru un nou <code>struct TreeSet</code> ce trebuie inițializată automat cu 0.
# Se inițializează <code>size</code> cu 0.
+
# Se întoarce adresa alocată.
# Se întoarce adresa elementului de tip <code>struct HashSet</code>.
 
  
 
* Complexitate în '''timp''': O(1)
 
* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(MAX_HASH)
+
* Complexitate în '''spațiu''': O(1)
  
 
=== Interogarea numărului de elemente din mulțime ===
 
=== Interogarea numărului de elemente din mulțime ===
Linia 127: Linia 547:
 
  * @return numarul de elemente din multime.
 
  * @return numarul de elemente din multime.
 
  */
 
  */
unsigned hashSetSize(struct HashSet * set);
+
unsigned treeSetSize(struct TreeSet * set);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Linia 143: Linia 563:
 
  * @return 1 dacă mulțimea este goală, 0 în rest.
 
  * @return 1 dacă mulțimea este goală, 0 în rest.
 
  */
 
  */
char hashSetIsEmpty(struct HashSet * set);
+
char treeSetIsEmpty(struct TreeSet * set);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Linia 160: Linia 580:
 
  *  exista deja, functia nu are nici un efect.
 
  *  exista deja, functia nu are nici un efect.
 
  * @param set multimea in care trebuie adaugat elementul.
 
  * @param set multimea in care trebuie adaugat elementul.
  * @param person elementul ce trebuie adaugta.
+
  * @param server elementul ce trebuie adaugat.
 
  */
 
  */
void hashSetPut(struct HashSet * set, struct Person person);
+
void treeSetPut(struct TreeSet * set, struct Server server);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
Adăugarea se realizează în felul următor:
 
Adăugarea se realizează în felul următor:
# Se aplică funcția hash pe variabila <code>person</code>.
+
# Dacă dimensiunea mulțimii este 0, se alocă memorie pentru un nod nou <code>newNode</code> în care:
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
#* <code>value</code> va lua valoarea lui <code>server</code>
# Se folosește funcția <code>arrayListSearch</code> pentru a verifica dacă <code>person</code> există în listă (funcția <code>arrayListSearch</code> trebuie re-implementată pentru a se folosi de funcția <code>equals</code> pentru compararea elementelor).
+
#* <code>parent</code>, <code>left</code> și <code>right</code> vor lua valoarea <code>NULL</code>.
# Dacă valoarea întoarsă este -1 atunci <code>person</code> se adaugă în listă și <code>size</code> se incrementează cu 1.
+
# Câmpul <code>root</code> ia valoarea <code>newNode</code>, <code>size</code> se incrementează și funcția se încheie.
 +
# Altfel, se definește o variabilă de tip nod numită <code>tmpNode</code> care se inițializează cu valoarea câmpului <code>root</code>.
 +
# Într-o buclă infinită se realizează următorii pași:
 +
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este 0 (elementele sunt egale), funcția se încheie.
 +
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mare ca 0 și <code>tmpNode->left</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->left</code>.
 +
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mare ca 0 și <code>tmpNode->left</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->left</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.
 +
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mică ca 0 și <code>tmpNode->right</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->right</code>.
 +
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mică ca 0 și <code>tmpNode->right</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->right</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.
  
* 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 '''timp''': O(1) best case (element adăugat imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
 
* Complexitate în '''spațiu''': O(1)
 
* Complexitate în '''spațiu''': O(1)
 
<div class="regula"><span style="color: red; font-weight: bold">Atenție:</span> Deoarece vectorul <code>array</code> conține variabile de tip <code>struct ArrayList</code> și nu pointeri, pentru a folosi funcțiile definite în '''arrayList.h''' e necesară obținerea adresei variabilei de tip <code>struct ArrayList</code> folosind operatorul &.</div>
 
  
 
=== Eliminarea unui element din mulțime ===
 
=== Eliminarea unui element din mulțime ===
Linia 185: Linia 610:
 
  *  nu exista, functia nu are nici un efect.
 
  *  nu exista, functia nu are nici un efect.
 
  * @param set multimea din care trebuie eliminat elementul.
 
  * @param set multimea din care trebuie eliminat elementul.
  * @param person elementul ce trebuie eliminat.
+
  * @param server elementul ce trebuie eliminat.
 
  */
 
  */
void hashSetRemove(struct HashSet * set, struct Person person);
+
void treeSetRemove(struct TreeSet * set, struct Server server);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Eliminarea se realizează în felul următor:
+
Eliminarea se realizează în felul următor (o descriere în imagini poate fi găsită [http://www.algolist.net/Data_structures/Binary_search_tree/Removal 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):
# Se aplică funcția hash pe variabila <code>person</code>.
+
# Folosind un pointer la nod <code>tmpNode</code>, se folosește tehnica de la căutarea unui element în mulțime pentru a identifica nodul care memorează serverul <code>server</code>. 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, <code>tmpNode</code> va fi pointer la nodul ce trebuie eliminat. În plus, se va defini o variabilă de tip char <code>direction</code> 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 <code>tmpNode</code> este pointer la nodul ce trebuie șters, <code>direction</code> va fi 1 sau -1 în funcție de poziția nodului <code>tmpNode</code> față de nodul părinte.
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele <code>NULL</code> (nodul ce trebuie șters este frunză), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>NULL</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>NULL</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
# Se folosește funcția <code>arrayListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
+
# Dacă <code>tmpNode->left</code> este <code>NULL</code> și <code>tmpNode->right</code> este diferit de <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->right</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->right</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
# Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția <code>arrayListRemove</code> pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.
+
# Dacă <code>tmpNode->left</code> este diferit de <code>NULL</code> și <code>tmpNode->right</code> este <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->left</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->left</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
 +
# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele diferite de <code>NULL</code> (nodul ce trebuie șters are doi copii), atunci:
 +
#* Se foloște un al doilea pointer la nod numit <code>minSubtreeNode</code> cu care se caută cea mai mică valoare din subarborele din dreapta nodului <code>tmpNode</code>.
 +
#* <code>tmpNode->value</code> ia valoarea <code>minSubtreeNode->value</code> apoi se șterge <code>minSubtreeNode</code> după aceleași reguli de mai sus.
  
* 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 '''timp''': O(1) best case (element găsit imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
 
* Complexitate în '''spațiu''': O(1)
 
* Complexitate în '''spațiu''': O(1)
  
Linia 207: Linia 635:
 
  * Functia intoarce 1 daca elementul specificat exista in multime.
 
  * Functia intoarce 1 daca elementul specificat exista in multime.
 
  * @param set multimea in care se cauta elementul.
 
  * @param set multimea in care se cauta elementul.
  * @param person elementul cautat.
+
  * @param server elementul cautat.
 +
* @return 1 daca elementul exista in multime, 0 daca nu.
 
  */
 
  */
void hashSetContains(struct HashSet * set, struct Person person);
+
char treeSetContains(struct TreeSet * set, struct Server server);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Eliminarea se realizează în felul următor:
+
Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:
# Se aplică funcția hash pe variabila <code>person</code>.
+
# Se definește un pointer la nod numit <code>tmpNode</code> care se inițializează cu valoarea lui <code>root</code>.
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
# Cât timp <code>tmpNode</code> este diferit de <code>NULL</code>:
# Se folosește funcția <code>arrayListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
+
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este 0, se întoarce valoarea 1 (elementul a fost găsit).
# Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.
+
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este pozitiv, <code>tmpNode</code> ia valoarea lui <code>tmpNode->left</code>.
 +
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este negativ, <code>tmpNode</code> ia valoarea lui <code>tmpNode->right</code>.
 +
# Când s-a ieșit din buclă, se întoarce 0 (elementul nu a fost găsit).
  
* 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 '''timp''': O(1) best case (element găsit în rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
 
* Complexitate în '''spațiu''': O(1)
 
* Complexitate în '''spațiu''': O(1)
  
=== Ștergerea unui <code>HashSet</code>===
+
=== Ștergerea unui <code>TreeSet</code>===
  
Pentru dezalocarea unui <code>HashSet</code>, se definește următoarea funcție:
+
Pentru dezalocarea unui <code>TreeSet</code>, se definește următoarea funcție:
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 
/**
 
/**
  * Functia sterge hash set-ul specificat.
+
  * Functia sterge tree set-ul specificat.
  * @param set hash set-ul ce trebuie sters.
+
  * @param set tree set-ul ce trebuie sters.
 
  */
 
  */
void deleteHashSet(struct HashSet * set);
+
void deleteTreeSet(struct TreeSet * set);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Pentru ștergerea unui <code>HashSet</code> se urmează următorii pași:
+
Pentru ștergerea unui <code>TreeSet</code> se urmează următorii pași:
# Se iterează peste tot <code>array</code>-ul, ștergându-se toate nodurile din toate listele.
+
# 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 <code>HashSet</code>.
+
# Se șterge memoria alocată pentru structura de tip <code>TreeSet</code>.
  
* Complexitate în '''timp''': O(MAX_HASH)
+
* Complexitate în '''timp''': O(n)
 
* Complexitate în '''spațiu''': O(1)
 
* Complexitate în '''spațiu''': O(1)
  
 +
-->
 +
 +
<!--
 
= Exerciții =
 
= Exerciții =
  
Linia 244: Linia 678:
  
 
<ol>
 
<ol>
<li> Dându-se fișierele [[Fișier:linkedList.h]], [[Fișier:linkedList.c]] și header-ele <code>hashSet.h</code> și <code>person.h</code> de mai jos, implementați toate funcțiile definite într-un fișier sursă numit <code>hashSet.c</code>:
+
<li> Dându-se fișierele [[Fișier:linkedList.h]], [[Fișier:linkedList.c]] și header-ele <code>hashSet.h</code> și <code>person.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>person.c</code> și <code>hashSet.c</code>:
 
<ul><li> <code>person.h</code>:
 
<ul><li> <code>person.h</code>:
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
Linia 281: Linia 715:
 
<li> <code>hashset.h</code>:
 
<li> <code>hashset.h</code>:
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
#ifndef HASHSET_H
+
#ifndef HASH_SET_H
#define HASHSET_H
+
#define HASH_SET_H
 +
 
 +
#include "linkedList.h"
 +
#include "person.h"
  
 
#define MAX_HASH 1000000
 
#define MAX_HASH 1000000
 +
 
struct HashSet {
 
struct HashSet {
     struct ArrayList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
+
     struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
 
     unsigned size; // numarul de elemente din multime
 
     unsigned size; // numarul de elemente din multime
 
};
 
};
 
+
 
/**
 
/**
 
  * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
 
  * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
Linia 295: Linia 733:
 
  */
 
  */
 
struct HashSet * createHashSet();
 
struct HashSet * createHashSet();
 
+
 
/**
 
/**
 
  * Functia intoarce numarul de elemente din multime.
 
  * Functia intoarce numarul de elemente din multime.
Linia 302: Linia 740:
 
  */
 
  */
 
unsigned hashSetSize(struct HashSet * set);
 
unsigned hashSetSize(struct HashSet * set);
 
+
 
/**
 
/**
 
  * Functia intoarce 1 dacă mulțimea nu conține nici un element.
 
  * Functia intoarce 1 dacă mulțimea nu conține nici un element.
Linia 309: Linia 747:
 
  */
 
  */
 
char hashSetIsEmpty(struct HashSet * set);
 
char hashSetIsEmpty(struct HashSet * set);
 
+
 
/**
 
/**
 
  * Functia adauga elementul dat in multime daca acesta nu exista. Daca
 
  * Functia adauga elementul dat in multime daca acesta nu exista. Daca
Linia 317: Linia 755:
 
  */
 
  */
 
void hashSetPut(struct HashSet * set, struct Person person);
 
void hashSetPut(struct HashSet * set, struct Person person);
 
+
 
/**
 
/**
 
  * Functia elimina elementul dat din multime daca acesta exista. Daca
 
  * Functia elimina elementul dat din multime daca acesta exista. Daca
Linia 325: Linia 763:
 
  */
 
  */
 
void hashSetRemove(struct HashSet * set, struct Person person);
 
void hashSetRemove(struct HashSet * set, struct Person person);
 
+
 
/**
 
/**
 
  * Functia intoarce 1 daca elementul specificat exista in multime.
 
  * Functia intoarce 1 daca elementul specificat exista in multime.
 
  * @param set multimea in care se cauta elementul.
 
  * @param set multimea in care se cauta elementul.
 
  * @param person elementul cautat.
 
  * @param person elementul cautat.
 +
* @return 1 daca elementul exista in multime, 0 daca nu.
 
  */
 
  */
void hashSetContains(struct HashSet * set, struct Person person);
+
char hashSetContains(struct HashSet * set, struct Person person);
 
+
 
/**
 
/**
 
  * Functia sterge hash set-ul specificat.
 
  * Functia sterge hash set-ul specificat.
Linia 338: Linia 777:
 
  */
 
  */
 
void deleteHashSet(struct HashSet * set);
 
void deleteHashSet(struct HashSet * set);
 +
 +
#endif
 +
</syntaxhighlight>
 +
</li>
 +
</ul>
 +
</li>
 +
<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Person readFromKeyboard()</code> și o altă funcție <code>main</code> 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.</li>
 +
</ol>
 +
 +
== Săptămâna 2 ==
 +
 +
<ol>
 +
<li> Dându-se header-ele <code>treeSet.h</code> și <code>server.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>server.c</code> și <code>treeSet.c</code>:
 +
<ul><li> <code>server.h</code>:
 +
<syntaxhighlight lang="C">
 +
#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 server2);
 +
 +
#endif
 +
</syntaxhighlight>
 +
</li>
 +
<li> <code>treeSet.h</code>:
 +
<syntaxhighlight lang="C">
 +
#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
 
#endif
 
</syntaxhighlight>
 
</syntaxhighlight>
Linia 344: Linia 905:
 
</ul>
 
</ul>
 
</li>
 
</li>
<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Person readFromKeyboard()</code> și o altă funcție <code>main</code> 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.</li>
+
<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Server readFromKeyboard()</code> și o altă funcție <code>main</code> 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.</li>
 
</ol>
 
</ol>
 +
 +
-->
 +
 +
== Implementarea de mulțimi cu arbori binari de căutare (BST)  ==
 +
 +
Pentru a adăuga elementele unei mulțimi într-un arbore binar de căutare, pe tipul respectiv trebuie definită o relație de ordine. Această relație este definită deja în STL prin structurile <code>std::less</code>, <code>std::greater</code>, <code>std::less_equal</code> și <code>std::greater_equal</code>. Pentru structura de date de tip mulțime implementată cu BST, este necesară definirea doar a structurii <code>std::less</code>, și doar pentru clase sau structuri proprii pentru care nu există deja implementare în STL. Două elemente '''a''' și '''b''' de tip '''T''' sunt considerate egale dacă <code>!less<T>(a, b) && !less<T>(b,a)</code>. Altfel spus, dacă nici unul nu este strict mai mic decât celălalt. Astfel, folosind operația de comparație, putem defini și egalitatea.
 +
 +
Definiția acestei structuri este:
 +
 +
<syntaxhighlight lang="cpp">
 +
namespace std {
 +
    template<class T>
 +
    struct less {
 +
        /**
 +
        * Metoda compară cele două elemente și întoarce true dacă primul element este strict mai mic
 +
        * decât al doilea.
 +
        * @param first primul element de comparat.
 +
        * @param second al doilea element de comparat.
 +
        * @return true dacă primul element este strict mai mic decât al doilea.
 +
        */
 +
        bool operator() (const T& first, const T& second) const;
 +
    };
 +
}
 +
</syntaxhighlight>
 +
 +
Să definim noile elemente de sintaxă:
 +
# <code>operator()</code> este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa <code>less<SomeType>(valueOfSomeType1, valueOfSomeType2)</code> pentru a apela metoda <code>operator()</code> din structura <code>less<T></code>
 +
# <code>const T &first</code> conține două elemente de noutate:
 +
#* cuvântul cheie <code>const</code> face ca elementul să nu poată fi modificat de metodă (ci doar citit)
 +
#* operatorul <code>&</code> se numește ''referință'', similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila <code>first</code> fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
 +
# cuvântul cheie <code>const</code> de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).
 +
 +
=== Clasa <code>std::set</code> ===
 +
 +
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).
 +
 +
 +
Clasa din STL care implementează mulțimi folosind arbori binari de căutare poartă numele de [http://en.cppreference.com/w/cpp/container/set std::set] și este definită în header-ul <code>set</code>. Mai departe vom exemplifica definirea funcției de comparație pentru utilizarea unui <code>std::set</code> în scopul stocării unor elemente de tip <code>struct Person</code>:
 +
 +
<syntaxhighlight lang="cpp">
 +
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];
 +
};
 +
</syntaxhighlight>
 +
 +
Să definim comparatorul! 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), prin urmare vom compara două persoane folosind strict acest câmp:
 +
 +
<syntaxhighlight lang="cpp">
 +
namespace std {
 +
    template<>
 +
    struct less<Person> {
 +
        /**
 +
        * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
 +
        * @param person1 prima persoana de comparat.
 +
        * @param person2 a doua persoana de comparat.
 +
        * @return true daca CNP-urile celor doua persoane sunt identice.
 +
        */
 +
        bool operator()(const Person &person1, const Person &person2) const {
 +
            return strcmp(person1.cnp, person2.cnp) < 0;
 +
        }
 +
    };
 +
</syntaxhighlight>
 +
 +
 +
=== Crearea unui <code>std::set</code> ===
 +
 +
Pentru instanțierea unui obiect de tip <code>std::set</code>, se folosește constructorul fără argumente:
 +
 +
<syntaxhighlight lang="cpp" highlight="5">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<int> mySet;
 +
    printf("My set is empty: %d\n", mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
=== Interogarea numărului de elemente din mulțime ===
 +
 +
Pentru interogarea numărului de elemente din mulțime sunt definite:
 +
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce numarul de elemente din multime.
 +
* @return numarul de elemente din multime.
 +
*/
 +
size_t size();
 +
 +
/**
 +
* Metoda intoarce true daca multimea e goala.
 +
* @return true daca multimea e goala
 +
*/
 +
bool empty();
 +
</syntaxhighlight>
 +
 +
Exemplu:
 +
 +
<syntaxhighlight lang="cpp" highlight="10">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
=== Adăugarea unui element în mulțime ===
 +
 +
Pentru operația de adăugare se definește următoarea metodă:
 +
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 +
*  exista deja, functia nu are nici un efect.
 +
* @param element elementul ce trebuie adaugat.
 +
*/
 +
void insert(T element);
 +
</syntaxhighlight>
 +
 +
Exemplu:
 +
 +
<syntaxhighlight lang="cpp" highlight="6-8">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
=== Eliminarea unui element din mulțime ===
 +
 +
Pentru operația de eliminare se definește următoarea metodă:
 +
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda elimina elementul dat din multime daca acesta exista. Daca
 +
*  nu exista, functia nu are nici un efect.
 +
* @param element elementul ce trebuie eliminat.
 +
*/
 +
void erase(T element);
 +
</syntaxhighlight>
 +
 +
Exemplu:
 +
 +
<syntaxhighlight lang="cpp" highlight="12">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
 +
    mySet.erase(1);
 +
 +
    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
 +
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
=== Verificarea dacă un element există în mulțime ===
 +
 +
Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:
 +
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 +
* @param element elementul cautat.
 +
* @return 1 daca elementul exista in multime, 0 daca nu.
 +
*/
 +
size_t count(T element);
 +
</syntaxhighlight>
 +
 +
Exemplu:
 +
 +
<syntaxhighlight lang="cpp" highlight="10,11">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<float> mySet;
 +
    mySet.insert(1);
 +
    mySet.insert(1.1);
 +
    mySet.insert(1);
 +
 +
    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
 +
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
=== Iterarea peste elementele mulțimii ===
 +
 +
Pentru a itera peste elementele din mulțime se folosesc iteratori. Iteratorul va oferi întotdeauna elementele în ordine crescătoare, conform definiției operației <code>std::less</code>.
 +
 +
<syntaxhighlight lang="cpp" highlight="12">
 +
#include<set>
 +
#include<cstdio>
 +
 +
int main() {
 +
    std::set<int> mySet;
 +
    mySet.insert(10);
 +
    mySet.insert(13);
 +
    mySet.insert(-5);
 +
    mySet.insert(-5);
 +
    mySet.insert(0);
 +
 +
    for(std::set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
 +
        printf("%d ", *it);
 +
    }
 +
    printf("\n");
 +
    return 0;
 +
}
 +
</syntaxhighlight>

Versiunea curentă din 26 aprilie 2017 22:16

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

Șiruri de caractere în C++ - clasa std::string

Ca să putem folosi cu ușurință structurile de date definite în STL pentru a stoca șiruri de caractere, introducem clasa std::string definită în header-ul string (a nu se confunda cu cstring unde sunt definite funcțiile de manipulare de stringuri din C).

Crearea unui std::string

Pentru a instanția un obiect de tip std::string, există mai multe variante:

  1. Utilizarea constructorului:
    #include <string>
    #include <cstdio>
    
    using std::string;
    
    int main() {
        string sentence("This is a sentence represented by a string object");
    
        printf("%s\n", sentence.c_str());
        return 0;
    }
    
  2. Utilizarea operatorului de atribuire:
    #include <string>
    #include <cstdio>
    
    using std::string;
    
    int main() {
        string sentence = "This is a sentence represented by a string object";
    
        printf("%s\n", sentence.c_str());
        return 0;
    }
    

Citirea unui std::string

Pentru a citi dintr-un stream un șir de caractere cu funcția scanf, va fi nevoie în continuare de un array de caractere, dar acesta va fi folosit pentru apelul constructorului clasei std::string.

#include <string>
#include <cstdio>

using std::string;

int main() {
    char buffer[128];
    scanf("%[^\n]", buffer);
    string line(buffer);

    printf("This is the line from the keyboard: '%s'\n", line.c_str());
    return 0;
}


Copierea unui std::string

Un obiect de tip std::string se copiază foarte simplu, fără a fi nevoie de utilizarea funcției strcpy:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string sentence = "This is a sentence represented by a string object";
    string copy = sentence;

    printf("This is the sentence: '%s' and this is the copy: '%s'\n", sentence.c_str(), copy.c_str());
    return 0;
}

Afișarea unui std::string

Pentru a afișa un șir de caractere cu funcția printf, va fi nevoie să obținem din obiectul de tip std::string de șirul de caractere în format char*. Acest lucru se realizează cu metoda c_str():

#include <string>
#include <cstdio>

using std::string;

int main() {
    string line = "This is some line!";

    printf("This is the line: '%s'\n", line.c_str());
    return 0;
}

Compararea a două obiecte de tip std::string

Compararea se poate realiza simplu, fără a utiliza funcția strcmp, ci folosind operatorii ==, !=, <, >, etc:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string text1 = "Some text";
    string text2 = "Some text";

    if(text1 == text2) {
        printf("The texts are identical\n");
    } else {
        printf("The texts are NOT identical\n");
    }
    return 0;
}

Modificarea obiectelor de tip std::string

Pentru a accesa caracterele individuale dintr-un obiect de tip std::string, se poate utiliza, ca și în cazul clasei std::vector, operatorul []:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string text1 = "Ana are un mar";
    text1[11] = 'c';
    text1[13] = 'l';

    printf("Textul modificat: %s\n", text1.c_str());

    return 0;
}

Mulțimea

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

Set.png

Mulțimea are următoarele proprietăți:

  1. Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
  2. Numărul de elemente ce poate fi stocat de structură este nelimitat.
  3. Elementele stocate în mulțime sunt de același fel.
  4. 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ă:

  1. Interogarea numărului de elemente din mulțime.
  2. Verificarea dacă mulțimea este goală.
  3. Adăugarea unui element în mulțime (insert).
  4. Verificarea dacă un element există în mulțime (count).
  5. Eliminarea unui element din mulțime (erase).

Pentru a verifica egalitatea a două elemente vom specializa o structură equal_to care va întoarce true dacă cele două argumente sunt egale și false 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 ==:

namespace std {
    template <class T>
    struct equal_to {
        /**
         * Functia verifica daca valorile value1 si value2 sunt egale.
         * @param value1 prima valoare de comparat.
         * @param value2 a doua valoare de comparat.
         * @return true daca cele doua valori sunt egale si false in rest.
         */
         bool equal_to(const T& value1, const T& value2) const;
    }
}

Atenție, pentru a putea fi folosită de clasele de tip mulțime din STL, această structură trebuie declarată în interiorul namespace-ului std.

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 equal_to astfel încât dacă două elemente e1 și e2 sunt considerate egale (equal_to(e1, e1) == true), atunci obligatoriu hash(e1) == hash(e2):

namespace std {
    template<class T> 
    struct hash {
        /**
         * Metoda calculeaza un hashcode pentru elementul element.
         * @param element referinta la un element de tip T pentru care se calculeaza hash-ul
         * @return hashcode-ul calculat.
         */
        std::size_t operator()(T const& element) const;
    };
}

Să definim noile elemente de sintaxă:

  1. std::size_t este un tip de dată ce reprezintă o dimensiune (deci este un număr întreg fără semn), iar dimensiunea lui în biți depinde de compilator (poate fi sinonim cu uint32_t sau cu uint64_t); un cod hash este reprezentat ca o valoare de tip std::size_t
  2. operator() este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa hash<SomeType>(someValueOfSomeType) pentru a apela metoda operator() din structura hash<T>
  3. T const &element conține două elemente de noutate:
    • cuvântul cheie const face ca elementul să nu poată fi modificat de metodă (ci doar citit)
    • operatorul & se numește referință, similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila element fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
  4. cuvântul cheie const de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).

Clasa std::unordered_set

Clasa din STL care implementează mulțimi folosind funcții hash poartă numele de std::unordered_set și este definită în header-ul unordered_set. Mai departe vom exemplifica definirea funcțiilor de egalitate și hash pentru utilizarea unui std::unordered_set în scopul stocării unor elemente de tip struct Person:

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 equal să întoarcă 1 dacă cnp-urile celor două argumente de tip struct Person sunt identice:

namespace std {
    template<>
    struct equal_to<Person> {
        /**
         * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
         * @param person1 prima persoana de comparat.
         * @param person2 a doua persoana de comparat.
         * @return true daca CNP-urile celor doua persoane sunt identice.
         */
        bool operator()(const Person &person1, const Person &person2) const {
            return strcmp(person1.cnp, person2.cnp) == 0;
        }
    };

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

namespace std {
    template<>
    struct hash<Person> {
        /**
         * Functie hash pentru structurile de tip Person.
         * @param person peroana pentru care se doreste codul hash.
         * @return codul hash al persoanei person
         */
        size_t operator()(Person const & person) const {
            return (size_t) atoi(person.cnp + 7);
        }
    };
    
}

Crearea unui std::unordered_set

Pentru instanțierea unui obiect de tip std::unordered_set, se folosește constructorul fără argumente:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<int> mySet;
    printf("My set is empty: %d\n", mySet.empty());
    return 0;
}

Interogarea numărului de elemente din mulțime

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

/**
 * Metoda intoarce numarul de elemente din multime.
 * @return numarul de elemente din multime.
 */
size_t size();

/**
 * Metoda intoarce true daca multimea e goala.
 * @return true daca multimea e goala
 */
bool empty();

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Adăugarea unui element în mulțime

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

/**
 * Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 *  exista deja, functia nu are nici un efect.
 * @param element elementul ce trebuie adaugat.
 */
void insert(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Eliminarea unui element din mulțime

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

/**
 * Metoda elimina elementul dat din multime daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param element elementul ce trebuie eliminat.
 */
void erase(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    mySet.erase(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    return 0;
}

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

Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:

/**
 * Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 * @param element elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
size_t count(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
    return 0;
}

Iterarea peste elementele mulțimii

Pentru a itera peste elementele din mulțime se folosesc iteratori:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<int> mySet;
    mySet.insert(10);
    mySet.insert(13);
    mySet.insert(-5);
    mySet.insert(-5);
    mySet.insert(0);

    for(std::unordered_set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    return 0;
}



Implementarea de mulțimi cu arbori binari de căutare (BST)

Pentru a adăuga elementele unei mulțimi într-un arbore binar de căutare, pe tipul respectiv trebuie definită o relație de ordine. Această relație este definită deja în STL prin structurile std::less, std::greater, std::less_equal și std::greater_equal. Pentru structura de date de tip mulțime implementată cu BST, este necesară definirea doar a structurii std::less, și doar pentru clase sau structuri proprii pentru care nu există deja implementare în STL. Două elemente a și b de tip T sunt considerate egale dacă !less<T>(a, b) && !less<T>(b,a). Altfel spus, dacă nici unul nu este strict mai mic decât celălalt. Astfel, folosind operația de comparație, putem defini și egalitatea.

Definiția acestei structuri este:

namespace std {
    template<class T> 
    struct less {
        /**
         * Metoda compară cele două elemente și întoarce true dacă primul element este strict mai mic
         * decât al doilea.
         * @param first primul element de comparat.
         * @param second al doilea element de comparat.
         * @return true dacă primul element este strict mai mic decât al doilea.
         */
         bool operator() (const T& first, const T& second) const;
    };
}

Să definim noile elemente de sintaxă:

  1. operator() este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa less<SomeType>(valueOfSomeType1, valueOfSomeType2) pentru a apela metoda operator() din structura less<T>
  2. const T &first conține două elemente de noutate:
    • cuvântul cheie const face ca elementul să nu poată fi modificat de metodă (ci doar citit)
    • operatorul & se numește referință, similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila first fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
  3. cuvântul cheie const de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).

Clasa std::set

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


Clasa din STL care implementează mulțimi folosind arbori binari de căutare poartă numele de std::set și este definită în header-ul set. Mai departe vom exemplifica definirea funcției de comparație pentru utilizarea unui std::set în scopul stocării unor elemente de tip struct Person:

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

Să definim comparatorul! 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), prin urmare vom compara două persoane folosind strict acest câmp:

namespace std {
    template<>
    struct less<Person> {
        /**
         * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
         * @param person1 prima persoana de comparat.
         * @param person2 a doua persoana de comparat.
         * @return true daca CNP-urile celor doua persoane sunt identice.
         */
        bool operator()(const Person &person1, const Person &person2) const {
            return strcmp(person1.cnp, person2.cnp) < 0;
        }
    };


Crearea unui std::set

Pentru instanțierea unui obiect de tip std::set, se folosește constructorul fără argumente:

#include<set>
#include<cstdio>

int main() {
    std::set<int> mySet;
    printf("My set is empty: %d\n", mySet.empty());
    return 0;
}

Interogarea numărului de elemente din mulțime

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

/**
 * Metoda intoarce numarul de elemente din multime.
 * @return numarul de elemente din multime.
 */
size_t size();

/**
 * Metoda intoarce true daca multimea e goala.
 * @return true daca multimea e goala
 */
bool empty();

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Adăugarea unui element în mulțime

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

/**
 * Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 *  exista deja, functia nu are nici un efect.
 * @param element elementul ce trebuie adaugat.
 */
void insert(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Eliminarea unui element din mulțime

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

/**
 * Metoda elimina elementul dat din multime daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param element elementul ce trebuie eliminat.
 */
void erase(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    mySet.erase(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    return 0;
}

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

Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:

/**
 * Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 * @param element elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
size_t count(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
    return 0;
}

Iterarea peste elementele mulțimii

Pentru a itera peste elementele din mulțime se folosesc iteratori. Iteratorul va oferi întotdeauna elementele în ordine crescătoare, conform definiției operației std::less.

#include<set>
#include<cstdio>

int main() {
    std::set<int> mySet;
    mySet.insert(10);
    mySet.insert(13);
    mySet.insert(-5);
    mySet.insert(-5);
    mySet.insert(0);

    for(std::set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    return 0;
}