Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів пошуку даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Розробка та дослідження ефективності
методів пошуку даних ”
Варіанти – 15, 2, 1
Львів – 2016
Мета роботи
• Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Загальне завдання:
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):
прізвище, ім'я, побатькові,
день, місяць,рік народження,
назва компанii мобільного зв'язку,
підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),
назва області, міста і вулиці в адресі прописки,
номер будинку і квартири в адресі прописки,
абревіатура інститута, кафедри, групи,
день, місяць,рік виконання лабораторної роботи.
Наприклад: Вміст файлу data.txt :
Petrenko,Bogdan,Sergyjovuch,25,3,1989,Kyivstar,0,6,7,5,7,6,4,9,2,1,Lvivska,Lviv,Bandery,12,1,IKTA,EOM,KI-21,12,4,2010
Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої.
Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць.
В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці.
Під час пошуку слів в хеш-таблицях програма повинна виводити на екран послідовність слів з якими виконуються порівняння і кількість виконаних операцій порівняння.
Особисте завдання:
Завдання 1:
а) Побудувати хеш-таблицю розмірністю m=37, метод організації якої:
h(key) = [(АSCII-код останього символа ключа) *(кількість символів в ключі)] % m;
б) Розв'язання колізій при хешуванні здійснити:
методом відкритої адресації з функцією повторного хешування
hі(key) = ( h(key) + i ) % m;
Завдання 2:
Побудувати хеш-таблицю. Розмірність таблиці (m), вигляд хеш-функції h(key) та вигляд функції повторного хешування hi(key) вибрати самостійно, керуючись умовами покращення ефективності методу побудови хеш-таблиці.
Розв'язання колізій при хешуванні здійснити методом роздільних ланцюжків.
Текст програми:
#include <iostream>
#include <fstream>
#include <string>
#define M 37
#define N 7
using namespace std;
//функції для першої таблиці
int Func_Key(string str) //обчислення хеш-функції
{
//h(key) = [(АSCII-код останього символа ключа) *(кількість символів в ключі)] % m;
return (str[size(str) - 1] * size(str)) % M;
}
int m = 1;
int Func_doubleKey(string** table, string str, int vubir = 0) //обчислення повторних хеш-функцій для розвязання колізій
{
int Key = Func_Key(str);
int doubleKey;
int i = 1;
do
{
doubleKey = (Key + i++) % M;
if ((table[doubleKey] == NULL))
return doubleKey;
if ((*table[doubleKey] != str) && vubir == 3)
{
cout << *table[doubleKey] << ", ";
m++;
}
} while ((*table[doubleKey] != str)); //цикл виконуватиметься до тих пір поки не буде знайдено вільного місця
return doubleKey; //або поки не зустрінеться такий самий елемент
}
bool add(string** table, string str) // функція додавання елемента в хеш-таблицю
{
int Key = Func_Key(str);
if (table[Key] == NULL) //якщо елемент під заданим ключем вільний то записуєм сюди значення
table[Key] = new string(str); // запис в хеш-таблицю
else
{
if (*table[Key] == str)
return false;
if (table[Func_doubleKey(table, str)] == NULL)
table[Func_doubleKey(table, str)] = new string(str);
else
return false;
}
}
bool remove(string** table, string str) // видалення елемента з хеш-таблиці
{
int Key = Func_Key(str);
if (table[Key] == NULL)
return false;
if (*table[Key] == str)
*table[Key] = "del";
else
{
if (table[Func_doubleKey(table, str)] == NULL)
return false;
if (*table[Func_doubleKey(table, str)] == str)
*table[Func_doubleKey(table, str)] = "del";
}
return true;
}
int search(string** table, string str, int vubir = 0) //пошук елемента в хеш-таблиці
{
int Key = Func_Key(str);
if (table[Key] == NULL)
return false;
if (*table[Key] == str)
return Key;
else
{
if (table[Func_doubleKey(table, str)] == NULL)
return false;
else
return Func_doubleKey(table, str, vubir);
}
}
////////////////////////////////////////////////////////////////////////////////////////////
struct Node {
string data;
Node* next;
};
//функції для другої таблиці
int Func_MyKey(string str)
{
int suma = 0;
for (int i = 0; i < size(str) - 1; i++)
{
suma += str[i];
}
return ((suma + 7) * size(str)) % N;
}
bool MyAdd(Node* &ptr, string str) //додавання елемента в другу хеш-таблицю
{
if (ptr == NULL)
{
ptr = new Node;
ptr->data = str;
ptr->next = NULL;
}
else
{
if (ptr->data != str)
MyAdd(ptr->next, str);
else
return false;
}
}
void vuvid2(Node* &ptr) //вивід другої хеш-таблиці
{
if (ptr != NULL)
{
cout << ptr->data << "\t";
if (ptr->next != NULL)
vuvid2(ptr->next);
}
}
int k = 1;
bool MySearch(Node* &ptr, string str, int vubir = 0) //пошук елемента в другій хеш-таблиці
{
if (ptr != NULL)
{
if (vubir == 3 && ptr->data != str)
{
cout << ptr->data << ", ";
k++;
}
if (ptr->data == str)
return true;
else
{
if (MySearch(ptr->next, str, vubir))
return true;
else
return false;
}
}
else
return false;
}
bool MyRemove(Node* &ptr, string str)
{
if (ptr != NULL)
{
if (ptr->data == str)
ptr = ptr->next;
else
MyRemove(ptr->next, str);
}
if (ptr == NULL)
return false;
}
////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
//const int NotUsed = system("color 70");
setlocale(0, "");
cout << "\tХеш-таблиця 1" << endl;
//№ варіанта = [ (день народження) * (ASCII–код першої літери прізвища – велика латинська літера)] % 20 + 1
cout << "Для хеш-функцiй: " << (9 * 'B') % 20 + 1 << " варiант" << endl;
//№ варіанта = [(місяць народження) * (ASCII–код першої літери прізвища – велика латинська літера)] % 25 + 1
cout << "Для колiзiй: " << (11 * 'B') % 25 + 1 << " варiант" << endl;
cout << "\tХеш-таблиця 2" << endl;
//№ варіанта = [(день народження) * (місяць народження)] % 11 + 1
cout << "Для колiзiй: " << (9 * 11) % 11 + 1 << " варiант" << endl << "****************************************************************" << endl;
////////////////////////////////////////////////////////////////////////////////////////////
string* table1[M]; //хеш-таблиця 1
Node* table2[N];// хеш-таблиця 2
for (int i = 0; i < M; i++)
{
table1[i] = NULL;
if (i < N)
table2[i] = NULL;
}
ifstream read_file("data.txt");
if (!read_file.is_open())
cout << "Файл не вiдкривається!\n";
else
{
string str;
while (!read_file.eof()) //зчитування слів з файлу
{
getline(read_file, str, ',');
add(table1, str); //запис в першу хеш-таблицю
MyAdd(table2[Func_MyKey(str)], str); //запис в другу хеш-таблицю
}
}
read_file.close();
//меню програми
int vubir;
tyt:
cout << "\n1. Добавити елемент\n2. Видалити елемент\n3. Пошук елемента\n4. Вивiд" << endl;
cout << "Зробiть вибiр: "; cin >> vubir;
switch (vubir)
{
case 1: //додати слово в хеш-таблицю
{
string str;
cout << "\n\nВведiть слово: "; cin >> str;
if (add(table1, str) && MyAdd(table2[Func_MyKey(str)], str))
cout << "Елемент додано" << endl;
else
cout << "Такий елемент вже є" << endl;
cout << "\n\nПовернутись (натисни 1): "; cin >> vubir;
if (vubir == 1)
{
system("cls");
goto tyt;
}
break;
}
case 2: // видалення елемента
{
string str;
cout << "\n\nВведiть слово: "; cin >> str;
MyRemove(table2[Func_MyKey(str)], str);
if (remove(table1, str) == false)
cout << "Такого елементу неiснує" << endl;
else
{
cout << "Елемент видалено" << endl;
}
cout << "\n\nПовернутись (натисни 1): "; cin >> vubir;
if (vubir == 1)
{
system("cls");
goto tyt;
}
break;
}
case 3: // пошук елемента
{
string str;
cout << "\n\nВведiть слово: "; cin >> str;
// для другої таблиці
if (search(table1, str) == false)
cout << "Такого елемента немає!" << endl;
else
{
cout << "\nЗнайдено:\nTable1[" << search(table1, str) << "] = " << *table1[search(table1, str)] << endl;
cout << "Порiвнюваннi слова: ";
search(table1, str, vubir);
cout << str << endl;
cout << "Кiлькiсть порiвнянь: " << m << endl;
m = 0;
}
// для другої таблиці
if (MySearch(table2[Func_MyKey(str)], str))
{
cout << "\nTable2[" << Func_MyKey(str) << "] = " << str << endl;
cout << "Порiвнюваннi слова: ";
MySearch(table2[Func_MyKey(str)], str, vubir);
cout << str << endl;
cout << "Кiлькiсть порiвнянь: " << k << endl;
k = 0;
}
cout << "\n\nПовернутись (натисни 1): "; cin >> vubir;
if (vubir == 1)
{
system("cls");
goto tyt;
}
break;
}
case 4: // вивід таблиць
{
cout << "\n" << endl;
for (int i = 0; i < M; i++)
{
if ((table1[i] != NULL) && (*table1[i] != "del"))
cout << "Table1[" << i << "]: " << *table1[i] << endl;
}
for (int i = 0; i < N; i++)
{
cout << "table2[" << i << "]: ";
vuvid2(table2[i]);
cout << endl;
}
cout << "\n\nПовернутись (натисни 1): "; cin >> vubir;
if (vubir == 1)
{
system("cls");
goto tyt;
}
break;
}
}
}
Результат виконання програми:
/
Рис.1 – Пошук елементу
/
Рис.2 – Вивід таблиць
Висновок: на даній лабораторній роботі я вивчив що таке хеш-таблиця і опанував різні методи їх побудов.
29.03.2016 08:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора