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

Методические указания к выполнению задания

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


Читайте также:
  1. I. Проверка домашнего задания
  2. II Проверка домашнего задания
  3. II. Проверка домашнего задания.
  4. II. Проверка домашнего задания.
  5. II. Проверка домашнего задания.
  6. VII. Методические указания
  7. XII. Требования к выполнению санитарных правил и организации работы медицинского персонала

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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Задание к лабораторной работе| Алгоритм пирамидальной сортировки

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