2018-02-13
294Лабораторная работа №1
По «Алгоритмам и структурам данных».
Вариант 1
Выполнили:
Займак Д.В.
Ведмеденко Д.С.
Коляда И.С.
Группа: ЗФ-322
Проверила: Романенко Т.А.
Новосибирск
2016
ЗАДАНИЕ
1. Спроектировать, реализовать и провести тестовые испытания АТД «Хеш-таблица» для коллекции, содержащей объекты произвольного типа. Тип объектов задаётся клиентской программой.
АТД «Хеш-таблица» представляет ассоциативное, неупорядоченное множество элементов, доступ к которым выполняется с использованием ключа.
Коллекция проектируется в одном из двух вариантов:
· АТД «Хеш-таблица с цепочками коллизий»,
· АТД «Хеш-таблица с открытой адресацией»,
Интерфейс АТД «Хеш-таблица» включает следующие операции:
· опрос размера таблицы,
· опрос количества элементов в таблице,
· опрос пустоты таблицы,
· очистка таблицы,
· поиск элемента по ключу,
· вставка элемента по ключу,
· удаление элемента по ключу.
· итератор для доступа к элементам в таблице с операциями:
|
|
|
- установка на первый элемент в таблице,
- переход к следующему элементу в таблице,
- проверка окончания просмотра,
- доступ по чтению и записи к данным текущего элемента.
Для тестирования коллекций интерфейс АТД «Хеш-таблица» включает дополнительные операции:
· вывод структуры хеш-таблицы на экран,
· опрос числа проб, выполненных операцией.
2. Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.
3. Получить экспериментальную оценку качества хеш-функции c 2, усреднённую по нескольким экспериментам.
4. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий», и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.
5. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.
6. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:
1) пункты 1 – 5 (см. раздел 2.2),
6) описание методики получения экспериментальной оценки c 2 и полученная оценка c 2, усреднённая по нескольким экспериментам.
7) описание методики тестирования трудоёмкости операций,
8) таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией»,
9) сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,
|
|
|
10) выводы,
11) список использованной литературы,
12) приложение с текстами программ:
- полное определение классов и текстов методов класса,
- текст программы получения оценки c 2,
текст программы тестирования трудоёмкости операций АТД.
Вариант 1.
Форма представления: хеш – таблица с цепочками коллизий
Тип ключа - вещественное число на интервале [-10 000.00, +10 000.00].
Метод хеширования - мультипликативный.
ФОРМАТ АТД
АТД «Хэш-таблица с цепочками коллизий »
Класс реализует хэш-таблицу с цепочками коллизий. Возможны произвольные размеры таблицы. Таблица может меняться: возможна вставка новых элементов и удаление существующих. Реализуется операция поиска в таблице. Имеется итератор для перемещения по таблице.
Данные:
Параметры:
Размер хэш-таблицы
Структура хранения коллекции:
Статический массив элементов, содержащих ключ, значение и указатель на следующий элемент.
ОПЕРАЦИИ:
Конструктор:
Вход: количество элементов
Предусловия: не создана хэш таблица
Процесс: создание хэш-таблицы
Выход: нет
Постусловия: создана хэш таблица
Деструктор:
Вход: нет
Предусловия: создана хэш таблица
Процесс: удаление хэш таблицы
Выход: нет
Постусловия: создана хэш таблица
опрос размера таблицы:
Вход: нет
Предусловия: нет
Процесс: возвращение размера таблицы
Выход: размер таблицы
Постусловия: нет
опрос количества элементов в таблице:
Вход: нет
Предусловия: нет
Процесс: возвращение количества элементов
Выход: количество элементов
Постусловия: нет
опрос пустоты таблицы:
Вход: нет
Предусловия: нет
Процесс: проверка заполненности таблицы
Выход: Истина, если таблица заполнена, иначе Ложь.
Постусловия: нет
очистка таблицы:
Вход: нет
Предусловия: нет
Процесс: удаление всех элементов
Выход: нет
Постусловия: таблица пуста
поиск элемента по ключу:
Вход: ключ элемента
Предусловия: элемент существует
Процесс: поиск элемента
Выход: значение элемента.
Постусловия: исключение при невыполнении предусловия
вставка элемента по ключу:
Вход: ключ элемента
Предусловия: нет
Процесс: поиск элемента
Выход: Истина, если элемент вставлен, иначе Ложь.
Постусловия: элемент добавлен
удаление элемента по ключу:
Вход: ключ элемента
Предусловия: элемент существует
Процесс: поиск элемента, удаление.
Выход: нет.
Постусловия: элемент удален. Исключение, если предусловие не выполнено.
КОНЕЦ АТД
Описание класса
class HashTab {
// Элемент списка, который содержится в хэш-таблице
struct Element {
K key; // Ключ
V value; // Значение
Element *next; // Следующий элемент списка
};
// Массив
Element **array;
// Размер хэш-таблицы
int capacity;
// Количество элементов в таблице
int size;
// Функция хэширования
int hash(K key);
int counter;
// Поиск элемента по ключу
Element *find(K key);
int closest_pow2 (int x);
public:
// Конструктор
HashTab(int capacity = 8);
// Деструктор
~HashTab();
// Добавляет элемент
bool insert(K key, V value);
// Удаляет элемент
bool remove(K key);
// Возвращает значение
V& get_value(K key);
// Возвращает количество элементов
int get_size();
// Возвращает размер хэш-таблицы
int get_capacity();
// Определяет пуста ли хэш-таблица
bool is_empty();
// Очищает хэш-таблицу
void clear();
int get_counter();
//Класс итератора
class Iterator {
HashTab<K, V> *table;
bool off;
int index;
Element *pointer;
public:
Iterator(HashTab<K, V> &table);
V& operator*();
bool beg();
bool is_off();
bool next();
K get_key();
};
// Вывод хэш таблицы на экран
void print();
};
Вывод
В ходе выполнения лабораторной работы была изучена теория и алгоритмы работы с хеш-таблицами. Был разработан алгоритм получения хеш-ключа элемента, выделения памяти под хеш-таблицу, поиск, вставка и удаление элементов из хеш-таблицы. Был получен практический опыт работы с шаблонами и классами.
|
|
|
Приложение А
Исходный код основной программы
#include "HashTab.h"
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;
void test_rand(int, double);
int main(int argc, char *argv[]) {
setlocale (0, "Rus");
//Переменные
int n = 3, value;
double key;
//Строки
const char wait_message[] = "Для продолжения нажмите любую клавишу...\n";
const char iterator_out_error[] = "Ошибка: итератор за пределами коллекции!\n";
const char key_not_found[]= "Ошибка: введённый ключ отсутствует в коллекции!\n";
HashTab<double, int>::Iterator *iterator;
// Очистка экрана
system("cls");
while(n!= 2) {
cout << "Итератор:\n"
"1. Тестирование\n"
"2. Меню\n"
"0. Выход\n";
cin >> n;
switch(n) {
int sz;
double a;
case 1:
cout << "Введите кол-во элементов:";
cin >> sz;
cout << "Введите альфу:";
cin >> a;
test_rand(sz, a);
break;
case 0: return 0;
}
}
system("cls");
//Запрос размера
cout << "Количество элементов: ";
cin >> n;
system("cls");
//Создаём таблицу
HashTab<double, int> *tab = new HashTab<double, int>(n);
//Основной цикл меню
bool iterator_created = false;
while(true) {
//system("cls");
//Отобразить коллекцию
cout << "----------------------Хэш таблица--------------------------\n";
tab->print();
//Отобразить итератор
if(iterator_created) {
cout << "----------------------Итератор-------------------------\n";
if(!iterator->is_off())
cout << "\tКлюч: " << iterator->get_key() << "\tЗначение: " << **iterator << '\n';
else
cout << "\tКлюч: -\tЗначение: -\n";
}
cout << "*************************************************\n";
// Меню
if(iterator_created) {
cout << "Итератор:\n"
"1. Сбросить\n"
"2. Следующий элемент\n"
"3. Вывести значение\n"
"4. Изменить значение\n"
|
|
|
"5. Состояние итератора\n"
"6. Удалить итератор\n";
} else {
cout << "Действия:\n"
"1. Вставить значение\n"
"2. Удалить значение\n"
"3. Вывести значение\n"
"4. Изменить значение\n"
"5. Количество элементов\n"
"6. Очистить таблицу\n"
"7. Проверить на пустоту\n"
"8. Создать итератор\n"
"9. Размер таблицы\n";
}
cout << "0. Выход\n*************************************************\n";
//Выбор пункта и проверка на корректность
cin >> n;
if(n < 0 || (!iterator_created && n > 11) || (iterator_created && n > 9))
continue;
//Код пунктов меню
switch(n) {
case 1: //Вставка | Сброс итератора
if(iterator_created) {
iterator->beg();
} else {
cout << "Введите ключ и значение: ";
cin >> key >> value;
if(tab->insert(key, value) == 0) {
cout << "Ошибка: коллекция уже содержит идентичный ключ!\n" << wait_message;
_getch();
}
}
break;
case 2: //Удаление по ключу | Итератор - следующее значение
if(iterator_created) {
if(!iterator->next()) {
cout << iterator_out_error << wait_message;
_getch();
}
} else {
cout << "Введите ключ удаляемого элемента: ";
cin >> key;
if(tab->remove(key) == 0) {
cout << key_not_found << wait_message;
_getch();
}
}
break;
case 3: //Получить значение
if(iterator_created) {
try {
cout << "Значение = " << **iterator << '\n';
} catch(exception) {
cout << iterator_out_error;
}
} else {
cout << "Введите ключ элемента: ";
cin >> key;
try {
cout << tab->get_value(key) << '\n' << wait_message;
}
catch(exception) {
cout << key_not_found << wait_message;
}
_getch();
}
break;
case 4: //Изменить значение
if(iterator_created) {
try {
cout << "Текущее значение = " << **iterator << '\n';
cout << "Изменить на ";
cin >> value;
**iterator = value;
} catch(exception) {
cout << iterator_out_error << wait_message;
_getch();
}
} else {
cout << "Введите ключ элемента и новое значение: ";
cin >> key >> value;
try {
tab->get_value(key) = value;
}
catch(exception) {
cout << key_not_found << wait_message;
_getch();
}
}
break;
case 5: //Число элементов | Состояние итератора
if(iterator_created) {
if(iterator->is_off())
cout << "Итератор вне коллекции\n";
else
cout << "Итератор внутри коллекции\n";
cout << wait_message;
_getch();
} else {
cout << "Число элементов в таблице: " << tab->get_size() << '\n' << wait_message;
_getch();
}
break;
case 6: //Очистка | Удалить итератор
if(iterator_created) {
if(iterator) {
delete iterator;
}
iterator_created = 0;
} else {
tab->clear();
}
break;
case 7: //Проверка на пустоту
if(tab->is_empty()) {
cout << "Коллекция пуста\n";
} else {
cout << "Коллекция не пуста\n";
}
cout << wait_message;
_getch();
break;
case 8: //Создать итератор
iterator_created = 1;
iterator = new HashTab<double, int>::Iterator(*tab);
break;
case 9: //Размер таблицы
if(!iterator_created) {
cout << "Размер таблицы:" << tab->get_capacity() << endl;
}
break;
case 0: //Выход
return 0;
break;
}
}
return 0;
}
double lrand(){
return ((float) rand() * (float) rand()) / 100.0;
}
void test_rand(int sz, double a){
srand(time(NULL));
HashTab<double, int> * tab = new HashTab<double, int>(sz);
cout << "capacity: " << tab->get_capacity() << endl;
int n = floor(tab->get_capacity()*a);
double* m=new double[n];
for(int i=0; i<n; i++)
{
m[i]=lrand();
tab->insert(m[i],1);
}
double I=0;
double D=0;
double S=0;
double idx;
for(int i=0;i<n/2;i++)
if(i%10==0){
idx = lrand();
tab->remove(idx);
D+=tab->get_counter();
tab->insert(m[rand()%n],1);
I+=tab->get_counter();
try{
tab->get_value(lrand());
S+=tab->get_counter();
}catch(exception& e){S+=tab->get_counter();}
} else {
int ind=rand()%n;
idx = m[ind];
try{
tab->get_value(rand()%n);
S+=tab->get_counter();
}catch(exception& e){
S+=tab->get_counter();
}
tab->remove(idx);
D+=tab->get_counter();
double key=lrand();
tab->insert(key,1);
I+=tab->get_counter();
m[ind]=key;
}
cout<<"items count: "<<tab->get_size()<<endl;
cout<<"Count insert: " << I/(n/2) <<endl;
cout<<"Count delete: " << D/(n/2) <<endl;
cout<<"Count search: " << S/(n/2) <<endl;
delete[] m;
}
Приложение Б
Исходный код класса
#ifndef HASHTAB_H
#define HASHTAB_H
#include <iostream>
#include <cmath>
using namespace std;
template <class K, class V>
class HashTab {
// Элемент списка, который содержится в хэш-таблице
struct Element {
K key; // Ключ
V value; // Значение
Element *next; // Следующий элемент списка
};
// Массив
Element **array;
// Размер хэш-таблицы
int capacity;
// Количество элементов в таблице
int size;
// Функция хэширования
int hash(K key);
int counter;
// Поиск элемента по ключу
Element *find(K key);
int closest_pow2 (int x);
public:
// Конструктор
HashTab(int capacity = 8);
// Деструктор
~HashTab();
// Добавляет элемент
bool insert(K key, V value);
// Удаляет элемент
bool remove(K key);
// Возвращает значение
V& get_value(K key);
// Возвращает количество элементов
int get_size();
// Возвращает размер хэш-таблицы
int get_capacity();
// Определяет пуста ли хэш-таблица
bool is_empty();
// Очищает хэш-таблицу
void clear();
int get_counter();
//Класс итератора
class Iterator {
HashTab<K, V> *table;
bool off;
int index;
Element *pointer;
public:
Iterator(HashTab<K, V> &table);
V& operator*();
bool beg();
bool is_off();
bool next();
K get_key();
};
// Вывод хэш таблицы на экран
void print();
};
int round (double x) {
return (int) floor(x + 0.5);
}
template <class K, class V>
int HashTab<K, V>::get_counter(){
return counter;
}
template <class K, class V>
int HashTab<K, V>::hash(K key)
{
double A = (sqrt(5.0) - 1) / 2;
double tmp;
double fract_part = modf(round(((key * 100)) + 1000000) * A, &tmp);
return (int) floor(capacity * fract_part);
}
template <class K, class V>
typename HashTab<K, V>::Element* HashTab<K, V>::find(K key)
{
counter = 1;
Element *cur = array[hash(key)];
while(cur) {
++counter;
if(cur->key == key) {
return cur;
}
cur = cur->next;
}
return NULL;
}
template <class K, class V>
int HashTab<K, V>::closest_pow2(int x)
{
int power = 1;
while((power) <= x)
power = power << 1;
return power >> 1;
}
template <class K, class V>
HashTab<K, V>::HashTab(int capacity)
{
this->capacity = closest_pow2(capacity / 2);
if(this->capacity == 0)
this->capacity = 1;
this->size = 0;
//Создаём массив элементов
array = new Element* [this->capacity];
// Обнуляем массив
memset(array, NULL, sizeof (Element *)* this->capacity);
}
template <class K, class V>
HashTab<K, V>::~HashTab()
{
clear();
delete []array;
}
template <class K, class V>
bool HashTab<K, V>::insert(K key, V value)
{
if (!find(key)) {
int index = hash(key);
Element *new_element = new Element();
new_element->key = key;
new_element->value = value;
new_element->next = array[index];
array[index] = new_element;
++size;
return true;
}
return false;
}
template <class K, class V>
bool HashTab<K, V>::remove(K key)
{
int index = hash(key);
counter = 1;
// Ищем элемент, который надо удалить
Element *prev = 0;
Element *cur = array[index];
while(cur!= 0) {
++counter;
if(cur->key == key)
break;
prev = cur;
cur = cur->next;
}
if(!cur) {
return false;
}
if(array[index] == cur) {
//Удаляемый элемент первый в списке
array[index] = cur->next;
} else {
//Удаляемый не первый элемент
prev->next = cur->next;
}
delete cur;
--size;
return true;
}
template <class K, class V>
V& HashTab<K, V>::get_value(K key)
{
Element *ptr = find(key);
if (ptr) {
return ptr->value;
} else {
throw exception("There is no such element!");
}
}
template <class K, class V>
int HashTab<K, V>::get_size()
{
return size;
}
template <class K, class V>
int HashTab<K, V>::get_capacity()
{
return capacity;
}
template <class K, class V>
bool HashTab<K, V>::is_empty()
{
return size == 0;
}
template <class K, class V>
void HashTab<K, V>::clear()
{
for(int i = 0; i < capacity; ++i) {
Element *cur = array[i];
while(cur) {
Element *next = cur->next;
delete cur;
cur = next;
}
array[i] = NULL;
}
size = NULL;
}
template <class K, class V>
void HashTab<K, V>::print()
{
Element *cur;
for(int i = 0; i < capacity; ++i) {
cout << i << ". ";
cur = array[i];
while(cur) {
cout << cur->key << " ";
cur = cur->next;
}
cout << '\n';
}
}
// Итератор
template <class K, class V>
HashTab<K, V>::Iterator::Iterator(HashTab<K, V> &table)
{
this->table = &table;
beg();
}
template <class K, class V>
V& HashTab<K, V>::Iterator::operator*()
{
if(off) {
throw exception("The iterator is off!");
}
return pointer->value;
}
template <class K, class V>
bool HashTab<K, V>::Iterator::beg()
{
//Если в таблице нет элементов - указатель не установлен
if(table->size == 0) {
off = true;
return false;
}
//Ищем первый элемент
off = false;
index = 0;
while(table->array[index] == 0) {
++index;
}
pointer = table->array[index];
return true;
}
template <class K, class V>
bool HashTab<K, V>::Iterator::is_off()
{
return off;
}
template <class K, class V>
bool HashTab<K, V>::Iterator::next()
{
//Проверка на нахождение в коллекции
if(off) {
return false;
}
//Ищем следующий элемент в списке
if(pointer->next) {
pointer = pointer->next;
return true;
}
//Ищем следующий список
++index;
while(index!= table->capacity && table->array[index] == 0) {
++index;
}
//Вышли за пределы
if(index == table->capacity) {
off = true;
return true;
}
//Список найден
pointer = table->array[index];
return true;
}
template <class K, class V>
K HashTab<K, V>::Iterator::get_key()
{
if(off) {
throw exception("The iterator is off!");
}
return pointer->key;
}
#endif // HASHTAB_H
