ВУЗ:
Составители:
18
Связи часто изображаются просто стрелками:
Здесь FIRST – указатель на первый узел в списке.
Сопоставим последовательное и связанное распределение:
1. Связанное распределение требует дополнительного пространства
в памяти для хранения связей. Однако при использовании связанной па-
мяти часто возникает неявный выигрыш в памяти за счёт совмещения
общих частей таблиц. Кроме того, связанное распределение будет более
эффективным при плотно загруженной памяти.
2. Легко исключить элемент, находящийся внутри связанного спи-
ска. Для этого необходимо только изменить связь в предшествующем
элементе. При последовательном же распределении такое исключение
обычно требует перемещения значительной части списка вверх на другие
места памяти.
3. При связанном распределении легко включить элемент в список.
Например, для включения элемента 21/2 в (9) необходимо изменить лишь
две связи:
Такая операция заняла бы значительное время при работе с длинной
последовательной таблицей.
4. При связанном распределении памяти значительно медленнее,
чем при последовательном, выполняются обращения к произвольным
частям списка. Однако в большинстве приложений продвижение по спи-
ску осуществляется последовательно, а не произвольным образом. Кроме
того, можно создать дополнительные переменные связи, указывающие на
соответствующие места в списке.
5. При использовании схемы со связями упрощается задача объе-
динения двух списков или разбиения списка на части.
6. Схема со связями годится для структур более сложных, чем ли-
нейные списки.
Рассмотрим организацию включения и исключения узлов для свя-
занного списка.
Пусть каждый узел списка имеет два поля:
INFO LINK (11)
где INFO – полезная информация, LINK – связь со следующим узлом.
Эл−т 1 Эл−т 2 Эл−т 3 Эл−т 4 Эл−т 5
FIRST
(9)
Эл−т 1 Эл−т 2 Эл−т 3 Эл−т 4 Эл−т 5
FIRST
(10)
Эл−т 21/2
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
