Міністерство освіти і науки України Національний університет “Львівська Політехніка” Кафедра ЕОМ Звіт До лабораторної роботи №7 На тему “ Розробка та дослідження ефективності методів пошуку даних ” Завдання Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць. Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому): прізвище, ім'я, побатькові, день, місяць,рік народження, назва компанii мобільного зв'язку, підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр), назва області, міста і вулиці в адресі прописки, номер будинку і квартири в адресі прописки, абревіатура інститута, кафедри, групи, день, місяць,рік виконання лабораторної роботи. Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої. Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць. В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці. Код програми #include <iostream> #include <string> #include <fstream> #include <string> using namespace std; int func_hesh1_met_1(char a[]); int func_hesh1_met_2(char *a,int i); int func_hesh2_met_3(char *a,int i); int add(char Hesh2_m1[37][128],char str[128]); int main(){ char Hesh1_m1[37][128]; char Hesh2_m1[37][128]; char a[28][128]; int i=0; int j=0; int n=128; for(i=0;i<37;i++){ for(j=0;j<128;j++){ Hesh1_m1[i][j]=NULL; Hesh2_m1[i][j]=NULL;}} for(i=0;i<28;i++){ for(j=0;j<128;j++){ a[i][j]=0;}} ifstream file("data.txt"); for(int i=0;i<28;i++){ file >> a[i]; } file.close(); //хеш таблиця номер 1 for(int i=0;i<28;i++) { int indx=1; int buff; int g=0; do{ buff=func_hesh1_met_2(a[i],indx); if(Hesh1_m1[buff][0]==NULL) { g=1; for(j=0;j<128;j++){ Hesh1_m1[buff][j]=a[i][j]; } } else indx++;} while(g!=1);} for(i=0;i<37;i++){ cout<<endl; for(j=0;j<28;j++){ cout<<Hesh1_m1[i][j];}} cout<<endl<<"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"<<endl; //хеш таблиця номер 2 for(int i=0;i<28;i++){ int indx=1; int buff; int g=0; do{ buff=func_hesh2_met_3(a[i],indx); if(Hesh2_m1[buff][0]==NULL){ g=1; for(j=0;j<128;j++){ Hesh2_m1[buff][j]=a[i][j];}} else indx++;} while(g!=1);} for(i=0;i<37;i++){ cout<<endl; for(j=0;j<28;j++){ cout<<Hesh2_m1[i][j];}} cout<<endl<<"ADD-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"<<endl; char str[128]; for(j=0;j<128;j++){ str[j]=0;} cin>>str; int g=0; g=add(Hesh2_m1,str); for(j=0;j<128;j++){ Hesh2_m1[g][j]=str[j];} for(i=0;i<37;i++){ cout<<endl; for(j=0;j<28;j++){ cout<<Hesh2_m1[i][j];}} cout<<endl; return 0;} int func_hesh1_met_1(char a[]){ return (a[0]%37);} int func_hesh1_met_2(char *a,int i) { return ((func_hesh1_met_1(a)+i + 4*i^2) % 37);} int func_hesh2_met_3(char *a,int i) { return ((func_hesh1_met_1(a)+i) % 37);} int add(char Hesh2_m1[37][128],char str[128]){ int buff; buff=func_hesh2_met_3(str,1); return buff;} Перша хеш таблиця / Друга хеш таблиця / Друга хеш таблиця після додавання елемента / Пошук існуючого елемента в хеш таблиці Пошук неіснуючого елемента в хеш таблиці Аналіз ефективності. На основі вигляду першої хеш таблиці можна зробити висновок про те, що вона буде більш ефективною. Це можна визначити підрахувавши кількість утворених кластерів. В першій хеш таблиці є 8 кластерів, і найбільший з них має 11 елементів. В другій хеш таблиці утворилося 4 кластери, і найдовший з них має 22 елементи. Ефективнішою таблицею буде перша, оскільки негативно на швидкість пошуку впливає довжина кластера, яка впливає на максимальну кількість порівнянь. В першій хеш таблиці максимальна довжина кластера 11 елементів, відповідно необхідно виконати в найгіршому випадку 11 порівнянь В другій хеш таблиці максимальна довжина кластера 22 елементи, відповідно в найгіршому випадку необхідно буде виконати 22 порівняння. Отже перша хеш таблиця є більш ефективною ніж друга. Висновок: я дослідив ефективність методів пошуку на прикладі різних методів організації хеш-таблиць, та вивчив основні методи побудови хеш-таблиць, дослідив переваги і недоліки, властиві різним методам, оцінив ефективність і провів порівняння ефективностей.