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

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

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

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

· АТД «Хеш-таблица с цепочками коллизий»,

· АТД «Хеш-таблица с открытой адресацией»,

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

· опрос размера таблицы,

· опрос количества элементов в таблице,

· опрос пустоты таблицы,

· очистка таблицы,

· поиск элемента по ключу,

· вставка элемента по ключу,

· удаление элемента по ключу.

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

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

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

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

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

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

· вывод структуры хеш-таблицы на экран,

· опрос числа проб, выполненных операцией.

2. Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.

3. Получить экспериментальную оценку качества хеш-функции c ², усреднённую по нескольким экспериментам.

4. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий», и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.

5. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.

6. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1) пункты 1 – 5 (см. раздел 2.2),

6) описание методики получения экспериментальной оценки c ² и полученная оценка c ², усреднённая по нескольким экспериментам.

7) описание методики тестирования трудоёмкости операций,

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

9) сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,

10) выводы,

11) список использованной литературы,

12) приложение с текстами программ:

- полное определение классов и текстов методов класса,

- текст программы получения оценки c ²,

- текст программы тестирования трудоёмкости операций АТД.

6.4.1. Варианты заданий:

1.

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

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

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

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

2.

Тип ключа - вещественное число на интервале [-10 000.00, +10 000.00].

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

Метод разрешения коллизий - квадратичный.

3.

Тип ключа - целое число на интервале [0, [phone]].

Метод хеширования – выбор цифр.

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

4.

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

Метод преобразования числа – формирование значения числа из кодов символов по схеме Горнера.

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

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

5.

Тип ключа - вещественное число на интервале [100 000.00, +150 000.00].

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

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

6.

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

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

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

Метод разрешения коллизий - квадратичный.

7.

Тип ключа - вещественное число на интервале [-5 000.000, +5 000.000].

Метод хеширования - свёртка.

Метод разрешения коллизий - квадратичный.

8.

Тип ключа – 12-значное натуральное число.

Метод хеширования - свёртка, комбинированная с выбором цифр.

Метод разрешения коллизий - линейный.

Дата добавления: 2015-11-04