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

В соответствии со схематичным изображением разветвленных списков типичная структура элемента такого списка в памяти должна быть такой, как показано на рис.4.3.

data - данные атома

down - указатель на подсписок того же уровня

next - указатель на следующий элемент

Рис.4.3. Структура элемента разветвленного списка

Элементы списка могут быть двух видов: атомы, содержащие данные и узлы, и содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно, как показано на рис.4.4.

type

data/down

next

Рис.4.4. Структура элемента разветвленного списка

Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис.4.5.

type

down

next

Рис. 4.5. Структура элемента разветвленного списка

В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т.п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом, также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка. В этом случае размер поля type может быть расширен, например, до 1 байта, и это поле может индицировать не только атом/подсписок, но и тип атомарных данных, поле next в дескрипторе данных может использоваться для представления еще какой-то описательной информации, например, размера атома. На рис.4.6 показано представление элементами такого формата списка: (КОВАЛЬ,(12,7,53),d). Первая (верхняя) строка на рисунке представляет элементы списка, вторая - элементы подсписка, третья - дескрипторы данных, четвертая - сами данные. В поле type каждого элемента мы использовали коды: n - узел, S ‑ атом (тип STRING), I - атом (тип INT), C - атом (тип CHAR).

Рис. 4.6. Пример представления списка элементами одного формата

Дата добавления: 2014-01-07