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

3.1 Основные понятия

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

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

Рис.5.2. Нелинейный список

 

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

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

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

 

 

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

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

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

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

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

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

type

data/down

next

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

type

down

next

     Рис. 5.5. Структура элемента разветвленного списка В этом  случае  указатель  down  указывает  на данные или на подсписок. Поскольку списки могут составляться из данных  различных типов, целесообразно адресовать указателем down не непосредственно данные,  а их дескриптор,  в котором может быть описан тип данных, их длина и т.п.  Само описание того, является ли адресуемый указателем данных объект атомом или узлом также  может  находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же,  как и элемента списка.