ВУЗ:
Составители:
128
ся в оперативной памяти; длина записей в справочнике выбирается существенно
меньшей, чем длина записей основного массива.
Система справочника – единственная система организации данных,
обеспечивающая ускорение поиска в неупорядоченных массивах и массивах
записей переменной длины.
Общий справочник. Общий справочник создается для основного неупо-
рядоченного массива, который может содержать записи как фиксированной, так
и переменной длины.
В общем справочнике для каждой записи основного массива создается
одна справочная запись. Записи справочника называются статьями.
Каждая статья общего справочника содержит поле ключа и поле указа-
теля. Указатель определяет местоположение записи с данным ключом в основ-
ном массиве. Если основной массив находится в оперативной памяти, то указа-
тель является адресом хранения записи, определяемым с точностью до байта.
Если основной массив находится во внешней памяти, то указатель определяет
абсолютную и относительную позицию записи в файле или на соответствую-
щем накопителе (номер зоны на магнитной ленте или номер дорожки на маг-
нитном диске). Статьи справочника обычно упорядочиваются по значению
ключа
.
При добавлении новой записи она помещается в конец основного мас-
сива в свободной области памяти. В справочнике для этой новой записи органи-
зуется соответствующая статья. Если справочник упорядочен, то новая статья
ставится в нужное место в соответствии со значением ключа, при этом статьи
справочника передвигаются, освобождая место для новой статьи.
При удалении записи она или удаляется из основного массива, или ста-
новится недоступной, физически оставаясь на прежнем месте. Справочник об-
новляется либо перемещением его статей со стиранием ставшей ненужной ста-
тьи, либо путем специальной пометки статьи, указывающей на недоступность
записи в основном массиве.
В справочнике может использоваться связанное представление данных.
В
этом случае при включении или удалении статей перезаписи справочника не
требуется, изменяются лишь соответствующим образом указатели.
Количество статей общего справочника равно количеству записей ос-
новного массива, поэтому экономия оперативной памяти образуется из-за раз-
ницы в длине основных записей и соответствующих им статей справочника.
Единый справочник. При организации единого справочника
основной
массив упорядочивается по значению ключей записи. Упорядоченный массив
делится на блоки, каждый блок содержит определенное число записей. Блоки
могут иметь различные размеры, т.е. содержать разное число записей. Однако
обычно устанавливают блоки одинакового размера. На каждый блок в справоч-
нике заводится одна статья, состоящая из поля ключа и поля указателя
. В поле
указателя статьи содержится адрес первой записи блока, а в поле ключа – зна-
чение ключа последней записи этого блока. При такой организации статьи для
Страницы
- « первая
- ‹ предыдущая
- …
- 126
- 127
- 128
- 129
- 130
- …
- следующая ›
- последняя »
