AiSD (index)

AiSD (1) - ADT SET

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

Ogólne zalecenia do przesyłanych programów.
(1) Katalog z programem powinien zawierać Makefile i pliki źródłowe.
(2) Program powinien kompilować się poleceniem make.
(3) Nie używać deklaracji using namespace std;.
(4) Zalecane są testy automatyczne z assert().

WPROWADZENIE

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

Zbiór to ADT, który pozwala przechowywać dane bez powtórzeń i (zwykle) 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), podobnie jak wstawianie i usuwanie elementów.

Czasem wymaga się, aby elementy zbioru były posortowane. Wtedy sprawdzanie należenia elementu do zbioru zajmuje czas O(log n), podobnie jak wstawianie i usuwanie elementów.

W języku Python dostępne są zbiory zmienne (set) i niezmienne (frozenset). Zbiorów niezmiennych nie można modyfikować po utworzeniu, ale są one hashowalne.

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

Działania na zbiorach: 

// 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 >
}
for (auto& item : intset) {   // działa pętla zakresowa
    std::cout << item << std::endl;
}   // 0 1 2 3 4 elementy uporządkowane rosnąco
for (auto it = intset.begin(); it != intset.end(); ++it) { // iteratory
    std::cout << *it << std::endl;
}
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.
Zastanowić się nad implementacją iteratora po elementach zbioru. 

// 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 { return size() == 0; } // czy zbiór jest pusty?
    int size() const; // liczba elementów zbioru
    void insert(const T& key); // wstawienie klucza do zbioru
    T* find(const T& key); // czy klucz jest w zbiorze? zwraca &key lub nullptr
    bool contains(const T& key); // czy klucz jest w zbiorze?
    void remove(const T& key);
    int hash(const T& key) { return (int(key) % BUCKET); } // działa dla int, float
    void clear(); // czyścimy zbiór
    void display() const; // wypisuje { item1, item2, ..., itemk }
};

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).
Zastanowić się nad implementacją iteratora po elementach zbioru.

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.
Zastanowić się nad implementacją iteratora po elementach zbioru.

ZADANIE 1.4 (DRZEWO TRIE)

Przygotować implementację realizującą ADT SET na bazie drzewa trie do przechowywania stringów.
Zastanowić się nad implementacją iteratora po elementach zbioru.

AiSD (index)