Файл: Цель работы освоить приёмы хеширования и эффективного поиска элементов множества. Практическое задание Разработайте приложение, которое использует хештаблицу пары ключ хеш.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 28
Скачиваний: 4
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Цель работы: освоить приёмы хеширования и эффективного поиска элементов множества.
Практическое задание
Разработайте приложение, которое использует хеш-таблицу (пары «ключ – хеш») для организации прямого доступа к элементам динамического множества полезных данных.
Множество реализуйте на массиве, структура элементов (перечень полей) которого приведена в индивидуальном варианте (п.3).
Приложение должно содержать класс с базовыми операциями: вставки, удаления, поиска по ключу, вывода. Включите в класс массив полезных данных и хеш-таблицу. Хеш-функцию
подберите самостоятельно, используя правила выбора функции.
Реализуйте расширение размера таблицы и рехеширование, когда это требуется, в соответствии с типом разрешения коллизий.
Предусмотрите автоматическое заполнение таблицы 5-7 записями.
Реализуйте текстовый командный интерфейс пользователя для возможности вызова методов в любой произвольной последовательности, сопроводите вывод достаточными для понимания происходящего сторонним пользователем подсказками.
Проведите полное тестирование программы (все базовые операции, изменение размера и рехеширование), тест-примеры определите самостоятельно. Результаты тестирования включите в отчет по выполненной работе.
| #include #include #include using namespace std; const int TABLE_SIZE = 10; // initial table size const int LOAD_FACTOR = 2; // load factor threshold const int EMPTY = -1; // empty slot marker class BankAccount { public: BankAccount() : accNum(0), name(""), address("") {} BankAccount(int num, string n, string addr) : accNum(num), name(n), address(addr) {} int getAccNum() const { return accNum; } string getName() const { return name; } string getAddress() const { return address; } void setAccNum(int num) { accNum = num; } void setName(string n) { name = n; } void setAddress(string addr) { address = addr; } private: int accNum; string name; string address; }; class BankAccountSet { public: BankAccountSet() : size(0), capacity(TABLE_SIZE) { data = new BankAccount[capacity]; table = new int[capacity]; for (int i = 0; i < capacity; i++) { table[i] = EMPTY; } } BankAccountSet() { delete[] data; delete[] table; } void insert(int num, string name, string address) { if (size >= capacity / LOAD_FACTOR) { resize(); } int index = hash(num); while (table[index] != EMPTY) { if (data[table[index]].getAccNum() == num) { return; // account already exists } index = (index + 1) % capacity; } data[size] = BankAccount(num, name, address); table[index] = size++; } bool remove(int num) { int index = findIndex(num); if (index == -1) { return false; // account not found } table[index] = EMPTY; int i = (index + 1) % capacity; while (table[i] != EMPTY) { int j = hash(data[table[i]].getAccNum()); if ((i > index && (j <= index || j > i)) || (i < index && (j <= index && j > i))) { table[index] = table[i]; table[i] = EMPTY; index = i; } i = (i + 1) % capacity; } size--; return true; } BankAccount* find(int num) { int index = findIndex(num); if (index == -1) { return nullptr; // account not found } return &data[table[index]]; } void print() const { for (int i = 0; i < capacity; i++) { if (table[i] != EMPTY) { cout << data[table[i]].getAccNum() << ": " << data[table[i]].getName() << ", " << data[table[i]].getAddress() << endl; } } } private: BankAccount* data; // array of BankAccount objects int* table; // hash table of indices into data array int size; // number of elements in the set int capacity; // maximum number of elements in the set int hash(int num) const { return num % capacity; } int findIndex(int num) const { int index = hash(num); while (table[index] != EMPTY) { if (data[table[index]].getAccNum() == num) { return index; } index = (index + 1) % capacity; } return -1; // account not found } void resize() { int oldCapacity = capacity; capacity *= 2; BankAccount* oldData = data; int* oldTable = table; data = new BankAccount[capacity]; table = new int[capacity]; for (int i = 0; i < capacity; i++) { table[i] = EMPTY; } size = 0; for (int i = 0; i < oldCapacity; i++) { if (oldTable[i] != EMPTY) { insert(oldData[oldTable[i]].getAccNum(), oldData[oldTable[i]].getName(), oldData[oldTable[i]].getAddress()); } } delete[] oldData; delete[] oldTable; } }; int main() { BankAccountSet set; set.insert(1234567, "Иванов Иван", "Москва, Коптевская, 63"); set.insert(2345678, "Артёмов Артём", "Москва, Иваново, 93"); set.insert(3456789, "Екатерина Николаевна", "Москва, Новопетровская, 92"); set.insert(4567890, "Николаев Николай", "Санкт-Петербург, Новосенная, 6"); set.insert(5678901, "Даниил Даниилович", "Москва, Кремль"); int choice; do { cout << "1. Добавить новую запись\n2. Удалить запись\n3. Найти запись\n4. Вывести все записи\n0. Выход\nВыберите действие: "; cin >> choice; switch (choice) { case 1: { int num; string name, address; cout << "Введите 7-значный номер счёта в банке: "; cin >> num; cout << "Введите имя: "; cin.ignore(); getline(cin, name); cout << "Введите адрес: "; getline(cin, address); set.insert(num, name, address); cout << "Запись добавлена успешно." << endl; break; } case 2: { int num; cout << "Введите 7-значный номер счёта в банке: "; cin >> num; if (set.remove(num)) { cout << "Запись удалена успешно." << endl; } else { cout << "Клиент не найден." << endl; } break; } case 3: { int num; cout << "Введите 7-значный номер счёта в банке: "; cin >> num; BankAccount* acc = set.find(num); if (acc != nullptr) { cout << "Имя: " << acc->getName() << endl; cout << "Адрес: " << acc->getAddress() << endl; } else { cout << "Клиент не найден." << endl; } break; } case 4: { set.print(); break; } case 0: { cout << "Выход..." << endl; break; } default: { cout << "Неверный выбор. Попробуйте ещё раз." << endl; break; } } } while (choice != 0); return 0; } |
Тестирование программы:
Рис.1 Вывод всех записей и добавление новой
Рис.2 Поиск и удаление записи
Вывод: В ходе практической работы были освоены приёмы хеширования и эффективного поиска элементов множества.