Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КІ-25
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
" Розробка та дослідження ефективності методів сортування "
Лабораторна робота № 7
з дисципліни:
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ "
Львів 2012
Мета роботи :
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Постановка задачі
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):
прізвище, ім'я, побатькові,
день, місяць,рік народження,
назва компанii мобільного зв'язку,
підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),
назва області, міста і вулиці в адресі прописки,
номер будинку і квартири в адресі прописки,
абревіатура інститута, кафедри, групи,
день, місяць,рік виконання лабораторної роботи.
а) Анкетні дані (вміст файлу data.txt)
б) Індивідуальне завдання
6.1.6
в) Обрана самостійно хеш-функція та метод розв'язання колізій.
h(key)= (АSCII-код першого символа ключа)%m;
m=39;
Функція повторного хешування hi(key)=(h(key)+i)%m;
Метод лінійної послідовності спроб. Суть цього методу полягає в тому, що при колізії комірки таблиці перевіряється послідовно одна за одною, якщо комірка порожня то ключ заноситься до неї, якщо комірка заповнена, то перевіряється наступна після неї комірка. Якщо досягається кінець таблиці то пошук продовжується з першої комірки таблиці з індексом 0, тобто хеш-таблиця розглядається як циклічний масив.
2. Завдання 1. Організація хеш-таблиці №1.
2.1 Обчислення хеш-значень (написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файла data.txt).
Вигляд хеш-функції h(key) = [сума АSCII-кодів перших трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m; m=37;
Функція повторного хешування hi(key)=(h(key)+7*i)%m;
h(Yaschuk)=(89+97+115)%37=5
h(Oleksandr)=(79+108+101)%37=29
h(Valeriyovuch)=(86+97+108)%37=32
h(26)=(50+54+50)%37=6
h(12)=(49+50+49)%37=0
h(1993)=(49+57+57)%37=15
h(Life)=(76+105+102)%37=24
h(0)=(48+48+48)%37=33
h(9)=(57+57+57)%37=23
h(7)=(55+55+55)%37=17
2.2Побудова хеш-таблиці
(для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити; визначити кількість кластерів в побудованій таблиці та довжину найбільшого кластера).
Ключі
Дані
Ключі
Дані
0
12
20
1
21
2
22
3
23
9
4
24
Life
5
Yaschuk
25
6
26
26
7
27
8
28
9
29
Oleksandr
10
30
11
31
12
32
Valeriyovuch
13
33
0
14
34
15
1993
35
16
36
17
7
18
19
2.3Пошук ключа:
(словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку).
Key = 4;
Алгоритм пошуку переглядає всі комірки хеш-таблиці в тому самому порядку, що і при вставці, доки не знайдеться або елемент з шуканим ключем, або вільна комірка (що означає відсутність елемента в хеш-таблиці).
Під час пошуку ключа 4, відбувається порівняння з такими ключами:
h(4)=( 52+52+52)%37= 8
Результат: 8
2.4 Результати роботи програми з першою хеш-таблицею:
(вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента).
/
Рис1.Вигляд побудованої хеш-таблиці.
/
Рис.2.Вигляд хеш-таблиці після додавання елементу(NEW, знаходиться за індексом 12).
/
Рис.3.Вигляд хеш-таблиці після вилучення елементу (NEW).
3. Завдання 2. Організація хеш-таблиці №2:
3.1 Обчислення хеш-значень
(написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файла data.txt).
Вигляд хеш-функції h(key)=(АSCII-код першого символа ключа)%m;
m=39;
Функція повторного хешування hi(key)=(h(key)+i)%m;
h(Yaschuk)=89%39=11
h(Oleksandr)=79%39=1
h(Valeriyovuch)=86%39=8
h(26)=50%39=11
h1(26)=51%39=12
h(12)=49%39=10
h(1993) = 49 % 39 = 10
h1(1993) = 50 % 39 = 11
h2(1993) = 51 % 39 = 12
h3(1993) = 52 % 39 = 13
h(Life)=76%39=37
h(0)= 48 % 39 = 9
h(9)= 57 % 39 = 18
h(7)=55%39=16
3.2Побудова хеш-таблиці:
(для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити).
Ключі
Дані
Ключі
Дані
0
20
1
Oleksandr
21
2
22
3
23
4
24
5
25
6
26
7
27
8
Valeriyovuch
28
9
0
29
10
12
30
11
Yaschuk
31
12
26
32
13
1993
33
14
34
15
35
16
7
36
17
37
Life
18
9
38
19
3.3 Пошук ключа:
(словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку).
Пошук ключа відбувається за таким же самим принципом як у хеш-таблиці №1.
Key = 4;
Під час пошуку ключа 4 , відбувається порівняння з такими ключами:
h(4)=52 % 39 = 13
Резульат: 13
3.4. Результати роботи програми з другою хеш-таблицею:
(вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента, послідовність пошуку ключа key в хеш-таблиці, значення С n i С m ).Сn = 28;Сm = 39
/
Рис.4.Вигляд побудованої другої хеш-таблиці.
/
Рис.5.Вигляд хеш-таблиці після додавання елементу(NEW, знаходиться за індексом 3).
/
Рис.6.Вигляд хеш-таблиці після вилучення елементу (NEW).
4. Аналіз ефективності побудованих методів організації хеш-таблиць.
4.1. Графіки С=f(α) (графік С=f1(α) для хеш-таблиці №1 і графік С=f2(α) для хеш-таблиці №2).
Для n=10;
Для 1-ої і 2-ої хеш-таблиць:С1=1;С2=2;……….С6=7;С7=8;С8=9;С9=10;С10=11;
//
C=f1(α) C=f2(α)
4.2. Графіки С=f(m) (графік С=f1(m) для хеш-таблиці №1 і графік С=f2(m) для хеш-таблиці №2)
Для n=10;
Для 1-ої хеш-таблиці:С1=31;С2=12;С6=22;С10=12;
Для 2-ої хеш-таблиці:С1=16;С2=12;С6=11;С10=12;
//
4.3. Висновки про ефективність (порівняти ефективності побудованих методів організації хеш-таблиць).
Відповідно до обрахунку кількості порівнянь для пошуку слів у двох хеш-таблицях, бачимо, що кількість порівнянь для пошуку слів відповідно з першими графіками однакова(це коли ми змінюєм кількість слів для пошуку, а не розмір таблиці).Згідно других графіків, бачимо, що у 2-ій хеш-таблиці кількість порівнянь для пошуку всіх слів у таблиці менша ніж кількість порівнянь у 1-ій хеш-таблиці.Це означає, що у 2-ій хеш-таблиці пошук елементів відбувається швидше ніж у 1-ій хеш-таблиці.
Додатки (тексти програм з коментарями).
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <conio.h>
using namespace std;
char Table_1[37][14]; // оголошення хеш-таблиці 1 на базі масиву
char Table_2[40][14]; // оголошення хеш-таблиці 2 на базі масиву
void vyvid() /// вивід першої таблиці
{
cout << "\n\n------------- TABLE 1 ----------------\n\n";
for (int i=0;i<37;i++)
cout << i << "\t" << Table_1[i] << "\n";
cout << "\n-----------------------------------------\n";
}
void vyvid_2() /// вивід другої таблиці
{
cout << "\n\n------------- TABLE 2 ----------------\n\n";
for (int i=0;i<40;i++)
cout << i << "\t" << Table_2[i] << "\n";
cout << "\n-----------------------------------------\n";
}
bool remove_data(char *data,int i) /// видаляє елемент з першої таблиці
{
if(!strcmp(Table_1[i],data)) // за ключем і
{
cout << "\n\nElement deleted \n\n";
Table_1[i][0]=0;
return 0;
}
else
return 1;
}
bool remove_data_2(char *data,int i) /// видаляє елемент з другої таблиці
{
if(!strcmp(Table_2[i],data)) // за ключем і
{
cout << "\n\nElement deleted \n\n";
Table_2[i][0]=0;
return 0;
}
else
return 1;
}
void main()
{
ifstream file_in("data.txt",ios::in);
if(!file_in)
{
cerr<<"File could not be opened"<<endl<<endl;
exit(1);
}
char *temp=new char[2],data[14];
int i=0,j=0,n=0;
int key;
for (i=0;i<37;i++)
Table_1[i][0]=0;
for (i=0;i<40;i++)
Table_2[i][0]=0;
temp[1] = 0;
while(!file_in.eof())
{
j=0;
while(1)
{
file_in.read(temp,1);
if(temp[0] == ',' || file_in.eof ())
{
data[j]=0;
break;
}
data[j++]=*temp;
}
// пошук ключа
if(data[2]==0)
{
key = (2*data[0]+data[1])%37;
}
else
{
if(data[1]==0)
{
key = (3*data[0])%37;
}
else
{
key = (data[0]+data[1]+data[2])%37;
}
}
int a=key;
/// заповнення першої таблиці
n=0;
while (Table_1[key][0]!=0 && n!=38)
{
key = (a+7*n)%37; // пошук ключа
n++;
}
strcpy(Table_1[key],data);
/// заповнення другої таблиці
n=0;
do
{
key = data[0] % 39; // пошук ключа
key = (key + n) % 39;
n++;
} while (Table_2[key][0]!=0 && n!=40);
strcpy(Table_2[key],data);
i++;
}
//////////////////////////////////////////////////////////////////////////
vyvid ();
strcpy(data,"NEW");
if(data[2]==0)
key = (2*data[0]+data[1])%37;
else if(data[1]==0)
key = (3*data[0])%37;
else
key = (data[0]+data[1]+data[2])%37;
int b=key;
n=0;
while (Table_1[key][0]!=0 && n!=38)
{
key = (b+7*n)%37; // пошук ключа
n++;
}
strcpy(Table_1[key],data);
cout << "\n\n------------- ADD element ------------------\n\n";
vyvid ();
cout << "\n\n------------- DELETE element ------------------\n\n";
remove_data (data,key);
vyvid ();
//////////////////////////////////////////////////////////////////////////
vyvid_2 ();
cout << "\n\n------------- ADD element ------------------\n\n";
n=0;
do
{
key = data[0] % 39; // пошук ключа
key = (key + n) % 39;
n++;
} while (Table_2[key][0]!=0 && n!=40); // якщо згідно ключа комірка в таблиці є пустою - розміщуємо елемент, інакше продовжуємо генерацію іншого ключа
strcpy(Table_2[key],data);
vyvid_2();
cout << "\n\n------------- DELETE element ------------------\n\n";
n=0;
do /// послідовність пошуку ключа в хеш таблиці
{
key = data[0] % 39;
key = (key + n) % 39;
n++;
} while (remove_data_2 (data,key) && n!=40); // якщо елемент за даним ключем знайдено - видаляємо його
if (n == 40)
cout << "\n\nELEMENT IS NOT FOUND \n\n";
vyvid_2();
delete [] temp;
getch();
}
19.11.2012 00:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора