|
Читайте также: |
1. Коллекции «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» разрабатываются, как отдельные шаблонные классы-контейнеры. Шаблонный класс«Хеш-таблица с цепочками коллизий» для организации цепочек использует внешний шаблонный класс «Список».
2. Параметрами шаблона являются тип ключа, тип данных.
3. Размер хеш-таблицы вычисляется конструктором коллекции в зависимости от заданного количества элементов с учётом типа хеш-таблицы, метода хеширования, указанного в варианте задания, и рекомендуемой величины α.
4. Для реализации операций АТД, рекомендуется использовать алгоритмы, приведённые в приложении 5.
5. Для тестирования разработанного класса – контейнера разрабатываются две программы - программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
6. Тестирование операций через меню выполняется для небольшого размера таблицы (до 10 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операции необходимо выводить на экран содержимое структуры хеш-таблицы с помощью операции вывода её структуры. При выводе структуры следует отражать состояние, как свободных, так и занятых позиций хеш-таблицы, содержимое цепочек коллизий.
7. Для получения оценки c 2 использовать количество ключей, минимум в 20 раз превышающее размер хеш-таблицы.
8. Тестирование трудоёмкости операций коллекций «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» выполняется в соответствии с технологией тестирования, изложенной в разделе 1.4.
9. Перед тестированием эффективности операций для обеих коллекций задаётся количество элементов, для хранения которых предназначена хеш-таблица. В качестве исходных данных для тестирования задаётся коэффициент заполнения α. Для коллекции «Хеш-таблица с цепочками коллизий» изменение α задаётся неравенством 0,1 
α 10. Для коллекции «Хеш-таблица с открытой адресацией» изменение α задаётся неравенством 0,1 α 1. После тестирования на экран выводится коэффициент заполнения и полученные оценки трудоёмкости для операций поиска, вставки и удаления элементов.
Контрольные вопросы и упражнения.
1. Приведите размер хеш-таблицы с открытой адресацией, предназначенной для хранения 200 элементов, если она использует мультипликативный метод хеширования, модульный метод хеширования.
2. Приведите вид первоначально пустой хеш-таблицы с цепочками коллизий после вставки ключей 1, 89, 45, 76, 2, 13, 33, 4. Хеш-таблица предназначена для хранения 20 элементов, использует модульное хеширование.
3. Приведите вид первоначально пустой хеш-таблицы с открытой адресацией после вставки ключей 1, 89, 45, 76, 2, 13, 33, 4. Хеш-таблица предназначена для хранения 10 элементов, использует модульное хеширование.
4. Приведите соответствующий строке JKRSDS ключ, полученный методом конкатенация битовых образов для хеш-таблицы размером 1000.
5. Приведите соответствующий числу 1263454756 ключ, полученный методом свертки для хеш-таблицы размером 1000.
6. Какая последовательность ячеек получается в результате квадратичного зондирования, если h (k) = k mod 11 и k = 19.
7. Какая последовательность зондируемых ячеек получается в результате двойного хеширования: h (k) = k mod 11, h 1 (k) = 1 + (k mod 10) и k = 19.
Литература
1. Альфред Ахо, Джон Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. - М. - СПб – Киев: «Вильямс», 2000 г. – 384 с.
2. Н. Вирт Алгоритмы + структуры данных = программы. - М.: «Мир», 1985 г. – 406 с.
3. Фрэнк М. Каррано, Джанет Дж. Причард. Абстракция данных и решение задач на С++. Стены и зеркала. - М. - СПб – Киев: «Вильямс», 2003 г. – 848 с.
4. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М: «Мир», 1976 г. (переиздание - М., Изд. "Вильямс", 2000 г.) – 735 с.
5. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М: «Мир», 1978 г. (переиздание - М., Изд. Изд. Вильямс", 2000 г.) – 844 с.
6. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Анализ и построение. - М: «БИНОМ», 2000 г. – 960 с.
7. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. – СПб.: БХВ-Петербург, 2004 г. – 464 с.
8. Дж. Макконелл. Анализ алгоритмов. Вводный курс. - М: «Техносфера», 2002 г. – 304 с.
9. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 1-4. - М: «DiaSoft», 2001 г. – 688 с.
10. Уильям Топп, Уильям Форд. Структуры данных в С++. – М: «Бином», 2000 г. – 816 с.
11. Хезфилд Р., Кирби Л. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. – Киев: «ДиаСофт», 2001г. – 736 с.
12. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. – М.: «Финансы и статистика», 2004 г. – 464 с.
Приложение A:
Дата добавления: 2015-11-04; просмотров: 70 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Задание к лабораторной работе | | | Алгоритм пирамидальной сортировки |