Лекция: Нелинейные разветвленные списки

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

Нелинейным разветвленным списком является список, элементами

которого могут быть тоже списки. В разделе 5.2 мы рассмотрели

двухсвязные линейные списки. Если один из указателей каждого эле-

мента списка задает порядок обратный к порядку, устанавливаемому

другим указателем, то такой двусвязный список будет линейным. Ес-

ли же один из указателей задает порядок произвольного вида, не

являющийся обратным по отношению к порядку, устанавливаемому дру-

гим указателем, то такой список будет нелинейным.

В обработке нелинейный список определяется как любая после-

довательность атомов и списков (подсписков), где в качестве атома

берется любой объект, который при обработке отличается от списка

тем, что он структурно неделим.

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

разделим запятыми, то в качестве списков можно рассматривать та-

кие последовательности:

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

( )

((a))

Первый список содержит четыре элемента: атом a, список (b,c,

d) (содержащий в свою очередь атомы b,c,d), атом e и список

(f,g), элементами которого являются атомы f и g. Второй список не

содержит элементов, тем не менее нулевой список, в соответствии с

нашим определением является действительным списком. Третий список

состоит из одного элемента: списка (a), который в свою очередь

содержит атом а.

Другой способ представления, часто используемый для иллюст-

рации списков, — графические схемы, аналогичен способу представ-

ления, применяемому при изображении линейных списков. Каждый эле-

мент списка обозначается прямоугольником; стрелки или указатели

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

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

дан на рис.5.12.

┌───┐ ┌────>┌───┐ ┌────>┌───┐ ┌────>┌───┐

│ a │ │ ┌─┼─ │ │ │ e │ │ ┌──┼─ │

├───┤ │ │ ├───┤ │ ├───┤ │ │ ├───┤

│ ─┼───┘ │ │ ─┼───┘ │ ─┼───┘ │ │nil│

└───┘ │ └───┘ └───┘ │ └───┘

└─>┌───┐ ┌>┌───┐ ┌>┌───┐ └─>┌───┐ ┌>┌───┐

│ b │ │ │ c │ │ │ d │ │ f │ │ │ g │

├───┤ │ ├───┤ │ ├───┤ ├───┤ │ ├───┤

│ ─┼──┘ │ ─┼──┘ │nil│ │ ─┼──┘ │nil│

└───┘ └───┘ └───┘ └───┘ └───┘

Рис.5.12. Схематическое представление разветвленного списка

Разветвленные списки описываются тремя характеристиками: по-

рядком, глубиной и длиной.

Порядок. Над элементами списка задано транзитивное отноше-

ние, определяемое последовательностью, в которой элементы появля-

ются внутри списка. В списке (x,y,z) атом x предшествует y, а y

предшествует z. При этом подразумевается, что x предшествует z.

Данный список не эквивалентен списку (y,z,x). При представлении

списков графическими схемами порядок определяется горизонтальными

стрелками. Горизонтальные стрелки истолковываются следующим обра-

зом: элемент из которого исходит стрелка, предшествует элементу,

на который она указывает.

Глубина. Это максимальный уровень, приписываемый элементам

внутри списка или внутри любого подсписка в списке. Уровень эле-

мента предписывается вложенностью подсписков внутри списка,

т.е.числом пар круглых скобок, окаймляющих элемент. В списке,

изображенном на рис.5.12), элементы a и e находятся на уровне 1,

в то время как оставшиеся элементы — b, c, d, f и g имеют уровень

2. Глубина входного списка равна 2. При представлении списков

схемами концепции глубины и уровня облегчаются для понимания, ес-

ли каждому атомарному или списковому узлу приписать некоторое

число l. Значение l для элемента x, обозначаемое как l(x), явля-

ется числом вертикальных стрелок, которое необходимо пройти для

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

рис.5.12 l(a)=0, l(b)=1 и т.д. Глубина списка является максималь-

ным значением уровня среди уровней всех атомов списка.

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

длина списка на рис.5.12 равна 3.

Типичный пример применения разветвленного списка — представ-

ление последнего алгебраического выражения в виде списка. Алгеб-

раическое выражение можно представить в виде последовательности

элементарных двухместных операций вида:

<операнд 1> <знак операции> <операнд 2>

┌───┐ ┌>┌───┐ ┌>┌───┐

┌─┼─ │ │ │ + │ │ │ f │

│ ├───┤ │ ├───┤ │ ├───┤

│ │ ─┼──┘ │ ─┼──┘ │nil│

│ └───┘ └───┘ └───┘

└>┌───┐ ┌>┌───┐ ┌──>┌───┐

┌───┼─ │ │ │ * │ │ ┌─┼─ │

│ ├───┤ │ ├───┤ │ │ ├───┤

│ │ ─┼──┘ │ ─┼──┘ │ │nil│

│ └───┘ └───┘ │ └───┘

└>┌───┐┌>┌───┐┌>┌───┐ └>┌───┐┌>┌───┐┌───>┌───┐

│ a ││ │ + ││ │ b │ │ c ││ │ — ││ ┌─┼─ │

├───┤│ ├───┤│ ├───┤ ├───┤│ ├───┤│ │ ├───┤

│ ─┼┘ │ ─┼┘ │nil│ │ ─┼┘ │ ─┼┘ │ │nil│

└───┘ └───┘ └───┘ └───┘ └───┘ │ └───┘ │

┌──────────────┘

└─>┌───┐┌>┌───┐┌>┌───┐

│ d ││ │ / ││ │ e │

├───┤│ ├───┤│ ├───┤

│ ─┼┘ │ ─┼┘ │nil│

└───┘ └───┘ └───┘

Рис.5.13. Схема списка, представляющего алгебраическое выражение

Выражение:

(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.