Розробка та дослідження ефективності методів пошуку даних. Звіт до лабораторної роботи з Алгоритми та методи обчислень. Робота № 527796

Розробка та дослідження ефективності методів пошуку даних

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2016

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритми та методи обчислень

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки Національний університет «Львівська політехніка» Кафедра ЕОМ Звіт до лабораторної роботи № 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 – Вивід таблиць Висновок: на даній лабораторній роботі я вивчив що таке хеш-таблиця і опанував різні методи їх побудов.

Звіт до лабораторної роботи Алгоритми та методи обчислень

R.Karpyn

29.03.2016 08:00

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись