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