В соответствии со схематичным изображением разветвленных
списков типичная структура элемента такого списка в памяти должна
быть такой, как показано на рис.5.14.
┌───────────────────┬───────────────────┬───────────────────┐
│data - данные атома│down - указатель на│next - указатель на│
│ │ подсписок │ следующий элемент│
│ │ │ того же уровня │
└───────────────────┴───────────────────┴───────────────────┘
Рис.5.14. Структура элемента разветвленного списка
Элементы списка могут быть двух видов: атомы - содержащие
данные и узлы - содержащие указатели на подсписки. В атомах не
используется поле down элемента списка, а в узлах - поле data.
Поэтому логичным является совмещение этих двух полей в одно, как
показано на рис.5.15.
┌────┬─────────┬────┐
│type│data/down│next│
└────┴─────────┴────┘
Рис.5.15. Структура элемента разветвленного списка
Поле type содержат признак атом/узел, оно может быть 1-бито-
вым. Такой формат элемента удобен для списков, атомарная информа-
ция которых занимает небольшой объем памяти. В этом случае теря-
ется незначительный объем памяти в элементах списка, для которых
не требуется поля data. В более общем случае для атомарной инфор-
мации необходим относительно большой объем памяти. Наиболее расп-
ространенный в данной ситуации формат структуры узла представлен-
ный на рис.5.16.
┌────┬────┬────┐
│type│down│next│
└────┴────┴────┘
Рис. 5.16. Структура элемента разветвленного списка
В этом случае указатель down указывает на данные или на
подсписок. Поскольку списки могут составляться из данных различ-
ных типов, целесообразно адресовать указателем down не непосредс-
твенно данные, а их дескриптор, в котором может быть описан тип
данных, их длина и т.п. Само описание того, является ли адресуе-
мый указателем данных объект атомом или узлом также может нахо-
диться в этом дескрипторе. Удобно сделать размер дескриптора дан-
ных таким же, как и элемента списка. В этом случае размер поля
type может быть расширен, например, до 1 байта и это поле может
индицировать не только атом/подсписок, но и тип атомарных данных,
поле next в дескрипторе данных может использоваться для представ-
ления еще какой-то описательной информации, например, размера
атома. На рис.5.17 показано представление элементами такого фор-
мата списка: (КОВАЛЬ,(12,7,53),d). Первая (верхняя) строка на ри-
сунке представляет элементы списка, вторая - элементы подсписка,
третья - дескрипторы данных, четвертая - сами данные. В поле type
каждого элемента мы использовали коды: n - узел, S - атом, тип
STRING, I - атом, тип INTEGER, C - атом, тип CHAR.
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│n│ │ ┼───>│n│ │ ┼─────────────────────────>│n│ │ │
└─┴┼┴─┘ └─┴┼┴─┘ └─┴┼┴─┘
│ │ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │
│ └>│n│ │ ┼─>│n│ │ ┼─>│n│ │ │ │
│ └─┴┼┴─┘ └─┴┼┴─┘ └─┴┼┴─┘ │
│ ┌─┬─┬─┐ │ ┌─┬─┬─┐│ ┌─┬─┬─┐│ ┌─┬─┬─┐ │ ┌─┬─┬─┐
└>│S│ │5│ └>│I│ │2│└>│I│ │2│└>│I│ │2│ └>│C│ │1│
└─┴┼┴─┘ └─┴┼┴─┘ └─┴┼┴─┘ └─┴┼┴─┘ └─┴┼┴─┘
│ ┌──────┐ │ ┌──┐ │ ┌──┐ │ ┌──┐ │ ┌─┐
└>│КОВАЛЬ│ └>│12│ └>│ 7│ └>│53│ └>│d│
└──────┘ └──┘ └──┘ └──┘ └─┘
5.17. Пример представления списка элементами одного формата