Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів пошуку даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 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;
}
Результат виконання програми:
/
Висновок: на даній лабораторній роботі я вивчила що таке хеш-таблиця і опанувала різні методи їх побудови.
09.10.2017 23:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора