SDA Lucrarea 5

De la WikiLabs
Versiunea din 20 aprilie 2016 18:45, autor: Rhobincu (discuție | contribuții) (Pagină nouă: Î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 el...)
(dif) ← Versiunea anterioară | Versiunea curentă (dif) | Versiunea următoare → (dif)
Jump to navigationJump to search

Î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ă.

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 (put).
  4. Verificarea dacă un element există în mulțime (contains).
  5. 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