ВУЗ:
Составители:
77
с ближайшим значением ключа и пустым указателем, ведущим в нужном на-
правлении. В поле этого указателя заносится абсолютный или относительный
адрес ячейки с новой записью. Запись оказывается включенной в список.
При исключении записи возможны следующие варианты:
Оба указателя исключаемого элемента «пустые». Тогда соответствую-
щему указателю порождающего узла присваивается значение Q
и доступ к ис-
ключаемому узлу становится невозможным.
Исключаемый элемент имеет один «непустой» указатель. Тогда у по-
рождающего узла соответствующий указатель заменяется «непустым» указате-
лем исключаемого узла.
Оба указателя исключаемого элемента «непустые». Тогда один из по-
рожденных узлов может быть включен в дерево в соответствии с вариантом
«2», а «непривязавшийся» узел
включается в дерево по правилу включения.
На рис. 5.28 показано включение в структуру, изображенную на рис.
5.27 новой записи с ключом 36 и исключение записей с ключами 63 (вариант 2)
и 180 (вариант 1).
Рис. 5.28. Включение и исключение записей в структуре двусвязного списка
Структуры данных, отображаемые многосвязным списком. Если древо-
видная структура
данных предварительно не преобразуется в двоичное дерево,
то при хранении такой структуры в памяти ЭВМ в виде связанного списка каж-
дый ее элемент (узел дерева) может иметь более двух прямых указателей. Такие
структуры хранения называются многосвязным или мультисвязным списком и
используются для отображения в памяти ЭВМ структур данных, имеющих вид
m-арных деревьев. Каждый элемент многосвязного списка имеет формат, пока-
занный на рис. 5.29.
21
Q 7 Q 33
38
100
260 63
Q 51 Q 180
Q 19 Q
Q Q
Q Q
Q 36 Q
Q
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
