Представление списковых структур в памяти.

В соответствии со схематичным изображением разветвленных

списков типичная структура элемента такого списка в памяти должна

быть такой, как показано на рис.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. Пример представления списка элементами одного формата