отчет лабораторная АиСД


Министерство образования и науки Российской Федерации
Новосибирский государственный технический университет
Заочное отделение института дистанционного обучения
Лабораторная работа №1
по дисциплине «Алгоритмы и структуры данных»
Коллекция данных – хеш-таблица
Вариант №6
Факультет: ЗФ
Группа: ЗФ-322
Студенты: Бондарев Н.А.Преподаватель: Романенко Т.А.
Шамшеев С.А.
Новосибирск
2016
1. Цели работы: Изучение методов построения таблиц с постоянным временем доступа к элементам. Освоение технологии реализации таблиц на примере АТД «Хеш – таблица».
2. Задание к лабораторной работе:
Спроектировать, реализовать и провести тестовые испытания АТД «Хеш-таблица» для коллекции, содержащей объекты произвольного типа. Тип объектов задаётся клиентской программой.
АТД «Хеш-таблица» представляет ассоциативное, неупорядоченное множество элементов, доступ к которым выполняется с использованием ключа.
Коллекция проектируется в одном из двух вариантов:
АТД «Хеш-таблица с цепочками коллизий»,
АТД «Хеш-таблица с открытой адресацией»,
Интерфейс АТД «Хеш-таблица» включает следующие операции:
опрос размера таблицы,
опрос количества элементов в таблице,
опрос пустоты таблицы,
очистка таблицы,
поиск элемента по ключу,
вставка элемента по ключу,
удаление элемента по ключу.
итератор для доступа к элементам в таблице с операциями:
установка на первый элемент в таблице,
переход к следующему элементу в таблице,
проверка окончания просмотра,
доступ по чтению и записи к данным текущего элемента.
Для тестирования коллекций интерфейс АТД «Хеш-таблица» включает дополнительные операции:
вывод структуры хеш-таблицы на экран,
опрос числа проб, выполненных операцией.
Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.
Получить экспериментальную оценку качества хеш-функции 2, усреднённую по нескольким экспериментам.
Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий», и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.
Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.
Составить отчёт по лабораторной работе.
3. Задание варианта:
Форма представления: хеш – таблица с цепочками коллизий
Тип ключа - вещественное число на интервале [-5 000.000 , +5 000.000].
Метод хеширования - свёртка.
4. АТД Хеш-таблица с цепочками коллизий
ДАННЫЕ:
Параметры:
Текущий размер списка m
Структура данных:
Структура данных - таблица указателей Node **ar
ОПЕРАЦИИ:
Конструктор:
Вход: размер таблицы m
Процесс: создание объекта списка
Начальные значения: NULL для всех элементов массива
Постусловия: нет
Чтение значений с заданным номером-хэш и ключем в списке
Вход: номер в таблице hash и key искомого элемента,
Предусловия 0 < count
Процесс: поиск в списке элемента key
Выход: возврат значения data, если объект найден
Постусловия: нет
Изменение значения с заданным номером в списке
Вход: 1. номер элемента, требующего изменения - hash и key
2. новое значение объекта data
Предусловия: нет
Процесс: проход по списку и замена элемента
Выход: значение true, если элемент изменен успешно и false в противном случае
Постусловия: нет
Включение нового элемента
Вход: значение элемента T, К
Предусловия: проверка наличия такого же элемента в строке hash
Процесс: Включение элемента со значением T в начало списка
Выход: значение true, если элемент добавлен и false в противном случае
Постусловия: нет
Удаление заданного значения из списка
Вход: значение элемента кеу
Предусловия: 0 < count
Процесс: найти нужную ссылку по hash, пробежать по списку
Выход: значение true, если элемент удален успешно и false в противном случае
Постусловия: нет
Деструктор
Процесс: уничтожение списка
Постусловия: структура данных корректно уничтожена
5.АТД «Итератор»
Итератор – объект, используемый для доступа к значениям элемента списка и для перемещения по списку. В данной работе при создании итератор сразу должен привязываться к списку. Итератор реализует последовательный доступ к элементам списка.
ДАННЫЕ:
Параметры:
Указатель на элемент списка Node* cur
ОПЕРАЦИИ:
Конструктор
Вход: указатель на объект списка
Предусловия: если список пуст, указатель на элемент списка cur не устанавливается
Процесс: привязка итератора к данному списку
Выход: нет
Постусловия: созданный итератор привязан к первому элементу данного списка, если этот элемент существует
Доступ к значению текущего элемента
Вход: нет
Предусловия: нет
Процесс: возврат адреса содержимого текущего элемента
Выход: возврат значения текущего элемента
Постусловия: нет
Установка итератора на следующий элемент списка
Вход: нет
Предусловия: нет
Процесс: Установка итератора на следующий элемент списка
Выход: нет
Постусловия: нет
Установка итератора на первый элемент списка
Вход: нет
Предусловия: нет
Процесс: Установка итератора на первый элемент списка
Выход: нет
Постусловия: нет
Просмотр элемента списка
Вход: нет
Предусловия: итератор установлен на элемент списка
Процесс: просмотр элемента списка
Выход: нет
Постусловия: нет
Изменение элемента списка
Вход: новое значение элемента списка
Предусловия: итератор установлен на элемент списка
Процесс: Изменение элемента списка
Выход: нет
Постусловия: нет

Шаблонный класс для коллекции «Список»:Таблица 1. Описание базового шаблонного класса, реализующего коллекцию данных
Название класса template <class K, class T> class Collection
Public (доступные поля класса) Сlass Iterator
Конструкторы и деструктор для класса
(доступные) Collection(int m )
~Collection ();
Public (доступные методы класса) bool insertdata(int hash, K key, T data);
bool deletedata(int hash, K key);
T& getdata(int hash, K key);
friend ostream & operator<<(ostream &out, const Collection &a)
Таблица 2. Описание вложенной структуры, реализующей элемент коллекции данных
Название класса class Node
Public (доступные поля класса) K key;
T data;
*next;
Node(K key, T data)
Таблица 3. Описание вложенного класса, реализующего доступ к элементам
Название класса Сlass Iterator
Private (скрытые поля класса) Node* cur;
Collection *pt;

Конструкторы и деструктор для класса
(доступные) Iterator (Collection *pt)
Iterator ();
Public (доступные методы класса) void beg ();
void next ();
T& operator*();
bool is_off();
8. Выводы
В результате проделанной работы был создан абстрактный тип данных — хэш таблица с односвязным списком – цепочками коализий. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем методам созданного класса.


Приложенные файлы

  • docx 8818401
    Размер файла: 23 kB Загрузок: 1

Добавить комментарий