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

    Определенная в примере 1.2 функция Concat, примененная, например, к
спискам y = ( a (b ш) ), z = ( d e ) должна возвратить значение Concat ( y, z ) =
= ( a ( b c ) d e ) . На Паскале она может быть записана следующим образом:
function Concat ( y, z : H_list ) : H_list;
begin
       if Null ( y ) then Concat := Copy ( z )
       else Concat := Cons( Copy( Head( y ) ), Concat( Tail( y ), z ) );
end;
    Функция создает новый иерархический список из копий атомов, входящих
в соединяемые списки. На рис.1.23 изображена последовательность вызовов
функций и возвращаемых ими значений, порождаемая вызовом функции
Concat. Верхние индексы на рисунке использованы для обозначения номе-
ров экземпляров (копий) атомов. Для краткости все вызовы функций Head,
Tail, а также большинство вызовов Copy, заменены на возвращаемые этими
функциями значения.

 Вызовы                                              Возвращаемые значения
Concat( ( a ( b c ) ), ( d e ) )                    ( a¹ ( b¹ c¹ ) d¹ e¹ )
Cons( a¹, Concat( ( ( b c ) ), ( d e ) ) *Concat(   ( a ¹ ( b¹ c¹ ) d¹ e¹ )
 ( ( b c ) ), ( d e ) )                             ( ( b¹ c¹ ) d¹ e¹ )
 Cons( ( b¹ c¹ ),Concat( Nil,( d e ) ) )            ( ( b¹ c¹ ) d¹ e¹ )
 *Concat( Nil, ( d e ) )                            ( d¹ e¹ )
      Copy( ( d e ) )                               ( d¹ e¹ )

       Рис. 1.23. Последовательность вызовов функций при соединении двух списков

    Обращающая список функция Reverse, определение которой дано в примере
1.4, также может быть применена к иерархическим спискам. Например, Re-
verse( y ) = ( d ( b с ) a ) для y = ( a ( b c ) d ). На Паскале функция может иметь вид
function Reverse ( y : H_list ) : H_list;
var p1, p2 : H_list;
begin
       if Null( y ) then Reverse := nil
       else begin p1 := Reverse ( Tail( y ) );
                     p2 := Cons ( Copy ( Head( y ) ), nil );
                     Reverse := Concat ( p1, p2 );
                     Destroy( p1 ); Destroy ( p2 );
        end;
end;
    Как можно видеть на рис. 1.24, в процессе выполнения Reverse создаются
рабочие копии атомов, входящие во временно существующие списки. Так,
атом d копируется четыре раза, причем все копии, кроме четвертой копии d4,
входящей в результирующий список, уничтожаются вместе с временно суще-
ствующими списками. На рис. 1.24 уничтожаемые при выполнении процеду-
ры Destroy списки изображены в квадратных скобках.

                                               29