Отчёт по хеш-таблицам
.docМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра ВМиК
Отчёт
по лабораторной работе
«Построение хеш-таблицы»
18 Вариант
Выполнил: студ. гр. ПРО-204
Бычковская Д.С.
Проверил:
Верхотурова Г.Н.
Уфа-2013
Постановка задачи
Построить хеш-таблицу, содержащую последовательность из m = 47 элементов размерности n = 5. Элементы генерируются с помощью датчика случайных чисел.
Хеш-функция – сумма двух последних и двух первых цифр элементов.
Метод открытой адресации с линейным опробованием.
Входные и выходные данные
Основные структуры и переменные, в которых будут обрабатываться и храниться входные и выходные данные, представлены следующим образом:
-
const int m=47
переменная содержит количество элементов, для которых будет построена хеш-таблица
-
const int t=m*1.5
переменная содержит максимальное количество элементов, которые можно разместить в хеш-таблице. Также она обозначает размер хеш-таблицы, который должен быть примерно в полтора раза больше размещаемых элементов (их 47)
-
int a[m]
массив, в котором будут располагаться сгенерированные целые двузначные элементы
-
int b[t]
массив, представляющий собой хеш-таблицу. Индекс элемента в массиве будет соответствовать его ключу
-
int j, prob=0, zapoln=0
целые переменные. Переменная j служит для работы с ключом очередного элемента, prob подсчитывает количество всех повторных проб размещения элементов в хеш-таблицу, переменная zapoln после заполнения хеш-таблицы считает количество заполненных ячеек
Также в программе использованы переменные i и j, которые не являются входными или выходными данными, но нужны в прграмме в служебных целях (для реализации циклов и подсчётов).
Реализация
#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
#include <time.h>
using namespace std;
int main()
{
srand(time(0));
const int m=47;
const int t=1.5*m; // размероность хеш-таблицы
long int a[m];
for (int i=0; i<m; i++)
{
l: a[i]=(rand()%9+1)*10000+(rand()*rand())%10000; /* Генератор случайных пятизначных чисел */
for (int j=0; j<(i); j++)
{
if (a[i]==a[j]) goto l;
}
cout<<"a["<<i+1<<"]="<<a[i]<<endl;
}
cout<<endl;
int prob=0; // число проб
int b[t]; // хеш-таблица
for (int i=0; i<t; i++) b[i]=0; /* помечаем ячейки таблицы, как свободные*/
for (int i=0; i<m; i++)
{
int c=0;
int j; /* хеш-функция: сумма первых двух и двух последних цифр элемента*/
j=((a[i]/1000+a[i]%100)%t); prob++;
int j0=j;
top:if(b[j]==0) // если ячейка хеш-таблицы свободна, заносим элемент
{
b[j]=a[i];
prob++;
}
else // если коллизия
{
prob++;
c++;
j=(j0+c)%t; //..то меняем адрес на адрес соседней ячейки
goto top;
}
}
for (int i=0; i<t; i++) cout<<"b["<<i<<"]="<<b[i]<<endl;
double srprob;
srprob=1.0*prob/m; // подсчет среднего числа проб
cout<<"srednee chislo prob="<<srprob<<endl;
int zapoln=0;
for (int i=0; i<t; i++)
{
if (b[i]!=0) zapoln++;
}
double koef; koef=1.0*zapoln/t; // подсчет коэфицента заполнения хеш-таблицы
cout<<"koeficent zapolneniya="<<koef<<endl;
system("pause");
}
Вывод
В данной лабораторной работе я познакомилась с такой структурой данных как хеш-таблица, научилась считать ключи элементов по хеш-функции, размещать эти элементы в таблицу согласно их ключам, а также устранять коллизии несколькими методами.