Методы программирования. Громов Ю.Ю - 123 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

123
Алгоритм L. (Линейное исследование и вставка.)
Этот алгоритм выполняет поиск данного ключа K в таблице с M уз-
лами. Если K отсутствует в таблице и таблица не полна, ключ K будет
вставлен в таблицу.
Узлы таблицы обозначаются как ТАВLЕ[i], 0 ≤ i < М, и могут быть
двух типов – пустыми и занятыми. В занятых узлах содержатся ключи
KEY[i] и, возможно, другие поля. Вспомогательная переменная N исполь-
зуется для отслеживания количества занятых узлов и увеличивается на 1
при каждой вставке нового ключа.
Алгоритм использует хеш-функцию h(K) и линейную последова-
тельность проб (60) для адресации таблицы.
L1. [Хеширование.] Присвоить i ← h(K). (Теперь 0 ≤ i < М.)
L2. [Сравнение.] Если узел ТАВLЕ[i] пуст, перейти к шагу L4. В про-
тивном случае, если KEY[i] = K, алгоритм успешно завершается.
L3. [Переход к следующему.] Присвоить i ← i – 1. Если теперь i < 0,
присвоить i ← i + М. Вернуться к шагу L2.
L4. [Вставка.] (Поиск оказался неудачным.) Если N = М – 1, алгоритм
завершается в связи с переполнением. В противном случае N ← N + 1,
пометить узел ТАВLЕ[i] как занятый и присвоить KEY[i] ← K. ■
0 585
1 433
2 830
3 516
4 571
5
6
7 161
8 432
Рис. 46. Линейная открытая адресация
На рисунке 46 показано, что происходит при вставке семи ключей
K = 830, 585, 516, 432, 571, 161 и 433 нашего примера с хеш-кодами
h(K) = 2, 0, 3, 0, 4, 8 и 1 соответственно. При этом ключи 432 и 161 сме-
щены со своих начальных позиций h(K).
Упражнения
1. Выполните с применением алгоритма C, использующего хеш-
функцию h(K) = K mod M, последовательную вставку ключей 443, 564,
434, 704, 157, 541, 240 в пустую хеш-таблицу из М = 9 узлов.
2. Примените алгоритм L, использующий хеш-функцию h(K) =
= K mod M, для последовательной вставки ключей 601, 372, 268, 365, 622,
609, 133 в пустую хеш-таблицу из М = 9 узлов.

Страницы