double arrow

Порядок выполнения работы. 1. Открыть проект Delphi Structures


1. Открыть проект Delphi Structures.

2. Добавить в управляющее главное меню пункт «Лабораторная работа №8», при выборе которого должно появляться окно модуля «Hesh» (модуль «Hesh» с формой добавить в проект).

3. Установить на форму модуля Hesh компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №8.1.

4. В обработчике события onClick управляющей кнопки на языке Object Pascal написать фрагмент программы для реализации алгоритма хеширования заданного ключа и дальнейшего поиска ключа в хеш-таблице в соответствии с вариантом задания.

5. Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.

6. произвести анализ запрограммированного алгоритма (по количеству сравнений).

7. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.


Таблица 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. Сформулируйте основное правило формирования вторичной хеш-таблицы.


Сейчас читают про: