Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Методические указания к выполнению задания | Структуры списков | Задание к лабораторной работе | Методические указания к выполнению задания | Структуры BST - деревьев | Задание к лабораторной работе | Структуры сбалансированных деревьев | Задание к лабораторной работе | Методические указания к выполнению задания | Функции хеширования |


Читайте также:
  1. II. Задание практического характера.
  2. Анализ вредных производственных факторов при работе с ПЭВМ
  3. В работе над эстрадно-цирковым номером «оправдание» относится к ситуации, когда ищется сюжет, действие, образ, оправдывающие трюки.
  4. В работе экзаменуемый может использовать следующие типы аргументов.
  5. Внимание! Вам предлагают задание "Возращение дочери могильщика".
  6. Внимание! Вам предлагают задание "Жестокое милосердие".
  7. Внимание! Вам предлагают задание "Знания Некромонгов".

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,

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

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

1.

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

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

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

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

2.

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

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

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

3.

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

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

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

4.

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

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

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

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

5.

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

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

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

6.

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

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

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

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

 

7.

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

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

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

8.

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

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

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


Дата добавления: 2015-11-04; просмотров: 142 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Разрешение коллизий и структуры хеш-таблиц| Методические указания к выполнению задания

mybiblioteka.su - 2015-2024 год. (0.008 сек.)