Нелинейные разветвленные списки

Основные понятия Нелинейным разветвленным списком является список, элементами которого могут быть тоже списки. Если один из указателей каждого элемента списка задает порядок обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейным. Если же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.

В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.

Если мы заключим списки в круглые скобки, а элементы списков разделим запятыми, то в качестве списков можно рассматривать такие последовательности:

(a,(b, c, d), e,(f, g)).

((a)).

Первый список содержит четыре элемента: атом a, список (b, c, d) (содержащий в свою очередь атомы b, c, d), атом e и список (f, g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.

Другой способ представления, часто используемый для иллюстрации списков, — графические схемы, аналогичен способу представления, применяемому при изображении линейных списков. Каждый элемент списка обозначается прямоугольником; стрелки или указатели показывают, являются ли прямоугольники элементами одного и того же списка или элементами подсписка. Пример такого представления дан на рисунке.

Разветвленные списки описываются тремя характеристиками: порядком, глубиной и длиной.

Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x, y, z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y, z, x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка, предшествует элементу, на который она указывает.

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

Длина — это число элементов уровня 1 в списке.

Пример применения разветвленного списка — представление последнего алгебраического выражения в виде списка. Алгебраическое выражение можно представить в виде последовательности элементарных двухместных операций вида:

Выражение:

(a+b)*(c-(d/e))+f.

будет вычисляться в следующем порядке:

a+b.

d/e.

c-(d/e).

• (a+b)*(c-d/e)
• (a+b)*(c-d/e)+f

При представлении выражения в виде разветвленного списка каждая тройка «операнд-знак-операнд» представляется в виде списка, причем, в качестве операндов могут выступать как атомы — переменные или константы, так и подсписки такого же вида. Скобочное представление нашего выражения будет иметь вид: (((a,+, b),*,(c,-,(d,/, e)),+, f).

Глубина этого списка равна 4, длина — 3.

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

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

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

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

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