Сиакод 2 испр
.docxФГБОУ ВО
Уфимский Государственный Авиационный Технический Университет
Кафедра ВМиК
Отчет по лабораторной работе №2
«Работа с хеш-таблицей»
по дисциплине
«Структуры и алгоритмы компьютерной обработки данных»
Выполнил:
студент группы МО-217
Шакиров Айдар Рушанович
Проверила:
Канд. техн. наук, доцент
Верхотурова Галина Николаевна
Уфа 2019
Цель:
Целью лабораторной работы является получение навыков работы с хеш-таблицей, содержащей заданную последовательность элементов (ключей).
Задание:
В программу из первой лабораторной работы («Построение хеш-таблицы») добавить следующие функции:
Функция генерирования или ввода в интерактивном режиме новых элементов.
Функция поиска элементов.
Функция добавления нового элемента.
Функция удаления элемента.
Функция замены элемента.
Функция для вывода параметров коэффициента заполнения и среднего числа проб.
Входные данные:
Table[] – исходная хеш-таблица;
Size – размерность хеш-таблицы Table[];
Occupancy – количество элементов в таблице;
Key1 – первое значение, введенное с клавиатуры;
key2 – второе значение, введенное с клавиатуры.
Выходные данные:
Table[] – итоговая хеш-таблица;
Occupancy – итоговое количество элементов в таблице;
CoefOccupancy –коэффициент заполнения таблицы;
AverageCountAttempt – среднее число проб.
Ход работы:
1. Отображаем диалоговый интерфейс для использования функций добавления, поиска, удаления, замены элементов, а также вывода параметров хеш-таблицы и выхода из программы.
while (true)
{
Console.WriteLine("Хеш-таблица:");
hashTable.PrintTable();
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Cyan;
Console.WriteLine("Интерактивный режим");
Console.WriteLine("1.Добавить ключ");
Console.WriteLine("2.Найти индекс по ключу");
Console.WriteLine("3.Удалить ключ");
Console.WriteLine("4.Заменить один ключ другим");
Console.WriteLine("5.Вывести параметры");
Console.WriteLine("0.Выход");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine();
...
Пользователь вводит соответствующее число, чтобы перейти к соответствующему действию.
В зависимости от действия вводятся 1 или 2 значения поочередно, которые будут переданы выбранной функции для работы с хеш-таблицей.
Console.Write("Выбор режима: ");
var mode = Console.ReadLine();
int key1, key2;
string str;
switch (mode[0]) //читаем первый символ введенного ответа
{
case '1':
Console.WriteLine("1.Свой ключ");
Console.WriteLine("2.Диапазон случайных");
Console.WriteLine();
Console.Write("Выбор режима: ");
mode = Console.ReadLine();
switch (mode[0])
{
case '1':
Console.WriteLine();
Console.Write("Введите ключ = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key1))
break;
if (hashTable.Add(key1))
NumberElements++;
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
case '2': //добавление случайных значений
Console.WriteLine();
Console.Write("Сколько ключей = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key1) || key1 < 0)
break;
var rand = new Random();
for (int i = 0; i < key1; i++)
if (hashTable.Add(rand.Next(10000, 99999)))
NumberElements++;
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
}
break;
case '2':
Console.WriteLine();
Console.Write("Введите ключ = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key1))
break;
hashTable.Find(key1);
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
case '3':
Console.Write("Введите ключ = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key1))
break;
if(hashTable.Remove(key1))
NumberElements--;
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
case '4':
Console.WriteLine();
Console.Write("Введите ключ для замены = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key1))
break;
Console.Write("Введите ключ чем заменить = ");
str = Console.ReadLine();
if (!int.TryParse(str, out key2))
break;
hashTable.Replace(key1,key2);
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
case '5':
Console.WriteLine();
Console.WriteLine("Коэффициент заполнения таблицы = {0:0.000}", hashTable.CoefOccupancy);
Console.WriteLine("Среднее число проб = {0:0.000}", hashTable.AverageCountAttempt);
Console.WriteLine("Нажмите любую клавишу, чтобы продолжить");
Console.ReadKey();
break;
case '0':
return;
default:
break;
}
}
После выполнения какого-либо действия выводится обновленная хеш-таблица и меню диалогового интерфейса.
3. Функция добавления элемента (ключа) в хеш-таблицу.
Получает на вход введенный нами элемент. Возвращает истинность добавления элемента.
Сначала проводит хеширование. Полученный индекс сохраняет как первоначальный индекс.
Запускает бесконечный цикл с параметром i – число проб, начиная с единицы.
Увеличивает число проб.
Затем проверяет равна ли null ячейка по полученному индексу или стоит ли пометка об удалении в соответствующей таблице.
Если да, то заносит по нему наш ключ и снимает пометку (делает равной false) об удалении по этому индексу и прерывает цикл.
Иначе проверяет совпадает ли наш ключ с занятым.
Если совпадает, то прерывает работу функции. Функция возвращает результат false.
Иначе производит новое хеширование в соответствии с методом разрешения коллизий – квадратичных проб. Сохраняет индекс.
Если количество проб превышает количество занятых ячеек в таблице, то завершает выполнение функции с результатом false.
Производит новые итерации цикла.
По окончании цикла увеличивает количество добавленных элементов таблицы и завершает работу функции с результатом true.
public bool Add(int key)
{
var index = this.Hash(key); //Использование хэш-функции
var index0 = index; //первоначальный индекс
for (int i = 1; ; i++) //номер пробы
{
this.IncCountAttempt(); //+1 проба
//если ячейка таблицы свободна или была удалена, то вносим значение элемента
if (Table[index] == null || Deleted[index])
{
Table[index] = key;
Deleted[index] = false;
break;
}
//если занята, то используем метод разрешения коллизий – квадратичные пробы
//index0 хранит значение первой пробы
else
{
if(Table[index] == key)
{
return false;
}
if (this.IsLog)
index = (index0 + (i * i)) % SizeTable;
}
if(i > Occupancy) //если попыток больше количества занятых ячеек, то прекращаем добавление
{
return false;
}
}
return true;
}
6. Функция поиска элемента.
Принимает на вход ключ, а возвращает индекс данного ключа в случае нахождения и возвращает -1 в случае неудачи.
Сначала происходит хеширование ключа, запоминается как первичный индекс.
Запускает бесконечный цикл с параметром i – число проб, начиная с единицы.
Если ячейка по данному индексу пустая, то поиск прекращает работу и возвращает -1.
Иначе по полученному индексу проверяется совпадает ли входной элемент с тем, который находится по индексу и не помечен как удаленный в соответствующей таблице.
Если да, то возвращается индекс.
Иначе происходит разрешение коллизий аналогично функции добавления.
Если количество проб превышает размер таблицы, то возвращается -1.
Производятся новые итерации цикла.
public int Find(int key)
{
var index = this.Hash(key); //Использование хэш-функции
var index0 = index; //первоначальный индекс
for (int i = 1; ; i++) //номер пробы
{
if (Table[index] != null)
{
if (Table[index] == key && !Deleted[index])
{
return index;
}
//если ключ не совпадает или был удален, то используем метод разрешения коллизий – квадратичные пробы
index = (index0 + (i * i)) % SizeTable;
}
//если ячейка свободна, то ключ не найден
else
{
return -1;
}
if (i > SizeTable)
return -1;
}
}
7. Функция удаления элемента из хэш-таблицы.
Она принимает на вход ключ, возвращает истинность успешности операции.
Сначала производит поиск элемента в хеш-таблице с помощью функции поиска элемента. Результат сохраняется.
Если результат не равен -1 (то есть найден), то данный элемент помечаем как удаленный, т. е. в массиве Deleted задаем по данному индексу true.
Возвращаем true.
Иначе возвращаем false.
public bool Remove(int key)
{
var findIndex = Find(key);
if (findIndex != -1)
{
Deleted[findIndex] = true;
return true;
}
return false;
}
8. Функция замены элемента хэш-таблицы.
Функция принимает 2 ключа – заменяемый и замещающий. Возвращает истинность положительного исхода операции.
Удаляем удаляемы элемент с помощью функции удаления.
Если удаление произошло успешно, то добавляем замещающий элемент с помощью функции добавления.
Возвращаем true.
Иначе возвращаем false.
public bool Replace(int source, int destination)
{
if (Remove(source))
{
Add(destination);
}
return false;
}
9. Вывод параметров на экран
Она выводит коэффициент заполнения таблицы и среднее число проб.
Коэффициент заполнения таблицы вычисляется делением количества занятых ячеек таблицы на размер таблицы.
Среднее число проб вычисляется делением количества произведенных проб на количество элементов, которые были добавлены в таблицу.
public double CoefOccupancy { get { return (double)Occupancy / SizeTable; } }
public double AverageCountAttempt { get { return (double)CountAttempt / addedElements; } }
…
Console.WriteLine("Коэффициент заполнения таблицы = {0:0.000}", hashTable.CoefOccupancy);
Console.WriteLine("Среднее число проб = {0:0.000}", hashTable.AverageCountAttempt);
Результат работы программы:
Заключение:
В ходе лабораторной работы была изучена и построена хэш-таблица, использующая метод разрешения коллизий – квадратичные пробы. В ней реализованы методы поиска, добавления, удаления и замены элементов.