лаба. Лабораторная работа 4 по дисциплине Алгоритмы и структуры данных Коллекция данных Хештаблица Вариант 6 Факультет авт

• Название: Лабораторная работа 4 по дисциплине Алгоритмы и структуры данных Коллекция данных Хештаблица Вариант 6 Факультет авт
• Дата: 29.11.2022
• Размер: 113.44 Kb.
• Имя файла: LR4_Lykov_Sokolova_ASD.docx
• Тип: Лабораторная работа; #819222

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Факультет автоматики и вычислительной техники

Кафедра вычислительной техники

Лабораторная работа №4

по дисциплине «Алгоритмы и структуры данных»

«Коллекция данных – Хеш-таблица»

Вариант №6

Факультет: АВТ

Группа: АВТ-309

Студенты: Лыков А.С. Преподаватель: Романенко Т.А.

Соколова А.В.

Новосибирск

2015

1.Цель работы

• 
  Изучение методов построения таблиц с постоянным временем доступа к элементам.
  
• 
  Освоение технологии реализации таблиц на примере АТД «хеш-таблица».
  

2. Задание

1. 
   Спроектировать, реализовать и провести тестовые испытания АТД «Хеш-таблица» для коллекции, содержащей объекты произвольного типа. Тип объектов задается клиентской программой.
   

АТД «Хеш-таблица» представляет ассоциативное, неупорядоченное множество элементов, доступ к которым выполняется с использованием ключа.

Коллекция проектируется в двух вариантах:

• 
  АТД «Хеш-таблица с цепочками коллизий»;
  
• 
  АТД «Хеш-таблица с открытой адресацией»;
  

Интерфейс АТД «Хеш-таблица» включает следующие операции:

• 
  опрос коэффициента заполнения таблицы;
  
• 
  опрос количества элементов в таблице;
  
• 
  опрос пустоты таблицы;
  
• 
  очистка таблицы;
  
• 
  поиск элемента по ключу;
  
• 
  вставка элемента по ключу;
  
• 
  удаление элемента по ключу;
  

• 
  итератор для доступа к элементам в таблице с операциями:
  

– установка на первый элемент в таблице,

– переход к следующему элементу в таблице,

– проверка окончания просмотра,

– доступ по чтению и записи к данным текущего элемента.

Для тестирования коллекций интерфейс АТД «Хеш-таблица» включает дополнительные операции:

• 
  вывод структуры хеш-таблицы на экран;
  
• 
  опрос числа проб, выполненных операцией.
  

2. 
   Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.
   
3. 
   Получить экспериментальную оценку качества хеш-функции ², усредненную по нескольким экспериментам.
   
4. 
   Выполнить тестирование средней трудоемкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.
   
5. 
   Провести сравнительный анализ теоретических и экспериментальных показателей трудоемкости операций.
   

3.Задание варианта

Тип ключа – строка текста произвольной длины.

Преобразование строки – конкатенация битовых образов символов.

Метод хеширования – мультипликативный.

Метод разрешения коллизий – двойное хеширование.

4. АТД «Хеш-таблица»

ДАННЫЕ:

Параметры:

Количество вставленных элементов count

Структура данных:

Структура данных на базе массива адресных указателей.

ОПЕРАЦИИ:

Конструктор:

Вход: предполагаемое количество хранимых ключей в таблице

Процесс: расчет размера хеш-таблицы и ее создание

Начальные значения: count = 0

Постусловия: count = 0

Конструктор копирования

Вход: ссылка на хеш-таблицу, которую необходимо копировать - t

Предусловия: нет

Процесс: создание копии t

Выход: нет

Постусловия: создана копия t

Опрос количества вставленных элементов

Вход: нет

Предусловия: нет

Процесс: чтение count

Выход: count

Постусловия: нет

Опрос коэффициента заполнения

Вход: нет

Предусловия: нет

Процесс: получение коэффициента заполнения хеш-таблицы

Выход: коэффициент заполнения хеш-таблицы

Постусловия: нет

Проверка на пустоту

Вход: нет

Предусловия: нет

