Динамические структуры данных. Алексеев А.Ю - 22 стр.

Вызовы                                                Возвращаемые значения
Reverse1 ( ( a b ) )                              (ba)
Rev ( ( a b ), Nil )                              (ba)
 Rev ( ( b ), Cons( a, Nil ) )                    (ba)
 * Cons ( a, Nil )                                (a)
Rev ( Nil, Cons ( b, ( a ) ) )                    (ba)
 * Cons ( b, ( a ) ) )                            (ba)

    Рис. 1.19. Последовательность вызовов функций, порождаемая вызовом Reverse1

    Количество вызовов конструктора Cons в последнем варианте обращения
списка длины n, очевидно, равно n, что по сравнению с первым вариантом да-
ет существенный выигрыш в объеме вычислений.
    Вопросы реализации рекурсивной обработки списков на Паскале рассмот-
рены далее в 1.7 сразу для иерархических списков, частным случаем которых
являются списки линейные.


                                 1.7. Иерархические списки

   Рассмотренные в предыдущих разделах динамические структуры однотип-
ных данных предназначены только для обработки последовательностей эле-
ментов, тогда как в практических приложениях возникает необходимость ра-
боты с более сложными, нелинейными конструкциями. Рассмотрим одну из
них, называемую иерархическим списком элементов базового типа El или S-
выражением. Определим соответствующий тип данных S_expr ( El ) рекур-
сивно, используя данное в 1.6 определение линейного списка (типа L_list ):

   < S_expr ( El ) > ::= < Atomic ( El ) > | < L_list ( S_expr( El ) ) >

   < Atomic ( E ) > ::= < El >

    Иерархический список согласно определению представляет собой или
элемент базового типа El, называемый в этом случае атомом ( атомарным S–
выражением ), или линейный список из S–выражений. Приведенное опре-
деление задает структуру непустого иерархического списка как элемента раз-
меченного объединения множества атомов и множества пар "голова"–"хвост"
и порождает различные формы представления в зависимости от принятой
формы представления линейного списка. Традиционно иерархические списки
представляют или графически, используя для изображения структуры списка
двухмерный рисунок, или в виде одномерной скобочной записи.
    Рассмотрим примеры (рис. 1.20) иерархических списков из элементов базово-
го типа El, представляющие списки в полной и сокращенной скобочной записи.
Переход к сокращенной записи произведен по правилам, изложенным в 1.6.


                                            22