ВУЗ:
Составители:
129
каждого блока становится известным диапазон ключей входящих в него запи-
сей: ключ предшествующей статьи задает нижний предел, а ключ данной статьи
– верхний предел значений ключа записей блока.
На рис. 10.1 изображены фрагмент последовательного массива записей
и соответствующий фрагмент справочника.
Поиск записи с нужным значением ключа осуществляется в два этапа.
На первом
этапе в результате просмотра справочника определяется блок, кото-
рому должна принадлежать нужная запись. Принцип упорядоченности при по-
строении справочника позволяет использовать ускоренные методы просмотра.
На втором этапе следует обращение по указателю к этому блоку и осуществля-
ется последовательный просмотр записей блока. В процессе просмотра нахо-
дится нужная запись или выясняется,
что такой записи нет. Последовательный
просмотр не занимает много времени, поскольку ограничивается размером бло-
ка. Поиск по единому справочнику наиболее эффективен, если число блоков и
число записей в блоке равны √N (N – число записей основного массива).
Для единого справочника существуют определенные трудности при
включении и удалении записей, так как при
этом необходимо обновлять два
последовательных упорядоченных массива: основной и справочник.
Справочник Основной массив
Ключ Указатель Адрес Ключ
33 102 102 22
55 105 103 27
78 108 104 33
… 111 105 42
106 49
107 55
108 60
109 63
110 78
111 79
112 81
Рис. 10.1. Пример организации единого справочника
На рис. 10.2 показан процесс включения в основной массив записи с
ключом 43.
Страницы
- « первая
- ‹ предыдущая
- …
- 127
- 128
- 129
- 130
- 131
- …
- следующая ›
- последняя »
