Напиши программу на языке C+: Реализация класса «set» с использованием хэш-таблиц.…
- User
Напиши программу на языке C+: Реализация класса «set» с использованием хэш-таблиц. Запрещено использовать стандартные классы языка C++, включающие в себя название “set”. В реализации должны присутствовать такие методы как: find(), count()
- 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() реализованы в соответствии с описанием задачи.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.