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

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Вызовы Результаты вызовов
R
everse( (a ( b c ) d) )
R
everse( ( ( b c ) d ) )
Reverse( ( d ) )
Reverse( Nil )
Cons( d
1
, Nil )
Concat( Nil, ( d¹ ) )
Destroy( Nil )
Destroy( ( d
1
) )
Cons( ( b
1
c
1
), Nil )
Concat( ( d
2
), ( ( b
1
c
1
) ) )
Destroy( ( d
2
) );
Destroy( ( ( b
1
c
1
) ) )
Cons( a
1
, Nil )
Concat( ( d
3
( b
2
c
2
) ), ( a
1
) )
Destroy( ( d
3
( b
2
c
2
) ) )
Destroy( ( a
1
) )
( d
4
( b
3
c
3
) a
2
)
( d
3
( b
2
c
2
) )
( d
2
)
( )
( d
1
)
( d
2
)
[ ( d
1
) ]
( ( b
1
c
1
) )
( d
3
( b
2
c
2
) )
[ ( d
2
) ] [ ( ( b
1
c
1
) ) ]
( a
1
)
( d
4
( b
3
c
3
) a
2
)
[ (d
3
( b
2
c
2
) ) ]
[ ( a
1
) ]
Рис. 1.24. Последовательность вызовов подпрограмм при обращении
иерархического списка
Для краткости на рисунке не приведены вызовы функций Head, Tail, Copy,
а также последовательности вызовов функций, порождаемые вызовом Concat.
Использующая накапливающий параметр функция обращения списка Rev
реализуется, например как
function Rev ( y, z : H_list ) : H_list;
begin
if Null( y ) then Rev := z
else Rev := Rev ( Tail ( y ), Cons ( Copy ( Head( y ) ), z ) );
end;
Функция Append из примера 1.3, добавляющая элемент в конец списка,
может быть реализована как
function Append ( y : H_list; x : El ) : H_list;
var p : H_list;
begin
p := Cons( Make_Atom( x ), nil );
Append := Concat ( y, p );
Destroy ( p );
end;
Подпрограммы ввода−вывода иерархических списков должны быть напи-
саны применительно к конкретной форме представления списка и помещены в
отдельный модуль. Так, если список представляется сокращенной скобочной
записью, размещенной в текстовом файле, а El – любой из типов, совмести-
30
 Вызовы                                     Результаты вызовов
Reverse( (a ( b c ) d) )                             ( d4 ( b3 c3 ) a2 )
Reverse( ( ( b c ) d ) )                    ( d3 ( b2 c2 ) )
 Reverse( ( d ) )                           ( d2 )
 Reverse( Nil )                             ( )
 Cons( d1, Nil )                            ( d1 )
 Concat( Nil, ( d¹ ) )
 Destroy( Nil )                             ( d2 )
 Destroy( ( d1 ) )                          [ ( d1 ) ]
 Cons( ( b1 c1 ), Nil )                     ( ( b1 c1 ) )
 Concat( ( d2 ), ( ( b1 c1 ) ) )            ( d3 ( b2 c2 ) )
 Destroy( ( d2 ) );                         [ ( d2 ) ] [ ( ( b1 c1 ) ) ]
  Destroy( ( ( b1 c1 ) ) )                  ( a1 )
  Cons( a1, Nil )                           ( d4 ( b3 c3 ) a2 )
  Concat( ( d3 ( b2 c2 ) ), ( a1 ) )        [ (d3 ( b2 c2 ) ) ]
  Destroy( ( d3 ( b2 c2 ) ) )               [ ( a1 ) ]
  Destroy( ( a1 ) )

             Рис. 1.24. Последовательность вызовов подпрограмм при обращении
                                   иерархического списка

    Для краткости на рисунке не приведены вызовы функций Head, Tail, Copy,
а также последовательности вызовов функций, порождаемые вызовом Concat.
    Использующая накапливающий параметр функция обращения списка Rev
реализуется, например как
function Rev ( y, z : H_list ) : H_list;
begin
      if Null( y ) then Rev := z
      else Rev := Rev ( Tail ( y ), Cons ( Copy ( Head( y ) ), z ) );
end;

   Функция Append из примера 1.3, добавляющая элемент в конец списка,
может быть реализована как
function Append ( y : H_list; x : El ) : H_list;
var p : H_list;
begin
      p := Cons( Make_Atom( x ), nil );
      Append := Concat ( y, p );
      Destroy ( p );
 end;

   Подпрограммы ввода−вывода иерархических списков должны быть напи-
саны применительно к конкретной форме представления списка и помещены в
отдельный модуль. Так, если список представляется сокращенной скобочной
записью, размещенной в текстовом файле, а El – любой из типов, совмести-
                                           30

Страницы