Процесс: проверка размера хеш-таблицы

Выход: true, если таблица пустая – count = 0

false, в противном случае – count ≠ 0

Постусловия: нет

Получение данных по ключу

Вход: ключ искомого элемента k

Предусловия: count ≠ 0, k присутствует в таблице.

Процесс: получение данных по ключу k

Выход: возврат данных, если ключ найден; генерация исключения при невыполнении предусловия

Постусловия: нет

Добавление данных с заданным ключом

Вход: ключ добавляемого элемента k и его данные d

Предусловия: k отсутствует в таблице

Процесс: добавление элемента с ключом k и данными d

Выход: true – элемент включён успешно,

false – при невыполнении предусловия

Постусловия: элемент добавлен в таблицу

Удаление данных с заданным ключом

Вход: ключ удаляемого элемента k

Предусловия: k присутствует в таблице

Процесс: удаление элемента с ключом k

Выход: true – элемент удалён успешно,

false – при невыполнении предусловия

Постусловия: нет

Очистка хеш-таблицы

Вход: нет

Предусловия: нет

Процесс: очистка таблицы, пока count ≠ 0

Выход: нет

Постусловия: хеш-таблица пустая

Деструктор

Процесс: уничтожение таблицы

Постусловия: структура данных корректно уничтожена

5.АТД «Итератор»

Итератор – объект, используемый для доступа к значениям ячеек хеш-таблицы и для перемещения по ней. В данной работе при создании итератор сразу должен привязываться к хеш-таблице.

ДАННЫЕ:

Параметры:

Указатель на хеш-таблицу HashTable* owner

ОПЕРАЦИИ:

Конструктор

Вход: указатель на объект таблицы

Предусловия: если таблица пуста, указатель на элемент таблицы не устанавливается

Процесс: привязка итератора к данной таблице

Выход: нет

Постусловия: созданный итератор привязан к первому элементу данной таблицы, если этот элемент существует

Доступ к данным текущего узла

Вход: нет

Предусловия: итератор установлен

Процесс: возврат адреса данных текущей ячейки

Выход: возврат данных текущей ячейки, генерация исключения при невыполнении предусловия

Постусловия: нет

Опрос состояния итератора

Вход: нет

Предусловия: нет

Процесс: опрос состояния итератора

Выход: true – итератор не установлен,

false – итератор установлен

Постусловия: нет

Установка итератора на следующий элемент

Вход: нет

Предусловия: итератор установлен

Процесс: установка итератора на следующую ячейку

Выход: нет

Постусловия: итератор установлен на следующую ячейку

Установка итератора на первый элемент

Вход: нет

Предусловия: итератор установлен

Процесс: Установка итератора на первую ячейку в таблице

Выход: нет

Постусловия: итератор установлен на первую ячейку в таблице

Установка итератора на последний элемент

Вход: нет

Предусловия: итератор установлен

Процесс: Установка итератора на последнюю ячейку таблицы

Выход: нет

Постусловия: итератор установлен на последнюю ячейку таблицы

6. Шаблонный класс для коллекции «Хеш-таблица»

template //T – тип данных

class HashTable

{

public:

HashTable(int sz); //Конструктор

HashTable(HashTable& t); //Конструктор копирования

HashTable(); //Деструктор

int GetCount(); //Опрос количества вставленных элементов

float GetAlfa(); //Опрос коэффициента насыщения

bool IsEmpty(); //Проверка на пустоту

bool Insert(const char* key, T data); //Вставка элемента по ключу

void Show(); //Вывод на экран

bool Delete(const char* key); //Удаление элемента по ключу

T Search(const char* key); //Получение данных по ключу

void Clear(); //Очистка таблицы

class Iterator

{

public:

Iterator(HashTable owner); //Конструктор итератора

void beg(); //На первый элемент

void end(); //На последний

void next(); //К следующему

bool IsOff(); //Проверка состояния итератора

T& operator*(); //Доступ к данным ячейки

};

};

7. Тестирования хеш-функции и трудоёмкости операций

Табл. 1. Оценка качества распределения

