Чец 1НТЫ. В этом особенно наглядно прослеживается анало-1ежду структурами программ и данных. Каждая рекур-аЯ процедура также должна обязательно содержать рный оператор, чтобы ее выполнение могло когда-нибудь дв [читься. Ясно, что окончание выполнения для процедуры ) f етствует конечности кардинального числа для типа !eij ых.

СЫЛКИ или УКАЗАТЕЛИ

[арактерная особенность рекурсивных структур, которая ает их от основных структур (массивов, записей, мно-йв), -их способность изменять размер. Поэтому для ре- &IBHO определенных структур невозможно установить сированный размер памяти, и поэтому транслятор не кет приписать компонентам такой переменной определен-i адреса. Для решения этой проблемы чаще всего примется метод динамического распределения памяти, т. е. вы-йния памяти для отдельных компонент в тот момент, когда I появляются во время выполнения программы, а не во ре тя трансляции. В этом случае транслятор выделяет фик-[юванный объем памяти для хранения адреса динамически мещаемой компоненты, а не самой компоненты. Напри-) р, генеалогическое дерево, изображенное на рис. 4,2, можнб едставить в виде отдельных, вполне возможно, не распо-{ кенных рядом в памяти записей - по одной для каждого : вовека. Эти записи связываются с помощью адресов, нахо-) 1ЩИХСЯ в соответствующих полях father { отец ) и mother , тать ). Графически это лучше всего изобразить стрелками 5 рис. 4.3).

Следует подчеркнуть, что использование ссылок для реа-

Шцш рекурсивных структур- чисто технический прием, рограммисту необязательно знать об их существовании. Па- ть может выделяться автоматически, как только упомй-8ется новая переменная. Однако если использование ссылок и указателей сделать явным, то можно строить более нообразные структуры данных, чем те, которые можно *Дать лишь с помощью рекурсивных определений. В част- сти, в этом случае можно определять бесконечные , или Циклические, структуры. Кроме того, на одну и ту же под-[РУктуру можно ссылаться из разных мест, т, е. относить

к нескольким разным структурам. Поэтому в современных biKax программирования принято обеспечивать явное ма-Улирование не только данными, но и ссылками на них. J° предполагает четкое разграничение в обозначениях даи-и ссылок на них. Следовательно, нужно ввести типы

bix, значениями которых являются ссылки (указатели)

на другие данные. Для этого мы используем такие 06031, чения:

typer,= tr

В описании типа (4.4) имеется в виду, что значениями тип Тр являются ссылки на данные типа Т. Таким образо1г? стрелка в (4.4) читается как ссылка на . Существенно, 4! тип элементов, на которые ссылаются значения типа т' дан в его определении. Мы говорим, что 1р связан с Т. .

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

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

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

new{p) (4.5)

выделяет память для переменной типа Т, создает ссылку тип^ Тр на эту новую переменную и присваивает значение это ссылки переменной р (см. рис. 4.4). Теперь сама ссылК^ обозначается как р (т. е. является значением ссылочной ременной р). В отличие от этого через р\ обозначается пер^ менная, на которую указывает р (т. е. динамически разЫ щенная переменная типа Т).

r/f) означает последовательность определений полей, содер-jKaniyo хотя бы одно поле типа Т, что приводит к рекурсии.

р: tT [

pt:T

Рис. 4.4. Динамическое размещение переменной р\.

Бее структуры типов, описанных по образу (4.6), представляют собой древовидную (или списковую) структуру, подобную изображенной на рис. 4.3. Недостаток такой структуры- наличие ссылок на элементы, состоящие только из одного поля признака, т. е. не содержащие никакой существенной информации. Применение метода ссылок дает возможность легко экономить память, так как позволяет включить информацию поля признака в значение самой ссылки. Обычно принято расширять область значений типа Тр, добавляя к ней значение, которое не ссылается ни на какой элемент. Мы обозначаем его специальным символом пП и считаем, что nil автоматически является элементом всех ссылочных типов, описанных в программе. Это расширение области ссылочных значений позволяет создавать конечные структуры без явного использования вариантов (условий) в (рекурсивных) описаниях.

Новые формулировки описаний типов данных (4.1) и (4.3), Основанные на явных ссылках, даны соответственно в (4.7) (4.8). Заметим, что в случае (4.8) (который соответствует схеме (4.6)) отсутствует вариант, поскольку р\.known-false Перь выражается как р - nil. Изменение названия типа Prf На person { человек ) отражает новую точку зрения на структуру, связанную с использованием явных ссылок. Вместо

ого чтобы рассматривать вначале данную структуру как це-/ огное образование, а затем выделять в ней подструктуры их компоненты, мы обращаем внимание в первую очередь

Компоненты, а их взаимосвязь (основанная на ссылках)

выше упоминалось, что каждый рекурсивный тип для чтобы его кардинальное число было конечным, должен то ать некоторый вариант. Наиболее типичный случай с^-дан на примере генеалогического дерева: после признака йяимает одно из двух значений (булевских); когда оно Р димает значение false, все прочие компоненты отсут-ствуют. Это изображается такой схемой описаний:

-. - typer-=rceeMH. р then 5(Г) end (4.6)