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

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 15 versiuni intermediare efectuate de același utilizator)
Linia 31: Linia 31:
 
=== Tipul de date și funcțiile de bază ===
 
=== Tipul de date și funcțiile de bază ===
  
−
În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip "persoană" (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:
+
În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip <code>Person</code> (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:
  
−
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
struct Person {
 
struct Person {
−
     char firstName[30];
+
     std::string firstName;
−
     char lastName[30];
+
     std::string lastName;
−
     char idNumber[9]; // seria si numarul de buletin
+
     std::string idNumber; // seria si numarul de buletin
−
     char address[255];
+
     std::string address;
−
     char birthday[11];
+
     std::string birthday;
−
     char cnp[14];
+
     std::string cnp;
 
};
 
};
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
Funcțiile de hash și de egalitate pentru clasa <code>std::string</code> sunt deja implementate în STL. Dacă totuși aveți nevoie de a folosi niste funcții proprii, acestea se scriu în același fel ca cele pentru mulțimi împlementate cu funcții hash (vezi [[SDA Lucrarea 5]]).
 +
 +
=== Clasa <code>std::unordered_map</code> ===
 +
 +
Pentru stocarea datelor necesare map-ului, În STL se definește clasa <code>std::unordered_map</code> în header-ul <code>unordered_map</code>. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:
  
−
Pentru a implementa o funcție hash pentru variabilele de tip <code>char *</code> (cheia este CNP-ul care este stocat ca un șir de caractere), avem întâi nevoie să definim operația de egalitate:
+
<syntaxhighlight lang="cpp">
 +
#include <unordered_map>
 +
#include <string>
  
−
<syntaxhighlight lang="C">
+
int main() {
 +
    std::unorder_map<std::string, Person> myMap; // un map de la string la Person
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Crearea unui <code>std::unordered_map</code>===
 +
 
 +
Pentru crearea unui <code>std::unordered_map</code>, se definește următorul constructor:
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
−
  * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
+
  * Constructorul creeaza un map nou și inițializează structurile de date interne.
−
* @param cnp1 primul CNP de comparat.
 
−
* @param cnp2 al doilea CNP de comparat.
 
−
* @return 1 daca CNP-urile celor doua persoane sunt identice.
 
 
  */
 
  */
−
char equals(char * cnp1, char * cnp2);
+
unordered_map();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Mai departe definim funcția hash pentru un CNP.
+
Exemplu:
 +
<syntaxhighlight lang="cpp" highlight="5">
 +
#include <unordered_map>
 +
#include <string>
  
−
Pentru a putea implementa un map cu funcții hash trebuie ca hash-ul maxim să fie o valoare rezonabilă pentru a putea aloca memorie cu dimensiunea valorii respective.
+
int main() {
 +
    std::unorder_map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap["190010112345"] = person;
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Interogarea numărului de elemente din map ===
  
−
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]):
+
Pentru interogarea numărului de elemente din map se definesc:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce numarul de elemente din map.
 +
* @return numarul de elemente din map.
 +
*/
 +
uint64_t size();
  
−
<syntaxhighlight lang="C">
 
 
/**
 
/**
−
  * Functie hash pentru un CNP stocat ca string.
+
  * Metoda intoarce true dacă map-ul nu conține nici un element.
−
* @param cnp CNP-ul pentru care se doreste codul hash.
+
  * @return true dacă map-ul este gol, false în rest.
−
  * @return codul hash al CNP-ului.
 
 
  */
 
  */
−
unsigned hash(char * cnp);
+
bool empty();
 +
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
În continuare vom utiliza pentru implementarea unui Hash Map o structură de date de tip secvență împlementată cu liste (LinkedList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:
+
Exemplu:
−
* [[Fișier:hashMapLinkedList.h]]
+
<syntaxhighlight lang="cpp" highlight="9,10">
−
* [[Fișier:hashMapLinkedList.c]]
+
#include <unordered_map>
 +
#include <string>
 +
#include <cstdio>
  
−
Elementul stocat în listă este un element de tip <code>Pair</code> care stochează împreună o cheie cu o valoare:
+
int main() {
−
<syntaxhighlight lang="C">
+
    std::unorder_map<std::string, Person> myMap;
−
struct Pair {
+
    Person person;
−
     char * key; /* CNP-ul */
+
    myMap["190010112345"] = person;
−
     struct Person value; /* Persoana */
+
    printf("Map-ul contine %lu elemente.\n", myMap.size());
−
};
+
     printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
     return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
=== Structura <code>HashMap</code> ===
+
=== Adăugarea unei perechi cheie-valoare în map ===
 +
 
 +
Pentru operația de adăugare se definesc următoarele metode:
  
−
Pentru stocarea datelor necesare map-ului, definim următoarea structură:
+
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda adauga perechea data in map daca cheia nu exista.
 +
* @param keyValuePair o pereche cheie-valoare
 +
* @return o pereche iterator-bool, unde iteratorul identifică perechea
 +
*  introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 +
*  perechea a fost introdusa sau nu (pentru ca exista deja).
 +
*/
 +
pair<iterator, bool> insert(pair<K, V> keyValuePair);
  
−
<syntaxhighlight lang="C">
+
/**
 +
* Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la
 +
*  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 +
*  neutră.
 +
* @param key cheia ce se dorește adăugată (sau interogată).
 +
* @return o referință la valoarea asociată cheii.
 +
*/
 +
V & operator[](K key);
 +
</syntaxhighlight>
  
−
#define MAX_HASH 1000000
+
Exemplu:
−
struct HashMap {
+
<syntaxhighlight lang="cpp" highlight="8-9">
−
     struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
+
#include <unordered_map>
−
     unsigned size; // numarul de elemente din map
+
#include <string>
−
};
+
#include <cstdio>
 +
 +
int main() {
 +
    std::unorder_map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
     myMap["190010112345"] = person;
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
     return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
=== Crearea unui <code>HashMap</code>===
+
=== Eliminarea unei chei din map ===
 +
 
 +
Pentru operația de eliminare se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda elimina cheia data din map daca acesta exista. Daca
 +
*  nu exista, functia nu are nici un efect.
 +
* @param key cheia ce trebuie eliminata.
 +
*/
 +
void erase(K key);
  
−
Pentru crearea unui <code>HashMap</code>, se definește următoarea funcție:
 
−
<syntaxhighlight lang="C">
 
 
/**
 
/**
−
  * Functia creeaza un hashMap nou si intoarce adresa de memorie alocata.
+
  * Metoda sterge toate elementele din map.
−
* @return un pointer la o structura de tip HashMap.
 
 
  */
 
  */
−
struct HashMap * createHashMap();
+
void clear();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Pentru crearea unui <code>HashMap</code> se urmează următorii pași:
+
Exemplu:
−
# Se alocă memorie pentru un element de tip <code>struct HashMap</code> folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0).
+
<syntaxhighlight lang="cpp" highlight="10,13,16">
−
# Se inițializează <code>size</code> cu 0.
+
#include <unordered_map>
−
# Se întoarce adresa elementului de tip <code>struct HashMap</code>.
+
#include <string>
 +
#include <cstdio>
 +
 +
int main() {
 +
    std::unorder_map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
    myMap["190010112345"] = person;
 +
    myMap.erase("098764321987");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.erase("191010112345");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.clear();
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
 
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
−
* Complexitate în '''timp''': O(1)
+
=== Verificarea dacă o cheie există în map ===
−
* Complexitate în '''spațiu''': O(MAX_HASH)
 
  
−
=== Interogarea numărului de elemente din map ===
+
Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
 +
* @param key cheia cautata.
 +
* @return 1 daca cheia exista in map, 0 daca nu.
 +
*/
 +
uint64_t count(K key);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
<syntaxhighlight lang="cpp" highlight="14,15">
 +
#include <unordered_map>
 +
#include <string>
 +
#include <cstdio>
 +
 +
int main() {
 +
    std::unorder_map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
    myMap["190010112345"] = person;
 +
    myMap.erase("098764321987");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.erase("191010112345");
 +
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
 +
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.clear();
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Căutarea unei valori după cheie ===
  
−
Pentru interogarea numărului de elemente din map definim:
+
Pentru a căuta o valoare după cheie, se definește următoarele metode:
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 
/**
 
/**
−
  * Functia intoarce numarul de elemente din map.
+
  * Metoda intoarce a referinta la valoarea asociată cheii key.
−
  * @param map map-ul pentru care se cere dimensiunea.
+
* @param key cheia cautata.
−
  * @return numarul de elemente din map.
+
* @return valoarea asociată cheii, dacă aceasta există,
 +
*  sau se generează o eroare daca cheia nu exista in map.
 +
*/
 +
V& at(K key);
 +
 
 +
/**
 +
* Operatorul intoarce o referinta la valoarea asociată cheii key.
 +
  * @param key cheia cautata.
 +
  * @return valoarea asociată cheii, dacă aceasta există,
 +
*  sau o valoare neutra daca nu există (care se si adauga in map).
 
  */
 
  */
−
unsigned hashMapSize(struct HashMap * map);
+
 
 +
V& operator[](K key);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Funcția va întoarce valoarea din câmpul <code>size</code> din structură.
+
Exemplu:
 +
<syntaxhighlight lang="cpp" highlight="10,11">
 +
#include <unordered_map>
 +
#include <string>
 +
#include <cstdio>
 +
 +
int main() {
 +
    std::unorder_map<std::string, Person> myMap;
 +
    Person person;
 +
    person.firstName = "Ghita";
 +
    myMap.insert({"191010112345", person});
 +
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
 +
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
−
* Complexitate în '''timp''': O(1)
 
−
* Complexitate în '''spațiu''': O(1)
 
  
−
Pentru a afla dacă map-ul este gol definim:
+
== Implementarea de structuri asociative cu arbori binari de căutare  ==
  
−
<syntaxhighlight lang="C">
+
Definirea arborilor binari de căutare și a proprietăților lor s-au făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)]]).
 +
 
 +
=== Clasa <code>std::map</code> ===
 +
 
 +
Pentru stocarea datelor necesare map-ului, În STL se definește clasa <code>std::map</code> în header-ul <code>map</code>. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#include <map>
 +
#include <string>
 +
 
 +
int main() {
 +
    std::map<std::string, Person> myMap; // un map de la string la Person
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
=== Crearea unui <code>std::map</code>===
 +
 
 +
Pentru crearea unui <code>std::map</code>, se definește următorul constructor:
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
−
  * Functia intoarce 1 dacă map-ul nu conține nici un element.
+
  * Constructorul creeaza un map nou și inițializează structurile de date interne.
−
* @param map map-ul de interes.
 
−
* @return 1 dacă map-ul este gol, 0 în rest.
 
 
  */
 
  */
−
char hashMapIsEmpty(struct HashMap * map);
+
map();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Funcția va întoarce 1 dacă valoarea din câmpul <code>size</code> este 0.
+
Exemplu:
 +
<syntaxhighlight lang="cpp" highlight="5">
 +
#include <map>
 +
#include <string>
  
−
* Complexitate în '''timp''': O(1)
+
int main() {
−
* Complexitate în '''spațiu''': O(1)
+
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap["190010112345"] = person;
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
−
=== Adăugarea unei perechi cheie-valoare în map ===
+
=== Interogarea numărului de elemente din map ===
 +
 
 +
Pentru interogarea numărului de elemente din map se definesc:
  
−
Pentru operația de adăugare se definește următoarea funcție:
+
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce numarul de elemente din map.
 +
* @return numarul de elemente din map.
 +
*/
 +
uint64_t size();
  
−
<syntaxhighlight lang="C">
 
 
/**
 
/**
−
  * Functia adauga perechea data in map daca cheia nu exista. Daca
+
  * Metoda intoarce true dacă map-ul nu conține nici un element.
−
*  cheia exista deja, valoarea si cheia sunt actualizate.
+
  * @return true dacă map-ul este gol, false în rest.
−
  * @param map map-ul in care trebuie adaugata perechea.
 
−
* @param key cnp-ul folosit pe post de cheie.
 
−
* @param value persoana asociata CNP-ului.
 
 
  */
 
  */
−
void hashMapPut(struct HashMap * map, char * key, struct Person value);
+
bool empty();
 +
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Adăugarea se realizează în felul următor:
+
Exemplu:
−
# Se aplică funcția hash pe variabila <code>key</code>.
+
<syntaxhighlight lang="cpp" highlight="9,10">
−
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
#include <map>
−
# Se iterează peste nodurile listei căutând cheia <code>key</code> în pereche, folosind funcția <code>equals</code>. Dacă cheia este găsită, atunci cheia și valoarea din pereche sunt actualizate cu valorile argumentelor <code>key</code> și <code>value</code> și funcția se încheie; altfel, se crează un nod nou care se adaugă listei care va conține perechea <code>key</code> - <code>value</code>, dimensiunea listei și dimensiunea map-ului se incrementează.
+
#include <string>
 +
#include <cstdio>
 +
 
 +
int main() {
 +
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap["190010112345"] = person;
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
−
* 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).
+
=== Adăugarea unei perechi cheie-valoare în map ===
−
* 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 LinkedList</code> și nu pointeri, pentru a folosi funcțiile definite în '''hashMapLinkedList.h''' e necesară obținerea adresei variabilei de tip <code>struct LinkedList</code> folosind operatorul &.</div>
+
Pentru operația de adăugare se definesc următoarele metode:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda adauga perechea data in map daca cheia nu exista.
 +
* @param keyValuePair o pereche cheie-valoare
 +
* @return o pereche iterator-bool, unde iteratorul identifică perechea
 +
*  introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 +
*  perechea a fost introdusa sau nu (pentru ca exista deja).
 +
*/
 +
pair<iterator, bool> insert(pair<K, V> keyValuePair);
 +
 
 +
/**
 +
* Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la
 +
*  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 +
*  neutră.
 +
* @param key cheia ce se dorește adăugată (sau interogată).
 +
* @return o referință la valoarea asociată cheii.
 +
*/
 +
V & operator[](K key);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
<syntaxhighlight lang="cpp" highlight="8-9">
 +
#include <map>
 +
#include <string>
 +
#include <cstdio>
 +
 +
int main() {
 +
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
    myMap["190010112345"] = person;
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
 
=== Eliminarea unei chei din map ===
 
=== Eliminarea unei chei din map ===
  
−
Pentru operația de eliminare se definește următoarea funcție:
+
Pentru operația de eliminare se definește următoarea metodă:
  
−
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
−
  * Functia elimina cheia data din map daca acesta exista. Daca
+
  * Metoda elimina cheia data din map daca acesta exista. Daca
 
  *  nu exista, functia nu are nici un efect.
 
  *  nu exista, functia nu are nici un efect.
−
  * @param map map-ul din care trebuie eliminat elementul.
+
  * @param key cheia ce trebuie eliminata.
−
  * @param key cheia (CNP-ul) ce trebuie eliminata.
+
  */
 +
void erase(K key);
 +
 
 +
/**
 +
* Metoda sterge toate elementele din map.
 
  */
 
  */
−
void hashMapRemove(struct HashMap * map, char * key);
+
void clear();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Eliminarea se realizează în felul următor:
+
Exemplu:
−
# Se aplică funcția hash pe variabila <code>key</code>.
+
<syntaxhighlight lang="cpp" highlight="10,13,16">
−
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
#include <map>
−
# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
+
#include <string>
−
# Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția <code>linkedListDelete</code> pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.
+
#include <cstdio>
 +
 +
int main() {
 +
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
    myMap["190010112345"] = person;
 +
    myMap.erase("098764321987");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.erase("191010112345");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.clear();
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
  
−
* 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).
+
    return 0;
−
* Complexitate în '''spațiu''': O(1)
+
}
 +
</syntaxhighlight>
  
 
=== Verificarea dacă o cheie există în map ===
 
=== Verificarea dacă o cheie există în map ===
Linia 202: Linia 447:
 
Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:
 
Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:
  
−
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
−
  * Functia intoarce 1 daca cheia specificata exista in map.
+
  * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
−
* @param map map-ul in care se cauta cheia.
+
  * @param key cheia cautata.
−
  * @param key cheia (CNP-ul) cautata.
 
 
  * @return 1 daca cheia exista in map, 0 daca nu.
 
  * @return 1 daca cheia exista in map, 0 daca nu.
 
  */
 
  */
−
char hashMapHasKey(struct HashMap * map, char * key);
+
uint64_t count(K key);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Verificarea unei chei dacă este sau nu în map se realizează în felul următor:
+
Exemplu:
−
# Se aplică funcția hash pe variabila <code>key</code>.
+
<syntaxhighlight lang="cpp" highlight="14,15">
−
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+
#include <map>
−
# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>key</code> există în listă.
+
#include <string>
−
# Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.
+
#include <cstdio>
−
 
+
−
* 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).
+
int main() {
−
* Complexitate în '''spațiu''': O(1)
+
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    myMap.insert({"191010112345", person});
 +
    myMap["190010112345"] = person;
 +
    myMap.erase("098764321987");
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.erase("191010112345");
 +
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
 +
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
    myMap.clear();
 +
    printf("Map-ul contine %lu elemente.\n", myMap.size());
 +
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 +
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
 
=== Căutarea unei valori după cheie ===
 
=== Căutarea unei valori după cheie ===
  
−
Pentru a căuta o valoare după cheie, se definește urmtoarea funcție:
+
Pentru a căuta o valoare după cheie, se definesc următoarele metode:
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 
/**
 
/**
−
  * Functia intoarce valoarea asociată cheii key.
+
  * Metoda intoarce a referinta la valoarea asociată cheii key.
−
* @param map map-ul in care se cauta cheia.
+
  * @param key cheia cautata.
−
  * @param key cheia (CNP-ul) cautata.
+
  * @return valoarea asociată cheii, dacă aceasta există,
−
  * @return valoarea asociată cheii.
+
*  sau se generează o eroare daca cheia nu exista in map.
 
  */
 
  */
−
struct Person hashMapGet(struct HashMap * map, char * key);
+
V& at(K key);
−
</syntaxhighlight>
 
−
 
 
−
Căutarea unei valori după cheie se realizează în felul următor:
 
−
# Se aplică funcția hash pe variabila <code>key</code>.
 
−
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
 
−
# Se iterează peste nodurile din listă și se caută cheia folosind funcția <code>equals</code>.
 
−
# Dacă cheia a fost găsită, se întoarce valoarea asociată; dacă s-a ajuns la sfârșitul listei fără a se găsi cheia, se întoarce o structură de tip <code>Person</code>, indiferent cu ce valori (comportament nedefinit).
 
−
 
 
−
* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
 
−
* Complexitate în '''spațiu''': O(1)
 
  
−
=== Ștergerea unui <code>HashMap</code>===
 
−
 
−
Pentru dezalocarea unui <code>HashMap</code>, se definește următoarea funcție:
 
−
<syntaxhighlight lang="C">
 
 
/**
 
/**
−
  * Functia sterge hash map-ul specificat.
+
  * Operatorul intoarce o referinta la valoarea asociată cheii key.
−
  * @param map hash map-ul ce trebuie sters.
+
  * @param key cheia cautata.
 +
* @return valoarea asociată cheii, dacă aceasta există,
 +
*  sau o valoare neutra daca nu există (care se si adauga in map).
 
  */
 
  */
−
void deleteHashMap(struct HashMap * map);
+
 
 +
V& operator[](K key);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Pentru ștergerea unui <code>HashMap</code> se urmează următorii pași:
+
Exemplu:
−
# Se iterează peste tot <code>array</code>-ul, ștergându-se toate nodurile din toate listele.
+
<syntaxhighlight lang="cpp" highlight="10,11">
−
# Se șterge memoria alocată pentru structura de tip <code>HashMap</code>.
+
#include <map>
−
 
+
#include <string>
−
* Complexitate în '''timp''': O(MAX_HASH)
+
#include <cstdio>
−
* Complexitate în '''spațiu''': O(1)
+
 +
int main() {
 +
    std::map<std::string, Person> myMap;
 +
    Person person;
 +
    person.firstName = "Ghita";
 +
    myMap.insert({"191010112345", person});
 +
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
 +
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
 +
    return 0;
 +
}
 +
</syntaxhighlight>

Versiunea curentă din 14 mai 2017 19:58

În acest laborator se vor implementa structuri de date asociative (map) cu arbori binari și funcții hash.

Structura de date asociativă - Map

Structura de date asociativă (map) este o structură de date abstractă care stochează perechi de elemente cheie-valoare, 
într-o ordine arbitrară stabilită de structură, astfel încât nu pot exista două perechi cu aceeași cheie în map.

În esență, un map este o mulțime (set) de chei care sunt întotdeauna stocate împreună cu o valoare.

Map.png

Map-ul 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 map sunt de același fel.
  4. Tipul de date al cheii și tipul de date al valorii pot fi diferite.
  5. Map-ul poate conține doar chei unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două chei sunt egale din punctul de vedere al map-ului, ele nu pot fi ambele prezente în perechi cheie-valoare în map.

Map-ul suportă următoarele operații de bază:

  1. Interogarea numărului de elemente din map.
  2. Verificarea dacă map-ul este gol.
  3. Adăugarea perechi cheie-valoare (insert) - dacă cheia există deja în map, aceasta nu se înlocuiește.
  4. Verificarea dacă o cheie există în map (count).
  5. Căutarea unei valori după o cheie dată (at);
  6. Eliminarea unei chei din map (erase).

Implementarea de structuri asociative cu funcții hash

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

Tipul de date și funcțiile de bază

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

struct Person {
    std::string firstName;
    std::string lastName;
    std::string idNumber; // seria si numarul de buletin
    std::string address;
    std::string birthday;
    std::string cnp;
};

Funcțiile de hash și de egalitate pentru clasa std::string sunt deja implementate în STL. Dacă totuși aveți nevoie de a folosi niste funcții proprii, acestea se scriu în același fel ca cele pentru mulțimi împlementate cu funcții hash (vezi SDA Lucrarea 5).

Clasa std::unordered_map

Pentru stocarea datelor necesare map-ului, În STL se definește clasa std::unordered_map în header-ul unordered_map. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare: 

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap; // un map de la string la Person
    return 0;
}

Crearea unui std::unordered_map

Pentru crearea unui std::unordered_map, se definește următorul constructor: 

/**
 * Constructorul creeaza un map nou și inițializează structurile de date interne.
 */
unordered_map();

Exemplu: 

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    return 0;
}

Interogarea numărului de elemente din map

Pentru interogarea numărului de elemente din map se definesc: 

/**
 * Metoda intoarce numarul de elemente din map.
 * @return numarul de elemente din map.
 */
uint64_t size();

/**
 * Metoda intoarce true dacă map-ul nu conține nici un element.
 * @return true dacă map-ul este gol, false în rest.
 */
bool empty();

Exemplu: 

#include <unordered_map>
#include <string>
#include <cstdio>

int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Adăugarea unei perechi cheie-valoare în map

Pentru operația de adăugare se definesc următoarele metode: 

/**
 * Metoda adauga perechea data in map daca cheia nu exista. 
 * @param keyValuePair o pereche cheie-valoare
 * @return o pereche iterator-bool, unde iteratorul identifică perechea 
 *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 *   perechea a fost introdusa sau nu (pentru ca exista deja).
 */
pair<iterator, bool> insert(pair<K, V> keyValuePair);

/**
 * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la 
 *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 *  neutră.
 * @param key cheia ce se dorește adăugată (sau interogată).
 * @return o referință la valoarea asociată cheii.
 */
V & operator[](K key);

Exemplu: 

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Eliminarea unei chei din map

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

/**
 * Metoda elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param key cheia ce trebuie eliminata.
 */
void erase(K key);

/**
 * Metoda sterge toate elementele din map.
 */
void clear();

Exemplu: 

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");

    return 0;
}

Verificarea dacă o cheie există în map

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

/**
 * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
 * @param key cheia cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
uint64_t count(K key);

Exemplu: 

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 
    return 0;
}

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definește următoarele metode: 

/**
 * Metoda intoarce a referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau se generează o eroare daca cheia nu exista in map.
 */
V& at(K key);

/**
 * Operatorul intoarce o referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau o valoare neutra daca nu există (care se si adauga in map).
 */

V& operator[](K key);

Exemplu: 

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    person.firstName = "Ghita";
    myMap.insert({"191010112345", person});
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
    return 0;
}


Implementarea de structuri asociative cu arbori binari de căutare

Definirea arborilor binari de căutare și a proprietăților lor s-au făcut în laboratorul 5 (SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)).

Clasa std::map

Pentru stocarea datelor necesare map-ului, În STL se definește clasa std::map în header-ul map. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare: 

#include <map>
#include <string>

int main() {
    std::map<std::string, Person> myMap; // un map de la string la Person
    return 0;
}

Crearea unui std::map

Pentru crearea unui std::map, se definește următorul constructor: 

/**
 * Constructorul creeaza un map nou și inițializează structurile de date interne.
 */
map();

Exemplu: 

#include <map>
#include <string>

int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    return 0;
}

Interogarea numărului de elemente din map

Pentru interogarea numărului de elemente din map se definesc: 

/**
 * Metoda intoarce numarul de elemente din map.
 * @return numarul de elemente din map.
 */
uint64_t size();

/**
 * Metoda intoarce true dacă map-ul nu conține nici un element.
 * @return true dacă map-ul este gol, false în rest.
 */
bool empty();

Exemplu: 

#include <map>
#include <string>
#include <cstdio>

int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Adăugarea unei perechi cheie-valoare în map

Pentru operația de adăugare se definesc următoarele metode: 

/**
 * Metoda adauga perechea data in map daca cheia nu exista. 
 * @param keyValuePair o pereche cheie-valoare
 * @return o pereche iterator-bool, unde iteratorul identifică perechea 
 *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 *   perechea a fost introdusa sau nu (pentru ca exista deja).
 */
pair<iterator, bool> insert(pair<K, V> keyValuePair);

/**
 * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la 
 *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 *  neutră.
 * @param key cheia ce se dorește adăugată (sau interogată).
 * @return o referință la valoarea asociată cheii.
 */
V & operator[](K key);

Exemplu: 

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Eliminarea unei chei din map

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

/**
 * Metoda elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param key cheia ce trebuie eliminata.
 */
void erase(K key);

/**
 * Metoda sterge toate elementele din map.
 */
void clear();

Exemplu: 

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");

    return 0;
}

Verificarea dacă o cheie există în map

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

/**
 * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
 * @param key cheia cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
uint64_t count(K key);

Exemplu: 

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 
    return 0;
}

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definesc următoarele metode: 

/**
 * Metoda intoarce a referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau se generează o eroare daca cheia nu exista in map.
 */
V& at(K key);

/**
 * Operatorul intoarce o referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau o valoare neutra daca nu există (care se si adauga in map).
 */

V& operator[](K key);

Exemplu: 

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    person.firstName = "Ghita";
    myMap.insert({"191010112345", person});
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
    return 0;
}
Adus de la „http://wiki.dcae.pub.ro/index.php?title=SDA_Lucrarea_6&oldid=5456”