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