ВУЗ:
Составители:
38
102 Запись C
. . . . . . . . . . .
100+N-2 Запись N
100+N-1 Запись N+1
Свободный участок
Рис. 3.6. Состояние последовательного массива после его перезапис
Многие приложения СОД требуют непрерывного обновления и коррек-
тировки записей, что приводит к большим потерям времени на частую переза-
пись и – к неэффективному использованию памяти. В таких приложениях по-
следовательное представление неприемлемо и заменяется связанным представ-
лением.
При связанном представлении в каждой записи
предусматривается
дополнительное поле, в котором размещается указатель (ссылка). Физический
порядок следования записей в этом случае может не соответствовать логиче-
скому порядку. В памяти записи располагаются в любых свободных ячейках и
связываются между собой указателями, показывающими место расположения
записи, логически следующей за данной записью. Указатель можно интерпре-
тировать как адрес ячейки
памяти, в которой хранится следующая запись.
Структуры хранения, основанные на связанном представлении данных,
называют связанными списками. Если каждая запись содержит лишь один ука-
затель, то список односвязный, при большем числе указателей – список много-
связный.
Пусть структура данных имеет следующую логическую последователь-
ность записей:
Запись А
Запись В
Запись С
Запись F
Записи размещены в ячейках с адресами 01, 05, 03, 10. В поле указателя
каждой записи размещается адрес связи (АС), определяющий адрес ячейки с
логически следующей записью. Структура хранения такого массива представ-
лена на рис. 3.7. Порядок чтения записей указан стрелками.
Связанное представление обеспечивает гибкость структуры хранения.
Ведение списка не требует перезаписи элементов массива, а
производится с
помощью такой замены указателей, чтобы логический порядок следования за-
писей не нарушался. Однако для размещения указателей требуется дополни-
тельный объем памяти.
Головная ячейка
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
