AiSD (index)

AiSD (1) - ADT SET

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

https://en.wikipedia.org/wiki/Set_(abstract_data_type)

WPROWADZENIE

Zbiór to ADT, który pozwala przechowywać dane bez powtórzeń i bez ustalonego uporządkowania. Jest to komputerowa realizacja matematycznego pojęcia zbioru skończonego. Istotne jest, aby operacja sprawdzania należenia elementu do zbioru była wykonywana w stałym czasie O(1).

Czasem wymaga się, aby elementy zbioru były posortowane. Wtedy sprawdzanie należenia elementu do zbioru zajmuje czas O(log n).

Typowe operacje dla ADT SET są następujące:

• konstruktor tworzący pusty zbiór,
• testowanie, czy zbiór nie jest pusty [empty()],
• odczyt liczby elementów w zbiorze [size()],
• dodanie elementu do zbioru [insert(item)],
• usuwanie elementu ze zbioru [erase(item), remove(item)],
• test należenia do zbioru [find(item), contains(item)],
• czyszczenie zbioru [clear()].

Działania na zbiorach:

• wyznaczanie sumy zbiorów S ∪ T [union(S,T)],
• wyznaczanie części wspólnej zbiorów S ∩ T [intersection(S,T)],
• wyznaczanie różnicy zbiorów S-T [difference(S,T)],
• sprawdzenie, czy zbiór S jest podzbiorem zbioru T, S ⊂ T [subset(S,T)],

// https://en.cppreference.com/w/cpp/container/set

#include <set>

// std::set is an associative container that contains a sorted set of unique
// objects of type Key. Sorting is done using the key comparison function Compare.
// Search, removal, and insertion operations have logarithmic complexity.
// Sets are usually implemented as red-black trees.

// Przykład użycia zbioru posortowanego.

// Elementy zbioru będą wewnętrznie posortowane.
// std::set<int> intset = {4,0,3,1,2};   // initializer list
std::set<int> intset;
for (int i = 0; i < 15; i++)
    intset.insert(i % 5);   // elementy powtarzające się są ignorowane
    // operacja insert() zwraca status typu
    // std::pair< std::set<int>::iterator, bool >
assert( intset.size() == 5 );
assert( intset.count(2) == 1 );   // dozwolone 0 lub 1 dla set
assert( intset.count(20) == 0 );   // brak 20 w zbiorze

// Wyszukiwanie elementu w zbiorze, dostajemy iterator.
auto it = intset.find(3);
assert( it != intset.end() );   // liczba 3 należy do zbioru

assert( intset.contains(3) );   // C++20

// intset.erase(3);   // usunięcie liczby 3
intset.erase(it);   // użycie iteratora do usunięcia liczby 3

it = intset.find(7);
assert( it == intset.end() );   // liczby 7 nie ma w zbiorze
intset.clear();   // opróżnienie zbioru
assert( intset.empty() );

// https://en.cppreference.com/w/cpp/container/unordered_set

#include <unordered_set>

// std::unordered_set is an associative container that contains a set of unique
// objects of type Key. Search, insertion, and removal have average constant-time complexity.
// The elements are not sorted in any particular order (hashing is used),
// but organized into buckets.
// Container elements may not be modified.

// Przykład użycia zbioru nieuporządkowanego.
// Działa to samo, co dla std::set.

ZADANIE 1.1 (TABLICA MIESZAJĄCA)

Przygotować implementację realizującą ADT SET na bazie tablicy mieszającej z wykorzystaniem metody łańcuchowej.

// Szablon dla prostego zbioru wykorzystującego metodę łańcuchową.

template<typename T>
class MySet {
    int BUCKET;    // liczba bukietów
    std::list<T> *table;
public:
    MySet(int b);  // konstruktor
    ~MySet() { clear(); delete [] table; }
    bool empty() const; // czy zbiór jest pusty?
    int size() const; // liczba elementów zbioru
    void insert(T key); // wstawienie klucza do zbioru
    T* find(const T& key); // czy klucz jest w zbiorze? zwraca &key lub nullptr
    void remove(const T& key);
    int hash(const T& key) { return (int(key) % BUCKET); } // działa dla int, float
    void display() const;
    void clear(); // czyścimy zbiór
};

template<typename T>
MySet<T>::MySet(int b) {
    BUCKET = b;
    table = new std::list<T>[BUCKET]; // tablica z pustymi listami
    assert( table != nullptr );
}

template<typename T>
void MySet<T>::display() const {
    for (int i = 0; i < BUCKET; i++)
        for (const T& k : table[i])
            std::cout << k << " ";
    std::cout << std::endl;
}

ZADANIE 1.2 (DRZEWO BST)

Przygotować implementację realizującą ADT SET na bazie drzewa BST, najlepiej samobalansującego (AVL, RBT). Inna możliwość to użycie listy z przeskokami. Elementy powtarzające się mają być ignorowane. Wyświetlane elementy zbioru będą posortowane (kolejność inorder).

ZADANIE 1.3 (TABLICA BOOL)

Przygotować implementację zbioru do przechowywania liczb całkowitych z zakresu od 0 do n-1. Wykorzystać tablicę int lub bool, w której 0 lub 1 na pozycji k oznacza odpowiednio brak lub istnienie liczby k w zbiorze. Zadbać o to, aby odczyt liczby elementów w zbiorze odbywał się w stałym czasie O(1). Zastosowanie: zbiór wierzchołków grafu w reprezentacji macierzy sąsiedztwa, gdzie wierzchołki grafu są liczbami od 0 do n-1.

ZADANIE 1.4 (DRZEWO TRIE)

Przygotować implementację realizującą ADT SET na bazie drzewa trie do przechowywania stringów.

AiSD (index)