ВУЗ:
Составители:
121
Рис. 44. Раздельные цепочки
Алгоритм С. (Поиск и вставка в хеш-таблице с цепочками.)
Этот алгоритм ищет заданный ключ K в таблице из М узлов. Если
ключ K в таблице отсутствует, а таблица не заполнена, он вставляется в
таблицу.
Узлы таблицы обозначаются через ТАВLЕ[i], 0 ≤ i ≤ М, и могут быть
двух различных типов – пустыми и занятыми. В занятом узле содержат-
ся поле ключа KEY[i], поле ссылки LINK[i] и, возможно, другие поля.
Алгоритм использует хеш-функцию h(K). Применяется также вспо-
могательная переменная R для упрощения поиска пустых мест. Если таб-
лица пуста, то R = М + 1. По мере выполнения вставок всегда будет оста-
ваться истинным утверждение, что узлы TABLE[j] заняты для всех j в
диапазоне R ≤ j ≤ М. По соглашению узел ТАВLЕ[0] всегда пуст.
С1. [Хеширование.] Присвоить i ← h(K) + 1. (Теперь 1 ≤ i ≤ М.)
С2. [Есть ли список?] Если узел ТАВLE[i] пуст, то перейти к шагу С6
(В противном случае ТАВLЕ[i] занят и необходимо приступить к поиску в
списке, начинающемся в этом узле.)
С3. [Сравнение.] Если K = KEY[i], то алгоритм успешно завершается.
С4. [Переход к следующему.] Если LINK[i] ≠ 0, то присвоить
i ← LINK[i] и вернуться к шагу С3.
С5. [Поиск пустого узла.] (Поиск был неудачным, и необходимо
найти пустое место в таблице.) Уменьшать R один или более раз, пока не
будет найдено такое значение, при котором узел ТАВLЕ[R] будет пуст.
Если R = 0, то алгоритм завершается в связи с переполнением (свободных
узлов больше нет); в противном случае присвоить LINK[i] ← R, i ← R.
HEAD[1]:
HEAD[2]:
HEAD[3]:
HEAD[4]:
HEAD[5]:
HEAD[6]:
HEAD[7]:
HEAD[8]:
HEAD[9]:
585
433 Λ
432 Λ
830 Λ
516 Λ
571 Λ
161 Λ
Λ
Λ
Λ
Страницы
- « первая
- ‹ предыдущая
- …
- 119
- 120
- 121
- 122
- 123
- …
- следующая ›
- последняя »
