Главная страница
Навигация по странице:

  • Тестирование программы

  • Практическая 2 СиАОД. Практическая №2 СиАОД. Цель работы освоить приёмы хеширования и эффективного поиска элементов множества. Практическое задание Разработайте приложение, которое использует хештаблицу пары ключ хеш


    Скачать 70.27 Kb.
    НазваниеЦель работы освоить приёмы хеширования и эффективного поиска элементов множества. Практическое задание Разработайте приложение, которое использует хештаблицу пары ключ хеш
    АнкорПрактическая 2 СиАОД
    Дата19.05.2023
    Размер70.27 Kb.
    Формат файлаdocx
    Имя файлаПрактическая №2 СиАОД.docx
    ТипДокументы
    #1144597


    Цель работы: освоить приёмы хеширования и эффективного поиска элементов множества.

    Практическое задание

    Разработайте приложение, которое использует хеш-таблицу (пары «ключ – хеш») для организации прямого доступа к элементам динамического множества полезных данных.

    Множество реализуйте на массиве, структура элементов (перечень полей) которого приведена в индивидуальном варианте (п.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 Поиск и удаление записи

    Вывод: В ходе практической работы были освоены приёмы хеширования и эффективного поиска элементов множества.



    написать администратору сайта