m				Попадает в диапазон
1024	992	1040,3	1056	Да
		1012,2		Да
		1060,9		Нет
		989,5		Нет
		1020,8		Да

=1024,74

Теоретические значения трудоемкости:

Хеш-таблица с цепочками коллизий:

Вставка

Удаление/поиск

Хеш-таблица с открытой адресацией:

Вставка

Удаление/поиск

Табл. 2. Средние трудоёмкости операций вставки, удаления и поиска в хеш-таблице с цепочками коллизий

α	Вставка (Теория)	Удаление/ поиск (Теория)	Вставка	Удаление	Поиск
0,25	1,25	1,1375	1,13	1,1	1
0,5	1,5	1,275	1,366	1,206	1,165
0,75	1,75	1,4125	1,637	1,34	1,3
1	2	1,55	1,89	1,47	1,4
1,25	2,25	1,6875	2,082	1,66	1,5

Табл. 3. Средние трудоёмкости операций вставки, удаления и поиска в хеш-таблице с открытой адресацией

α	Вставка (Теория)	Удаление/ поиск (Теория)	Вставка	Удаление	Поиск
0,25	1,25	1,1375	1,13	1,1	1
0,5	1,5	1,275	1,366	1,206	1,165
0,75	1,75	1,4125	1,637	1,34	1,3
1	2	1,55	1,89	1,47	1,4
1,25	2,25	1,6875	2,082	1,66	1,5

Рис.1 Сравнение результатов операций в хеш-таблице с цепочками.



Рис.2 Сравнение результатов операций в хеш-таблице с открытой адресацией.

Собранные статистические данные о качестве распределения удовлетворяют теоретическим значениям. По итогам пяти экспериментов значение попадает в диапазон 3 раза, а =1024.74

Тестирование трудоемкости операций также адекватно теоретическим значениям. Однако при больших значениях коэффициента заполнения таблицы с открытой адресацией наблюдается значительное отклонение от теории, т. к. в результате зондирования при вставке мы иногда попадаем на занятые ячейки

8. Выводы

В результате проделанной работы был создан абстрактный тип данных — хеш-таблица в двух вариантах: с цепочками коллизий и с открытой адресацией. Работоспособность классов была проверена с помощью созданной программы-меню, дающей доступ ко всем методам созданных классов.

Классы были протестированы на производительность путём нахождения средней трудоёмкости вставки, удаления и поиска элементов при разных коэффициентах заполнения. Также было проведено тестирование хеш-функции.

Тестирование показало адекватность теоретических предположений о трудоёмкости и качестве хеш-функции.

Приложение A

Исходный код программы

//Абстрактный класс

#pragma once

#include

#include

using namespace std;

class HashTableException

{

std::string code;

public:

HashTableException()

{

code = "Исключение";

}

std::string What()

{

return code;

}

};

template

class HashTable

{

protected:

double A;

int cnt;

int size; //размер таблицы

int count; //всего включённых элементов

unsigned concat(const char* key); //конкатенация битовых образов символов

virtual int clp2(int x) = 0; //Ближайшая степень 2;

unsigned Hash(unsigned key); //хеширование

public:

int GetCount() { return count; }

int GetLastViewedCount() { int temp = cnt; cnt = 0; return temp; }

int GetSize() { return size; }

float GetAlfa() { return (float)count / size; }

bool IsEmpty() { return count == 0; }

virtual bool Insert(const char*, T) = 0;

virtual void Show() = 0;

virtual bool Delete(const char*) = 0;

virtual T Search(const char*) = 0;

virtual void Clear() = 0;

public:

class Iterator

{

protected:

int pos;

public:

virtual void beg() = 0;

virtual void end() = 0;

virtual void next() = 0;

virtual bool IsOff() = 0;

virtual T& operator*() = 0;

};

};
template

unsigned HashTable::concat(const char* key)

{

unsigned k = 0, kk = 0;

for (int i = 0; key[i] != NULL; i++)

{

if (i % 6 == 0)

{

k ^= kk;

kk = 0;

}

kk <<= 5;

kk |= (key[i] - 'A' + 1);

}

k ^= kk;

return k;

}
template

