Практические задания
Задание 1. Построить бесконфликтную хеш-таблицу для заданного набора текстовых ключей. Число ключей (и размер таблицы) равен 10. В качестве ключей взять 10 любых служебных слов языка Паскаль. Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа: код (End) = код (E) + код (n) + код (d). Преобразование числового кода ключа в значение индекса выполнить с помощью простейшей хеш-функции, которая берет остаток от целочисленного деления кода на размер хеш-таблицы (в задании – 10).
Для подсчета индексов ключей написать вспомогательную программу, которая в диалоге многократно запрашивает исходный текстовый ключ (служебное слово языка Паскаль) и подсчитывает значение хеш-функции. Программа должна вычислять длину очередного текстового ключа с помощью функции Length, в цикле вычислять сумму кодов всех символов ключа и брать остаток от деления этой суммы на 10.
Если некоторые исходные ключи будут конфликтовать друг с другом, можно изменить исходное слово, например – сменить регистр начальной буквы или всех букв в слове, полностью заменить слово на близкое по значению (End на Stop и.т.д.), ввести какие-либо спецсимволы или придумать другие способы
После подбора неконфликтующих ключей написать основную программу, которая должна:
· ввести подобранные ключи и расположить их в ячейках хеш-таблицы в соответствии со значением хеш-функции
· вывести хеш-таблицу на экран
· организовать циклический поиск разных ключей, как имеющихся в таблице (с выводом местоположения), так и отсутствующих: вычислить для ключа значение хеш-функции и сравнить содержимое соответствующей ячейки таблицы с исходным ключом
Задание 2. Реализовать метод внутреннего хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле
j = (( h (ключ) + i ) mod m ) + 1, где i = 0, 1, 2, . . . , m-2
Программа должна выполнять следующие действия:
· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
· вывод текущего состояния таблицы на экран
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска.
Задание 3. Реализовать метод открытого хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.
Программа должна выполнять следующие действия:
· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
· вывод текущего состояния таблицы на экран
· удаление заданного ключа из таблицы
Алгоритм удаления:
· вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице
· если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей
· если удаляемый элемент найден в списке, то производится его удаление с изменением указателей
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска.
4.5. Контрольные вопросы по теме
1. В чем заключается метод хеш-поиска?
2. Для чего используется хеш-функция и какие к ней предъявляются требования?
3. Что такое хеш-таблица и как она используется?
4. Как по трудоемкости соотносятся между собой основные методы поиска (полный перебор, двоичный поиск, хеш-поиск)?
5. Как с помощью простейшей хеш-функции находится расположение в таблице строковых ключей?
6. Какие проблемы могут возникать при построении хеш-таблиц с произвольными наборами ключей?
7. В каких ситуациях можно построить бесконфликтную хеш-таблицу?
8. Где на практике и почему можно использовать бесконфликтные хеш-таблицы?
9. Что такое открытое хеширование и для чего оно применяется?
10. Какие структуры данных используются для реализации открытого хеширования?
11. Какие шаги выполняет алгоритм построения хеш-таблицы при открытом хешировании?
12. Какие шаги выполняет алгоритм поиска в хеш-таблице при открытом хешировании?
13. Какие проблемы могут возникать при использовании открытого хеширования?
14. Как влияет размер хеш-таблицы на эффективность открытого хеширования?
15. Что такое внутреннее хеширование и для чего оно применяется?
16. Какие правила можно использовать для поиска свободных ячеек при внутреннем хешировании?
17. Какие шаги выполняет алгоритм построения хеш-таблицы при внутреннем хешировании?
18. Какие шаги выполняет алгоритм поиска в хеш-таблице при внутреннем хешировании?
19. Как влияет размер хеш-таблицы на эффективность внутреннего хеширования?
20. В каких задачах НЕ следует применять метод хеш-поиска?
Дата добавления: 2020-07-18; просмотров: 458;