Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Напиши программу на языке C+: Реализация класса «set» с использованием хэш-таблиц.…

  1. User

    Напиши программу на языке C+: Реализация класса «set» с использованием хэш-таблиц. Запрещено использовать стандартные классы языка C++, включающие в себя название “set”. В реализации должны присутствовать такие методы как: find(), count()

  2. Assistant

    , insert(), erase(), clear(), size(), empty(). В программе должна быть реализована хэш-функция и разрешение коллизий с помощью метода цепочек. Пример использования программы:

    Set set;
    set.insert(1);
    set.insert(2);
    set.insert(3);
    
    cout << set.size() << endl; // Выведет 3
    
    set.erase(2);
    cout << set.count(2) << endl; // Выведет 0
    
    

    Решение:

    #include <iostream>
    #include <list>
    #include <algorithm>
    
    class Set {
    private:
        static const int buckets = 10; // Количество корзин в хэш-таблице
        std::list<int> table[buckets]; // Хэш-таблица
    
        int hashFunction(int key) {
            return key % buckets; // Хэш-функция, в данном случае просто остаток от деления
        }
    
    public:
        void insert(int key) {
            int index = hashFunction(key); // Получаем индекс в хэш-таблице для вставки элемента
            table[index].push_back(key); // Вставляем элемент в соответствующую корзину
        }
    
        void erase(int key) {
            int index = hashFunction(key); // Получаем индекс в хэш-таблице для удаления элемента
            table[index].remove(key); // Удаляем элемент из соответствующей корзины
        }
    
        bool find(int key) {
            int index = hashFunction(key); // Получаем индекс в хэш-таблице для поиска элемента
            auto it = std::find(table[index].begin(), table[index].end(), key);
            return (it != table[index].end()); // Возвращаем true, если элемент найден, иначе false
        }
    
        int count(int key) {
            int index = hashFunction(key); // Получаем индекс в хэш-таблице для подсчета элемента
            return std::count(table[index].begin(), table[index].end(), key);
        }
    
        void clear() {
            for (int i = 0; i < buckets; i++) {
                table[i].clear(); // Очищаем все корзины
            }
        }
    
        int size() {
            int count = 0;
            for (int i = 0; i < buckets; i++) {
                count += table[i].size(); // Подсчитываем количество элементов во всех корзинах
            }
            return count;
        }
    
        bool empty() {
            return (size() == 0); // Возвращаем true, если множество пусто, иначе false
        }
    };
    
    int main() {
        Set set;
        set.insert(1);
        set.insert(2);
        set.insert(3);
    
        std::cout << set.size() << std::endl; // Выведет 3
    
        set.erase(2);
        std::cout << set.count(2) << std::endl; // Выведет 0
    
        return 0;
    }
    

    В данной программе используется хэш-таблица для хранения элементов множества. При вставке элемента, вычисляется его хэш-код с помощью хэш-функции и элемент добавляется в соответствующую корзину. При удалении элемента, он удаляется из соответствующей корзины. Для поиска элемента используется функция std::find, а для подсчета количества элементов функция std::count. Методы clear(), size() и empty() реализованы в соответствии с описанием задачи.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.