- •Структуры данных и алгоритмы их обработки
- •Структуры данных и алгоритмы их обработки Лабораторный практикум
- •230105 - «Программное обеспечение вычислительной техники и автоматизированных систем»
- •220201- «Управление и информатика в технических системах»
- •Лабораторная работа № 1
- •Фундаментальные структуры данных
- •Лабораторная работа № 2 Алгоритмы поиска в фиксированной группе данных.
- •Лабораторная работа № 3 Алгоритмы базовых и улучшенных сортировок. Порядковые статистики.
- •Часть I (пункты 3÷6)
- •Часть II (пункты 7÷10)
- •Лабораторная работа №4 Полустатические структуры данных
- •Контрольные вопросы
- •Лабораторная работа № 5
- •Динамические структуры данных односвязные и двусвязные списковые структуры
- •Контрольные вопросы
- •Лабораторная работа № 6
- •Деревья , как динамические структуры данных .
- •Лабораторная работа № 7
- •Алгоритмы метода перебора с возвратами - (мпв), "жадные" алгоритмы.
- •Лабораторная работа № 8 Хеширование. Алгоритмы организации и обработки хеш-таблиц.
- •Порядок выполнения работы.
- •Лабораторная работа № 9 Сетевые модели. Алгоритмы на графах.
- •Порядок выполнения работы.
Лабораторная работа № 8 Хеширование. Алгоритмы организации и обработки хеш-таблиц.
(4 часа)
Цель работы: Освоить на практике алгоритмы организации хеш-таблиц с открытой адресацией и хеш-таблиц с разрешением коллизий методом цепочек .
Домашнее задание:
Изучить алгоритмы организации хеш-таблиц с открытой адресацией, способы разрешения коллизий для таких таблиц , а так же алгоритмы поиска по ключу, добавления и удаления элемента.
Изучить организацию хеш-таблиц с разрешением коллизий методом цепочек.
Порядок выполнения работы.
Открыть проект Delphi Structures.
Добавить в управляющее главное меню пункт «Лабораторная работа №8», при выборе которого должно появляться окно модуля «Hesh» (модуль «Hesh» с формой добавить в проект).
Установить на форму модуля Hesh компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №8.1.
В обработчике события onClick управляющей кнопки на языке Object Pascal написать фрагмент программы для реализации алгоритма хеширования заданного ключа и дальнейшего поиска ключа в хеш-таблице в соответствии с вариантом задания.
Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
произвести анализ запрограммированного алгоритма (по количеству сравнений).
Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.
Таблица 8.1
|
№ вар. |
Текст задачи |
|
1. |
Организовать хеш-таблицу с открытой адресацией, используя хеш-функцию h(k)=trunc(M*Frac(k*d)), где d=(sqrt(5)-1)/2, M - размер хеш-таблицы. Организовать процедуру поиска по ключу в этой хеш-таблице. Результат поиска - номер ячейки с найденным ключом или (-1).
|
|
2. |
Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования хеш-адреса использовать хеш-функцию универсального хеширования и процедуру линейного исследования для разрешения коллизии.
|
|
3. |
Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования начального хеш-адреса использовать метод деления, а затем при возникновении коллизии процедуру квадратичного исследования.
|
|
4. |
Построить хеш-таблицу с открытой адресацией, используя двойное хеширование, как способ открытой адресации. Хеш-функция h1(k) и h2(k) организовать методом деления. Формирование таблицы - с помощью процедуры поиска и вставки по ключу.
|
|
5. |
Организовать хеш-таблицу, используя хеш-функцию h(k) по методу умножения для формирования хеш-адреса. разрешение коллизий - методом внешних цепочек. а) Написать процедуру поиска и вставки по ключу. б) Написать процедуру удаления ключа.
|
|
6. |
Организовать хеш-таблицу с помощью идеального хеширования - двухуровневая схема с универсальным хешированием на каждом уровне. Запрограммировать процедуру поиска и вставки по ключу.
|
|
7. |
Организовать программно хеширование 100 записей в таблицу. состоящую из 20 ссылок на линейные списки (стеки), первоначально пустые. записи имеют неотрицательные целые ключи k<50, формируемые случайным образом. Хеш-функцию организовать методом умножения в отдельной Function.
|
|
8. |
Организовать программно хеширование 50 записей в таблицу. состоящую из 10 ссылок на линейные списки (очереди), первоначально пустые. записи имеют неотрицательные целые ключи k<30, формируемые случайным образом. Хеш-функцию организовать методом деления в отдельной Function
|
Контрольные вопросы
1. Что такое хеширование?
2. Какую структуру данных используют для формирования хеш-таблицы?
3.Что мы называем ситуацией конфликта или коллизией, возникающей при хешировании?
4. Как организована -таблица с прямой адресацией?
5. В чем заключается метод цепочек разрешения коллизии при хешировании?
6. Какие вы знаете хеш-функции?
7. Что такое хеш-таблица с открытой адресацией и каковы способы разрешения коллизий для нее?
8. Какова основная идея идеального хеширования?
9. Сформулируйте основное правило формирования вторичной хеш-таблицы.