unsigned HashTable::Hash(unsigned key) //хэширование ключа

{

//мультипликативный алгоритм

double X = A*key;

X = X - (unsigned)X; //Дробная часть

return (unsigned)(X*size);

}

/************************************************************

* ЦЕПОЧКИ *

* *

************************************************************/

#include "HashTable.h"

#include

#include

#include

using namespace std;

template

class ChainHash : public HashTable

{

struct Pair

{

std::string key;

T value;

bool operator==(Pair t)

{

return (key == t.key);

}

};

class Chain

{

friend class Iterator;

struct Node

{

Pair data;

Node* next;

};

Node* head;

int size;

int cnt;

public:

Chain()

{

head = NULL;

size = cnt = 0;

}

Chain(Chain& c)

{

Node* pc = c.head;

head = new Node;

head->data = pc->data;

head->next = NULL;

pc = pc->next;

Node* p = head;

while (pc)

{

Node* pnew = new Node;

pnew->data = pc->data;

pnew->next = NULL;

p->next = pnew;

pc = pc->next;

p = p->next;

}

size = c.size;

cnt = c.cnt;

}

Chain()

{

Node* p = head;

while (p)

{

Node* prev = p;

p = p->next;

delete prev;

}

size = 0;

cnt = 0;

}

bool Add(Pair data);

bool Delete(Pair data);

Pair Search(Pair data);

int GetLastViewedCount() { int temp = cnt; cnt = 0; return temp; }

int GetSize() { return size; }

void Show();

};

Chain** arr; //массив цепочек коллизий

int clp2(int x)

{

if (x == 0) return 1;

int res = 1;

while (x > 0)

{

res <<= 1;

x >>= 1;

}

return res >>= 1;

}

public:

ChainHash(int _size)

{

A = (sqrt(5.0) - 1.0) / 2.0;

size = clp2(_size/2);

arr = new Chain*[size]; //выделение памяти под списки

for(int i=0;i
{

arr[i]=NULL;

}

count=cnt=0;

}

ChainHash(ChainHash& c)

{

A = (sqrt(5.0) - 1.0) / 2.0;

size = c.size;

count = c.count;

cnt = 0;

arr = new Chain*[size]; //выделение памяти под списки

for (int i = 0; i < size; i++)

{

arr[i] = new Chain(*c.arr[i]);

}

}

ChainHash()

{

for(int i=0;i
{

delete arr[i];//выделенной под цепочки

}

delete []arr;

}

bool Insert(const char*, T);

void Show();

bool Delete(const char*);

T Search(const char*);

void Clear();

class Iterator : public HashTable::Iterator

{

ChainHash* owner;

typename Chain::Node* cur;

public:

Iterator(HashTable* owner)

{

this->owner = (ChainHash*)owner;

cur = NULL;

pos = 0;

}

void beg();

void end();

void next();

bool IsOff();

T& operator*()

{

if (IsOff()) throw HashTableException();

return cur->data.value;

}

};

};

/*--------------------------*/

//Методы класса Chain

//Вставка в начало

template

bool ChainHash::Chain::Add(Pair data)

{

if (!head)

{

cnt++;

head = new Node;

head->data = data;

head->next = NULL;

size++;

return true;

}

Node* p = head;

while (p)

{

cnt++;

if (p->data == data)

return false;

p = p->next;

}

Node* pnew = new Node;

pnew->data = data;

pnew->next = head;

head = pnew;

size++;

return true;

}

//Удаление

template

bool ChainHash::Chain::Delete(Pair data)

{

Node* p = head;

Node* prev;

while (p)

{

cnt++;

if (p->data == data)

break;

prev = p;

p = p->next;

}

if (!p) return false;

if (p == head)

head = head->next;

else

prev->next = p->next;

delete p;

size--;

return true;

}

template

typename ChainHash::Pair ChainHash::Chain::Search(Pair data)

{

Node* p = head;

while (p)

{

cnt++;

if (p->data == data)

return p->data;

p = p->next;

}

throw HashTableException();

}

template

void ChainHash::Chain::Show()

{

Node* p = head;

while (p)

{

cout << (p->data).key << " ";

p = p->next;

}

cout << endl;

}

/***************МЕТОДЫ ТАБЛИЦЫ С ЦЕПОЧКАМИ*************/

template

bool ChainHash::Insert(const char* str, T data)

{

unsigned _key = Hash(concat(str));//хэшируем ключ

if (arr[_key] == NULL)

{

arr[_key] = new Chain();

}

Pair elem = {string(str), data };

bool inserted = arr[_key]->Add(elem);//вставляем

cnt += arr[_key]->GetLastViewedCount();

if (!inserted) return false;

count++;//увеличиваем счётчик

return true;//удача

}

template

T ChainHash::Search(const char *key)

{

unsigned _key = Hash(concat(key));//хэшируем ключ

if(arr[_key]==NULL)

throw HashTableException();

Pair elem;

Pair Found;

elem.key = key;

try

{

Found = arr[_key]->Search(elem);

cnt += arr[_key]->GetLastViewedCount();

}

catch (HashTableException)

{

throw HashTableException();

}

return Found.value;

}

template

bool ChainHash::Delete(const char *key)

{

unsigned _key = Hash(concat(key));//хэшируем ключ

if(arr[_key]==NULL)

return false;//список пуст

bool found = false;

Pair elem = { key, 0 };

bool deleted = arr[_key]->Delete(elem);

cnt += arr[_key]->GetLastViewedCount();

if (!deleted) return false;

if(arr[_key]->GetSize()==0)

{

delete arr[_key];

arr[_key]=NULL;

}

count--;//уменьшаем кол-во элементов

return true;//удача

}

template

void ChainHash::Clear()

{

for (int i = 0; i
{

delete arr[i];//выделенной под списки

arr[i] = NULL;

}

count=0;

}

template

void ChainHash::Show()

{

for(int i=0;i
{

if (arr[i] != NULL)

{

cout << i << " ";

arr[i]->Show();

}

else

std::cout << i << endl;

}

}

template

void ChainHash::Iterator::beg()

{

for (int i = 0; i < owner->size; i++)

{

if (owner->arr[i])

{

cur = owner->arr[i]->head;

pos = i;

return;

}

}

}

template

void ChainHash::Iterator::end()

{

for (int i = owner->size-1; i >= 0; i--)

{

if (owner->arr[i])

{

Chain::Node* p = owner->arr[i]->head;

Chain::Node* prev;

while (p)

{

prev = p;

p = p->next;

}

cur = prev;

pos = i;

return;

}

}

}

template

void ChainHash::Iterator::next()

{

if (!cur) return;

if (cur->next)

{

cur = cur->next;

return;

}

for (int i = pos+1; i < owner->size; i++)

{

if (owner->arr[i])

{

cur = owner->arr[i]->head;

pos = i;

return;

}

}

cur = NULL;

}

template

bool ChainHash::Iterator::IsOff()

{

return (cur == NULL);

}

/************************************************************

* ОТКРЫТАЯ АДРЕСАЦИЯ *

* *

************************************************************/

#include "HashTable.h"

enum Status {FREE, BUSY, DELETED};
template

class OpenHash : public HashTable

{

struct Cell

{

string key;

T data;

Status status;

};

Cell* arr;

unsigned hash1(int key);

unsigned doubleHash(const char* key, unsigned i);

int clp2(int x) {

//Ищет и возвращает ближайшую к x сверху степень двойки

x--;

for (int p = 1; p < 32; p <<= 1) x |= (x >> p);

return ++x;

}

public:

OpenHash(int sz);

OpenHash(OpenHash& t);

OpenHash() { delete[] arr; }

void Show();

void Clear();

bool Insert(const char* key, T data);

bool Delete(const char* key);

T Search(const char* key);

class Iterator : public HashTable::Iterator

{

OpenHash* owner;

Cell* cur;

public:

Iterator(HashTable* owner)

{

this->owner = (OpenHash*)owner;

cur = NULL;

pos = 0;

}

void beg();

void end();

void next();

bool IsOff();

T& operator*()

{

if (IsOff()) throw HashTableException();

return cur->data;

}

};

};
template

OpenHash::OpenHash(int sz)

{

A = (sqrt(5.0) - 1.0) / 2.0;

sz = clp2(2 * sz);

size = sz;

count = cnt = 0;

arr = new Cell[sz];

for (int i = 0; i < size; i++)

arr[i].status = FREE;

}
template

OpenHash::OpenHash(OpenHash& t)

{

if (!t.size) return;

for (int i = 0; i < size; i++)

arr[i] = t.arr[i];

}
template

void OpenHash::Clear()

{

for (int i = 0; i < size; i++)

{

arr[i].status = FREE;

}

count = 0;

}
template

unsigned OpenHash::hash1(int key)

{

double X = A*key;

X = X - (unsigned)X; //Дробная часть

unsigned h = (unsigned)(X*(size-1));

h += !(h % 2);

return h;

}
template

unsigned OpenHash::doubleHash(const char* key, unsigned i)

{

int k = concat(key);

return((Hash(k) + i*hash1(k)) % size);

}
template

bool OpenHash::Insert(const char* key, T data)

{

cnt = 0;

int i = 0;

int pos = -1;

unsigned j = 0;

do

{

cnt++;

j = doubleHash(key, i);

if (arr[j].status == DELETED && pos == -1)

pos = j;

if (arr[j].status == BUSY && arr[j].key == key)

return false;

i++;

}

while (i != size && arr[j].status != FREE);

if (i == size && pos == -1)

return false;

if (pos == -1)

pos = j;

arr[pos].key = key;

arr[pos].data = data;

arr[pos].status = BUSY;

count++;

return true;

}

template

bool OpenHash::Delete(const char* key)

{

cnt = 0;

int i = 0;

unsigned j = 0;

do

{

cnt++;

j = doubleHash(key, i);

if (arr[j].status == BUSY && arr[j].key == key)

{

arr[j].status = DELETED;

count--;

if (count == 0)

for (int i = 0; i < size; i++)

arr[i].status = FREE;

return true;

}

i++;

} while (i != size && arr[j].status != FREE);

return false;

}

template

T OpenHash::Search(const char* key)

{

cnt = 0;

int i = 0;

unsigned j = 0;

do

{

cnt++;

j = doubleHash(key, i);

if (arr[j].status == BUSY && arr[j].key == key)

return arr[j].data;

i++;

} while (i != size && arr[j].status != FREE);

throw HashTableException();

}
template

void OpenHash::Show()

{

for (int i = 0; i < size; i++)

{

if (arr[i].status == FREE)

cout << i << " f" << endl;

if (arr[i].status == BUSY)

cout << i << " " << arr[i].key << endl;

if (arr[i].status == DELETED)

cout << i << " d" << endl;

}

}
template

void OpenHash::Iterator::beg()

{

for (int i = 0; i < owner->size; i++)

{

if (owner->arr[i].status == BUSY)

{

cur = &owner->arr[i];

pos = i;

return;

}

}

cur = NULL;

}

template

void OpenHash::Iterator::end()

{

for (int i = owner->size-1; i >= 0; i--)

{

if (owner->arr[i].status == BUSY)

{

cur = &owner->arr[i];

pos = i;

return;

}

}

}

template

void OpenHash::Iterator::next()

{

if (!cur) return;

for (int i = pos + 1; i < owner->size; i++)

{

if (owner->arr[i].status != FREE && owner->arr[i].status != DELETED)

{

cur = &owner->arr[i];

pos = i;

return;

}

}

cur = NULL;

}

template

bool OpenHash::Iterator::IsOff()

{

return (cur == NULL);

}

Код меню и программы-тестирования

#include "ChainHashTable.h"

#include "OpenHashTable.h"

#include

using namespace std;

namespace TestHash

{

const double A = (1 + sqrt(5.0)) / 2;

unsigned concat(const char* key)

{

unsigned k = 0, kk = 0;

for (int i = 0; key[i] != NULL; i++)

{

if (i % 6 == 0)

{

k ^= kk;

kk = 0;

}

kk <<= 5;

kk |= (key[i] - 'A' + 1);

}

k ^= kk;

return k;

}

unsigned Hash(const char* str, int size)

{

//мультипликативный алгоритм

unsigned key = concat(str);

double X = A*key;

X = X - (unsigned)X; //Дробная часть

return (unsigned)(X*size);

}

char* randomString()

{

int size = 5 + rand() % 16;

char* result = new char[size + 1];

for (int i = 0; i < size; i++)

{

result[i] = (char)('A' + rand() % 26);

}

result[size] = '\0';

return result;

}

void TestHashTable(double alpha, bool chain, int size)

{

srand((unsigned)time(0));

double ins, fnd, del;

ins = fnd = del = 0;

//const int size = 1024;

HashTable* ht;

if (chain)

ht = new ChainHash(size);

else

ht = new OpenHash(size);

int count = (int)(alpha*ht->GetSize());

string* arr = new string[count];

char* str = NULL;

for (int i = 0; i < count; i++)

{

str = randomString();

ht->Insert(str, 1);

arr[i] = str;

delete[] str;

}

ht->GetLastViewedCount();

cout << "Размер до " << ht->GetCount() << endl;

for (int i = 0; i < count / 2; i++)

{

if (i%10 != 0)

{

int index = rand() % count;

ht->Delete(arr[index].c_str());

del += ht->GetLastViewedCount();

str = randomString();

ht->Insert(str, 1);

ins += ht->GetLastViewedCount();

arr[index] = str;

index = rand() % count;

ht->Search(arr[index].c_str());

fnd += ht->GetLastViewedCount();

delete[] str;

}

else

{

ht->Delete(randomString());

del += ht->GetLastViewedCount();

str = randomString();

int index = rand() % count;

ht->Insert(arr[index].c_str(), 1);

ins += ht->GetLastViewedCount();

try {

ht->Search(randomString());}

catch (HashTableException)

{fnd += ht->GetLastViewedCount();}

fnd += ht->GetLastViewedCount();

delete[] str;

}

}

delete[] arr;

cout << "Размер после " << ht->GetCount() << endl;

if (chain)

cout << "Вставка T " << 1+alpha << endl;

else

cout << "Вставка T " << 0.1*(-log(1-alpha)/alpha)+0.9*(1/(1-alpha)) << endl;

cout << "Вставка " << ins / (count / 2) << endl;

if (chain)

cout << "Удаление T " << 0.1*(1+alpha)+0.9*(1+alpha/2) << endl;

else

cout << "Удаление T " << 0.9*(-log(1-alpha)/alpha)+0.1*(1/(1-alpha)) << endl;

cout << "Удаление " << del / (count / 2) << endl;

if (chain)

cout << "Поиск T " << 0.1*(1+alpha)+0.9*(1+alpha/2) << endl;

else

cout << "Поиск T " << 0.9*(-log(1-alpha)/alpha)+0.1*(1/(1-alpha)) << endl;

cout << "Поиск " << fnd / (count / 2) << endl;

delete ht;

}

void TestHashFunc(int size)

{

srand((unsigned)time(0));

int* arr = new int[size];

for (int i = 0; i < size; i++)

arr[i] = 0;

char* str = NULL;

for (int i = 0; i < 20 * size; i++)

{

str = randomString();

unsigned k = Hash(str, size);

arr[k]++;

delete[] str;

}

double sum = 0;

//СКО

for (int i = 0; i < size; i++)

{

sum += (arr[i] - 20)*(arr[i] - 20);

}

sum /= 20.0;

cout << "m-sqrt(m) " << (double)(size - sqrt((double)size)) << endl;

cout << sum << endl;

cout << "m+sqrt(m) " << (double)(size + sqrt((double)size)) << endl;

delete[] arr;

}

}

void ShowMenu(bool iter = 0)

{

if (iter == 0)

{

cout << "1. Показать таблицу" << endl;

cout << "2. Вставка элемента в таблицу" << endl;

cout << "3. Удаление по ключу" << endl;

cout << "4. Поиск данных по ключу" << endl;

cout << "5. Очистить таблицу" << endl;

cout << "6. Опрос количества элементов в таблице" << endl;

cout << "7. Коэффициент заполения таблицы" << endl;

cout << "8. Проверка на пустоту" << endl;

cout << "9. Итератор" << endl;

cout << "10. Показать меню" << endl;

cout << "11. Опрос размера таблицы" << endl;

cout << "12. Тестирование хеш-функции" << endl;

cout << "13. Тестирование трудоемкости операций" << endl;

cout << "14. Число зондирований" << endl;

}

else

{

cout << "1. На первый элемент" << endl;

cout << "2. На последний" << endl;

cout << "3. Проверка состояния" << endl;

cout << "4. К следующему" << endl;

cout << "5. Прочитать данные" << endl;

cout << "6. Записать данные" << endl;
}

}

void main()

{

setlocale(LC_ALL, "Russian");

HashTable* ht;

bool chainHash;

int htSize;

cout << "Хеш-таблица с цепочками коллизий - 1, с открытой адресацией - 0:" << endl;

cin >> chainHash;

cout << "Размерностью:" << endl;

cin >> htSize;

if (chainHash)

ht = new ChainHash(htSize);

else

ht = new OpenHash(htSize);

bool exit = 1;

int k;

bool Show = 1;

while (exit)

{

if (Show)

{

ShowMenu();

Show = 0;

}

cin >> k;

switch (k)

{

case 1:

{

ht->Show();

break;

}

case 2:

{

string str;

int data;

cout << "Введите ключ: " << endl;

cin >> str;

cout << "Введите данные: " << endl;

cin >> data;

cout << ht->Insert(str.c_str(), data) << endl;

break;

}

case 3:

{

string str;

cout << "Введите ключ: " << endl;

cin >> str;

cout << ht->Delete(str.c_str()) << endl;

break;

}

case 4:

{

string str;

cout << "Введите ключ: " << endl;

cin >> str;

try

{

cout << ht->Search(str.c_str()) << endl;

}

catch (HashTableException e)

{

cout << e.What() << endl;

}

break;

}

case 5:

{

ht->Clear();

break;

}

case 6:

{

cout << ht->GetCount() << endl;

break;

}

case 7:

{

cout << ht->GetAlfa() << endl;

break;

}

case 8:

{

cout << ht->IsEmpty() << endl;

break;

}

case 9:

{

HashTable::Iterator* it;

if (chainHash)

it = new ChainHash::Iterator(ht);

else

it = new OpenHash::Iterator(ht);

bool exit = 1;

int k;

bool Show = 1;

while (exit)

{

if (Show)

{

ShowMenu(1);

Show = 0;

}

cin >> k;

switch (k)

{

case 1:

{

it->beg();

break;

}

case 2:

{

it->end();

break;

}

case 3:

{

cout << it->IsOff() << endl;

break;

}

case 4:

{

it->next();

break;

}

case 5:

{

try

{

cout << **it << endl;

}

catch (HashTableException e)

{

cout << e.What() << endl;

}

break;

}

case 6:

{

cout << "Новые данные:" << endl;

int data;

cin >> data;

try

{

**it = data;

}

catch (HashTableException e)

{

cout << e.What() << endl;

}

break;

}

default:

exit = 0;

break;

}

}

delete it;

break;

}

case 10:

{

Show = 1;

break;

}

case 11:

{

cout << ht->GetSize() << endl;

break;

}

case 12:

{

int size;

cout << "Введите размер таблицы " << endl;

cin >> size;

TestHash::TestHashFunc(size);

break;

}

case 13:

{

double alpha;

cout << "Введите коэффициент заполнения " << endl;

cin >> alpha;

TestHash::TestHashTable(alpha, chainHash, htSize);

break;

}

case 14:

{

cout << ht->GetLastViewedCount() << endl;

break;

}

default:

exit = 0;

break;

}

}

delete ht;

}