ИЗ любого фиксированного описания не очевидна.

type expression =з record о/?: operator;

opdl, opdl: perm end;

type term record r (4

if t then (id: alfa)

else (sub: [expression) -

tyfeperson record name: alfa;

father, mother: [person (4.8) end

-.труктура данных, представляющая генеалогическое де-рево, показанная на рис. 4.2 и 4.3, здесь вновь изображаете. на рис. 4.5, где ссылки на неизвестных лиц обозначены через

nil. Очевидно, что при этом достигается значительная экономия памяти.

Обращаясь вновь к рис. 4.5, предположим, что Фред и Мэ-i ри - брат и сестра, т. е. имеют i общих отца и мать. Такой случай легко выразить, заменив два значения nil в соот-, ветствующих полях двух запи- сей (mother- у Фреда и /а/< her - у Мэри). Реализация, прн которой концепция ссылок скрыта или используются другие приемы управления памятью, вынуждала бы программиста представить записи Адама и Евы по два раза каждую. Хотя при просмотре дан-ных не имеет значения, представлены эти два идентичны-ч отца (или две матери) двумя записями или одной, разница важна, когда допускается выборочное изменение. Когда ссылки используются как явные элементы данных, а не как скрытые вспомогательные средства реализации, программист может явно указывать случаи разделения памяти (в смьк ле совместного владения какой-либо областью памяти).

Другое следствие использования явных ссылок - возмоЖ ность определять и обрабатывать циклические структур! данных. Разумеется, эта дополнительная гибкость не тольк^ увеличивает возможности, но и требует большей осторо* ности, так как работа с циклическими структурами легк может привести к бесконечным вычислениям.

Рис. 4.5. Структура с nil.

-fo, ЧТО МОЩНОСТЬ и гибкость тесно связаны с опасностью ,йбочного использования, - явление, широко известное программировании. Особенно это касается оператора без- яовного перехода (goto). Возможно, продолжая аналогию р#ДУ структурами программ и структурами данных, чисто ggypCHBHbie структуры данных можно поместить на уровень, оответствующий процедуре, тогда как введение ссылок JjjjiO-CpaBHHTb с использованием операторов (goto). Так как с помощью оператора (goto), можно строить любые программные схемы (включая циклы), так и с помощью ссы-можно создавать структуры данных любого вида (в том чйсле циклические). Соответствия между структурами программ и структурами данных указаны в табл. 4.1.

Таблица 4.1. Соответствия между структурами программ и данных

Схема строения

Оператор

Тип данных

Атомарный элемент Перечисление Известное число повторений Выбор

Неизвестное число повторений

Рекурсия

Универсальный граф

Присваивание Составной оператор Оператор цикла с параметром Условный оператор

Оператор цикла с предусловием или постусловием

Оператор процедуры

Оператор безусловного перехода

Скалярный тип

Запись с вариантами, объединение типов

Последовательность, или файл

Рекурсивный тип данных

Структура, связанная ссылками

В гл. 3 было показано, что итерация есть частный случай рекурсии и что вызов рекурсивной процедуры Р, описанной По схеме

)rocedure Р; )egin

if В then begin Ро; Р end

(4.9)

Где Ро - оператор, не содержащий Р, эквивалентен итеративному оператору

while В do Ро

Аналогии, указанные в табл. 4.1, позволяют обнаружить кую же связь между рекурсивными типами данных и после

typeT = record If end

If В then(4: To, t: T)

где To - тип, не содержащий Т, эквивалентен файловому thav данных

file of Го

и может быть им заменен. Отсюда видно, что рекурсию можно заменять итерацией в программах и описаниях данных в том (и только в том) случае, если имя процедуры или типа появляется только один раз в конце (или начале) своего описания.

-Остальная чшггь этой главы посвящена созданию и обработке структур данных, компоненты которых связаны явными ссылками. Особое значение придается структурам простой (][)ормы; приемы работы с более сложными структурами можно получить из способов работы с основными видами структур. Эти виды - линейные списки, или цепочки, самый простой случай, а также деревья. Предпочтение, которое мы оказываем этим строительным блокам , не означает, что на практике не встречаются более сложные структуры. В действительности следующая история, напечатанная в цюрихской газете в июле 1922 г., доказывает, что иррегулярность может появляться даже в структурах, которые обычно считаются образцом регулярности, таких, как (семейные) деревья. В этой истории говорится о человеке, который так описывает несчастье своей жизни:

Я женился на вдове, у которой была взрослая дочь. Мой отец, который довольно часто нас навещал, влюбился в мою падчерицу и женился на ней. Следовательно, мой отец стал моим зятем, а моя падчерица стала моей матерью. Спустя несколько месяцев, моя жена родила сына, который стал шурином моего отца и одновременно моим дядей. У жены моего отца, то есть моей падчерицы, тоже роди-пся сын. Таким образом, у меня появился брат и одновременно внук. Моя жена является моей бабушкой, так как она мать моей матери. Следовательно, я муж моей жены и одновременно ее внук, другими словами, я - свой собственный дедушка.

4.3. линейные списки

4.3.1. Основные операции

. Самый простой способ соединить, или связать, множество элементов - это расположить их линейно в списке, или в О'Ч^ реди.. В этом случае каждый элемент содержит только оДнУ ссылку, связывающую его со следующим элементом списка-

довательностью. В самом деле, рекурсивный тип, опредед^ мый по схеме ., .