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

   На рис. 1. 22 представлен макет модуля HList, реализующего на Турбо-
Паскале типы данных и базовые функции, необходимые для организации и
рекурсивной обработки иерархических списков. Значение типа H_list (иерар-
хический список) здесь представляет собой ссылку на запись с вариантами
типа S_expr, поле Tag которой идентифицирует запись как атом или как пару
"голова"–"хвост", т.е. служит индикатором размеченного объединения. Пред-
полагается, что пара "голова"–"хвост" может быть получена только с помо-
щью вызова функции Cons, создающей экземпляр записи типа S_expr и воз-
вращающей ссылку на эту запись, а содержимое полей Hd и Tl - как результат
вызова функций Head и Tail соответственно.
   Функция Nil не включена в состав модуля HList, так как при использова-
нии предлагаемого представления списка пустой список s естественным обра-
зом представляется пустой ссылкой: s = nil.
   Реализация абстрактного типа Atomic как одного из вариантов записи типа
S_expr привела к появлению в составе модуля HList двух новых функций, ра-
нее не включенных в число базовых:

                     Make_Atom : El → Atomic( El );

                        Get_El : Atomic( El ) → El.

    Первую из них предлагается использовать для конструирования атомарных
S – выражений, а вторую – для получения содержимого поля Atm варианта
Atomic записи типа S_expr.
    Формально это можно представить как изменение данного ранее опреде-
ления абстрактного типа Atomic на определение

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

   Функциональную спецификацию иерархического списка при этом необхо-
димо дополнить правилом А8 для всех t типа El:

                     A8) Get_El ( Make_Atom( t ) ) = t.

   В дополнение к базовым функциям в состав модуля HList включены также
функция копирования списка Copy, полезность которой будет ясна из даль-
нейшего изложения, и процедура Destroy, предназначенная для "сборки мусо-
ра", т.е. освобождения памяти, занятой ненужными уже списочными структу-
рами. После выполнения Destroy ( x ) память, занятая списком x,
освобождается, а значение переменной x становится неопределенным.




                                    25