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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

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

Рік:

2017

Тип роботи:

Лабораторна робота

Предмет:

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

Завантажити

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

Міністерство освіти і науки Національний університет «Львівська політехніка» Кафедра ЕОМ Звіт до лабораторної роботи № 2 з дисципліни: “Алгоритми та методи обчислень” на тему: “ Розробка та дослідження ефективності методів пошуку даних ” Львів – 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, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої. Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць. В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці. Під час пошуку слів в хеш-таблицях програма повинна виводити на екран послідовність слів з якими виконуються порівняння і кількість виконаних операцій порівняння. Лістинг програми: CashTable.h #include "Node.h" #include <time.h> #include <vector> #include <list> class CashTable { public: CashTable(int Size); ~CashTable(); Node* Find(string Key); bool Add(string Key, Node* node); bool Delete(string Key); void Print(); private: int hesh_helper(string Key); private: int m_iSize; vector<vector<Node*>> m_vTable; }; Node.h #define _CRT_SECURE_NO_WARNINGS #include <string> #include <iostream> using namespace std; class Node { public: Node(string Name, string LastName, string Number); Node(const Node &nd); ~Node(); void SetName(string name); string GetName(); void SetLastName(string LastName); string GetLastName(); void SetNumber(string Number); string GetNumber(); void print(); private: string m_sName; string m_sLastName; string m_sNumber; }; CashTable.cpp #include "CashTable.h" CashTable::CashTable(int Size) { m_iSize = Size; m_vTable.resize(m_iSize); } CashTable::~CashTable() { for (int i = 0; i < m_vTable.size(); i++) for (int j = 0; m_vTable[i].size(); j++) { if (m_vTable[i][j] != NULL) { delete m_vTable[i][j]; m_vTable[i][j] = NULL; } } } Node* CashTable::Find(string Key) { int tmp = hesh_helper(Key); for (int i = 0; i < m_vTable[tmp].size(); i++) { if (m_vTable[tmp][i]->GetNumber() == Key) { return m_vTable[tmp][i]; } } return NULL; } bool CashTable::Add(string Key, Node* node) { if (Find(Key)==NULL) { int tmp = hesh_helper(Key); m_vTable[tmp].push_back(NULL); m_vTable[tmp][m_vTable[tmp].size() - 1] = node; return true; } return false; } bool CashTable::Delete(string Key) { int tmp = hesh_helper(Key); for (int i = 0; i < m_vTable[tmp].size(); i++) { if (m_vTable[tmp][i]->GetNumber() == Key) { delete m_vTable[tmp][i]; m_vTable[tmp][i] = NULL; m_vTable[tmp].erase(m_vTable[tmp].begin() + i); return true; } } return false; } int CashTable::hesh_helper(string Key) { int sum=0; char * data = new char[Key.size() + 1]; strcpy(data, Key.c_str()); data[Key.size()] = '\0'; for (int i = 0; i < Key.size(); i++) { sum += data[i]; } delete[] data; int p = ((sum)<<2) % m_iSize; if (p < 0) return -p; else return p; } void CashTable::Print() { for (int i = 0; i < m_vTable.size(); i++) { for (int j = 0; j < m_vTable[i].size(); j++) { if (m_vTable[i][j] != NULL) { m_vTable[i][j]->print(); cout <<endl; } } } } Node.cpp #include "Node.h" Node::Node(string Name, string LastName, string Number) { m_sName = Name; m_sLastName = LastName; m_sNumber = Number; } Node::Node(const Node &nd) { m_sName = nd.m_sName; m_sLastName = nd.m_sLastName; m_sNumber = nd.m_sNumber; } Node::~Node() { } void Node::SetName(string name) { m_sName = name; } string Node::GetName() { return m_sName; } void Node::SetLastName(string LastName) { m_sLastName = LastName; } string Node::GetLastName() { return m_sLastName; } void Node::SetNumber(string Number) { m_sNumber = Number; } string Node::GetNumber() { return m_sNumber; } void Node::print() { cout << m_sName << " " << m_sLastName << " " << m_sNumber<<" "; } Main.cpp #include "CashTable.h" int main() { CashTable CTable(37); Node *p1 = new Node("Tania", "Sulyma", "380907654345"); Node *p2 = new Node("Petro", "Petryk", "380456709123"); Node *p3 = new Node("Ivan", "Zvenyhora", "380509876543"); Node *p4 = new Node("Vasulii", "Lobotryas", "380120956783"); Node *p5 = new Node("Sasha", "Sushka", "784521658467"); Node *p6 = new Node("Serhii", "More", "123548538735"); CTable.Add(p1->GetNumber(), p1); CTable.Add(p2->GetNumber(), p2); CTable.Add(p3->GetNumber(), p3); CTable.Add(p4->GetNumber(), p4); CTable.Add(p5->GetNumber(), p5); CTable.Add(p6->GetNumber(), p6); cout << "Original Table: \n" << endl; CTable.Print(); cout << endl; cout << "Find elem with key='380907654345': \n" << endl; if (CTable.Find("380907654345") != NULL) CTable.Find("380907654345")->print(); cout << endl<<endl; cout << "Delete elem with key='380907654345': \n" << endl; CTable.Delete("380907654345"); CTable.Print(); cout << endl; system("pause"); return 0; } Результат виконання програми: / Висновок: на даній лабораторній роботі я вивчила що таке хеш-таблиця і опанувала різні методи їх побудови.

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

22tann22

09.10.2017 23:13

Коментарі

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

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

поділитись