SDA Lucrarea 5
În acest laborator se vor implementa mulțimi cu funcții hash și arbori binari.
Mulțimea
Mulțimea este o structură de date abstractă care stochează o colecție de elemente unice în care ordinea nu contează.
Mulțimea are următoarele proprietăți:
- Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
- Numărul de elemente ce poate fi stocat de structură este nelimitat.
- Elementele stocate în mulțime sunt de același fel.
- Mulțimea poate conține doar elemente unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două elemente sunt egale din punctul de vedere al mulțimii, ele nu pot fi ambele conținute de mulțime.
Mulțimea suportă următoarele operații de bază:
- Interogarea numărului de elemente din mulțime.
- Verificarea dacă mulțimea este goală.
- Adăugarea unui element în mulțime (put).
- Verificarea dacă un element există în mulțime (contains).
- Eliminarea unui element din mulțime (remove).
Pentru a verifica egalitatea a două elemente vom defini o funcție equals
care va întoarce 1 dacă cele două argumente sunt egale și 0 dacă nu. Această funcție trebuie să existe pentru orice implementare de mulțime, atunci când elementele nu sunt valori ce pot fi comparate cu operatorul implicit ==:
/**
* Functia verifica daca valorile value1 si value2 sunt egale.
* @param value1 prima valoare de comparat.
* @param value2 a doua valoare de comparat.
* @return 1 daca cele doua valori sunt egale si 0 in rest.
*/
char equals(T value1, T value2);
Implementarea de mulțimi cu funcții hash
O funcție hash este o funcție care ia ca argument un șir de bytes de orice dimensiune și întoarce un șir de bytes de dimensiune fixă ce poartă numele de valoare de hash, cod hash sau pur și simplu hash.
Definiția unei funcții hash este strâns legată de definiția funcției equals
astfel încât dacă două elemente e1 și e2 sunt considerate egale (equals(e1, e1) == 1
), atunci obligatoriu hash(e1) == hash(e2)
.
Tipul de date și funcțiile de bază
În continuare vom prezenta un exemplu de mulțime pentru elemente de tip "persoană" implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:
struct Person {
char firstName[30];
char lastName[30];
char idNumber[9]; // seria si numarul de buletin
char address[255];
char birthday[11];
char cnp[14];
};
Pentru a implementa o funcție hash pentru variabilele de tip struct Person
, avem întâi nevoie să definim operația de egalitate. O persoană își poate schimba numele, buletinul și adresa, și pot exista mai multe persoane cu aceeași dată de naștere, dar ceea ce identifică clar o persoană este codul numeric personal (CNP). Deci vom defini funcția equals
să întoarcă 1 dacă cnp-urile celor două argumente de tip struct Person
sunt identice:
/**
* Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
* @param person1 prima persoana de comparat.
* @param person2 a doua persoana de comparat.
* @return 1 daca CNP-urile celor doua persoane sunt identice.
*/
char equals(struct Person person1, struct Person person2);
Mai departe definim funcția hash pentru o Persoană.
Pentru a putea implementa o mulțime cu funcții hash trebuie ca hash-ul maxim să fie o valoare rezonabilă pentru a putea aloca memorie cu dimensiunea valorii respective.
Din motivul de mai sus, și pentru a micșora posibilitatea unei coliziuni de hash ce va micșora performanța structurii, ieșirea funcției hash va fi un număr între 0 și 999999 obținut din ultimele 6 cifre ale CNP-ului convertite din text în număr (pentru conversie puteți folosi funcția atoi):
/**
* Functie hash pentru structurile de tip Person.
* @param person peroana pentru care se doreste codul hash.
* @return codul hash al persoanei person
*/
unsigned hash(struct Person person);
În continuare vom utiliza pentru implementarea unui Hash Set o structură de date de tip secvență împlementată cu liste (ArrayList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:
Structura HashSet
Pentru stocarea datelor necesare mulțimii, definim următoarea structură:
#define MAX_HASH 1000000
struct HashSet {
struct ArrayList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
unsigned size; // numarul de elemente din multime
};
Crearea unui HashSet
Pentru crearea unui HashSet
, se definește următoarea funcție:
/**
* Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
* @return un pointer la o structura de tip HashSet.
*/
struct HashSet * createHashSet();
Pentru crearea unui HashSet
se urmează următorii pași:
- Se alocă memorie pentru un element de tip
struct HashSet
folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0). - Se inițializează
size
cu 0. - Se întoarce adresa elementului de tip
struct HashSet
.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(MAX_HASH)
Interogarea numărului de elemente din mulțime
Pentru interogarea numărului de elemente din mulțime definim:
/**
* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/
unsigned hashSetSize(struct HashSet * set);
Funcția va întoarce valoarea din câmpul size
din structură.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(1)
Pentru a afla dacă mulțimea este goală definim:
/**
* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/
char hashSetIsEmpty(struct HashSet * set);
Funcția va întoarce 1 dacă valoarea din câmpul size
este 0.
- Complexitate în timp: O(1)
- Complexitate în spațiu: O(1)
Adăugarea unui element în mulțime
Pentru operația de adăugare se definește următoarea funcție:
/**
* Functia adauga elementul dat in multime daca acesta nu exista. Daca
* exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param person elementul ce trebuie adaugta.
*/
void hashSetPut(struct HashSet * set, struct Person person);
Adăugarea se realizează în felul următor:
- Se aplică funcția hash pe variabila
person
. - Folosind valoarea obținută se accesează lista de pe poziția hash-ului din
array
. - Se folosește funcția
arrayListSearch
pentru a verifica dacăperson
există în listă (funcțiaarrayListSearch
trebuie re-implementată pentru a se folosi de funcțiaequals
pentru compararea elementelor). - Dacă valoarea întoarsă este -1 atunci
person
se adaugă în listă șisize
se incrementează cu 1.
- Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
- Complexitate în spațiu: O(1)
array
conține variabile de tip struct ArrayList
și nu pointeri, pentru a folosi funcțiile definite în arrayList.h e necesară obținerea adresei variabilei de tip struct ArrayList
folosind operatorul &.Eliminarea unui element din mulțime
Pentru operația de eliminare se definește următoarea funcție:
/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param person elementul ce trebuie eliminat.
*/
void hashSetRemove(struct HashSet * set, struct Person person);
Eliminarea se realizează în felul următor:
- Se aplică funcția hash pe variabila
person
. - Folosind valoarea obținută se accesează lista de pe poziția hash-ului din
array
. - Se folosește funcția
arrayListSearch
pentru a verifica dacăperson
există în listă. - Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția
arrayListRemove
pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.
- Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
- Complexitate în spațiu: O(1)
Verificarea dacă un element există în mulțime
Pentru a verifica dacă un element există în mulțime, se definește următoarea funcție:
/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param person elementul cautat.
*/
void hashSetContains(struct HashSet * set, struct Person person);
Eliminarea se realizează în felul următor:
- Se aplică funcția hash pe variabila
person
. - Folosind valoarea obținută se accesează lista de pe poziția hash-ului din
array
. - Se folosește funcția
arrayListSearch
pentru a verifica dacăperson
există în listă. - Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.
- Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
- Complexitate în spațiu: O(1)
Ștergerea unui HashSet
Pentru dezalocarea unui HashSet
, se definește următoarea funcție:
/**
* Functia sterge hash set-ul specificat.
* @param set hash set-ul ce trebuie sters.
*/
void deleteHashSet(struct HashSet * set);
Pentru ștergerea unui HashSet
se urmează următorii pași:
- Se iterează peste tot
array
-ul, ștergându-se toate nodurile din toate listele. - Se șterge memoria alocată pentru structura de tip
HashSet
.
- Complexitate în timp: O(MAX_HASH)
- Complexitate în spațiu: O(1)
Exerciții
Săptămâna 1
- Dându-se fișierele Fișier:LinkedList.h, Fișier:LinkedList.c și header-ele
hashSet.h
șiperson.h
de mai jos, implementați toate funcțiile definite într-un fișier sursă numithashSet.c
:-
person.h
:#ifndef PERSON_H #define PERSON_H struct Person { char firstName[30]; char lastName[30]; char idNumber[9]; // seria si numarul de buletin char address[255]; char birthday[11]; char cnp[14]; }; /** * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale. * @param person1 prima persoana de comparat. * @param person2 a doua persoana de comparat. * @return 1 daca CNP-urile celor doua persoane sunt identice. */ char equals(struct Person person1, struct Person person2); /** * Functie hash pentru structurile de tip Person. * @param person peroana pentru care se doreste codul hash. * @return codul hash al persoanei person */ unsigned hash(struct Person person); #define T struct Person #endif
-
hashset.h
:#ifndef HASHSET_H #define HASHSET_H #define MAX_HASH 1000000 struct HashSet { struct ArrayList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash unsigned size; // numarul de elemente din multime }; /** * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata. * @return un pointer la o structura de tip HashSet. */ struct HashSet * createHashSet(); /** * Functia intoarce numarul de elemente din multime. * @param set multimea a carei dimensiuni este ceruta. * @return numarul de elemente din multime. */ unsigned hashSetSize(struct HashSet * set); /** * Functia intoarce 1 dacă mulțimea nu conține nici un element. * @param set multimea de interes. * @return 1 dacă mulțimea este goală, 0 în rest. */ char hashSetIsEmpty(struct HashSet * set); /** * Functia adauga elementul dat in multime daca acesta nu exista. Daca * exista deja, functia nu are nici un efect. * @param set multimea in care trebuie adaugat elementul. * @param person elementul ce trebuie adaugta. */ void hashSetPut(struct HashSet * set, struct Person person); /** * Functia elimina elementul dat din multime daca acesta exista. Daca * nu exista, functia nu are nici un efect. * @param set multimea din care trebuie eliminat elementul. * @param person elementul ce trebuie eliminat. */ void hashSetRemove(struct HashSet * set, struct Person person); /** * Functia intoarce 1 daca elementul specificat exista in multime. * @param set multimea in care se cauta elementul. * @param person elementul cautat. */ void hashSetContains(struct HashSet * set, struct Person person); /** * Functia sterge hash set-ul specificat. * @param set hash set-ul ce trebuie sters. */ void deleteHashSet(struct HashSet * set); #endif
-
- Scrieți o altă sursă
main.c
în care să definiți o funcțiestruct Person readFromKeyboard()
și o altă funcțiemain
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.