иначе, если бы связь МАМЕ отсутствовала (см. упр. 10), ко это существенно замедлило бы выполнение вкутреИких циклов в алгоритмах В и С. Ясно, что здесь скова имеет место компромисс между экономией пространства для связи и скоростью выполнения алгоритмов. (Скорость работы алгоритма С ке так уж важна для компиляторов языка COBOL, если рассматривать типичные способы употребления команд MOVE CORRESPONDING. Однако алгоритм В должен работать быстро.) Известно, что связи NAME используются и для выполнения других важных задач в компиляторе языка COBOL, особенно при выводе диагностической информации.

Алгоритм А постепенно создает таблицу данных, причем никогда не приходится возвращать узлы в область свободной памяти. Поэтому позиции таблицы данных обычно располагаются в последовательных ячейках памяти в порядке появления элементов данных в исходной программе на языке COBOL, Таким образом, в нашем примере (5) ячейки А1, ВЗ, ,,, будут располагаться одна за другой. Такой последовательный характер размещения ячеек в таблице данных позволяет сущестаенно упростить работу. Например, связь CHILD каждого узла либо равна Л, либо указывает на узел, который следует сразу же за ним, поэтому поле CHILD можио сократить до размера 1 бит. Или поле CHILD можно удалить и вместо него проверить условие PARENT(Р -I- с) = Р, где с--размер узла в таблице данных.

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

Интересно отметить, что по крайней мере полдюжины разработчиков компиляторов COBOL в начале 60-х годов независимо пришли к одному способу организации таблицы данных с помощью пяти связей (или четырех из пяти, так как связь CHILD обычно не используется). Впервые описанив такого метода было опубликовано Г, В, Лоусоном (мл,) (Н, W. Lawaon, Jr.) [см. АСМ National Conference Digest (Syracuse, N.Y.: 1962], Однако Дэвид Дам (David Dahna) в 1965 году предложил оригинальный метод, который позволяет получить тот же результат, что и при работе с алгоритмами В и С, но с использованием двух полей связи и последовательного распределения позиций в таблице данных без существенного снижения скорости выполнения (см, упр, 12-14).

УПРАЖНЕНИЯ

1. [00] Бели конфигурации данных в языке COBOL рассматривать как древовидные структуры, то в каком порядке они записаны; в прямом, обратном или ни в одном из них?

а. [10] Оцените время выполнения алгоритма А,

3. [22] Структуры данных языка PL/I подобны структурам языка COBOL, но в них допустима любая последовательность номеров уровней. Например, последовательность

1 А 1 А

3 в 2 в

Б С эквивалентна последовательности 3 С

4 D 3d

2 Е 2 Е

В итоге правило (а) изменяется таким образом; "Элементы группы должны иметь невоз-растающую последовательность номеров уровней, причем все они должны быть больше номера уровня группы данной группы". Как необходимо изменить алгоритм А, чтобы

выполнить переход от соглашений, принятых для языка COBOL, к соглашениям, принятым для языка PL/I?

► 4. [S6] Алгоритм А не позволит обнаружить ошибку, если программист в COBOL-программе нарушит упомянутое в этом разделе правило (с). Как следует изменить алгоритм А, чтобы принимались только те структуры, которые удовлетворяют правилу (с)?

5. [20] На практике алгоритм В может получать из входного потока связанный список ссылок на таблицу символов, а не то, что прежде называлось "Ро, Pi, , Рп" Пусть Т является акой указательной переменной, что

INFO(T) =Ро, INFO (RLINK (Т)) =Pi, INFO (RLINKf"(Т)) = Pn, RLINk"+(Т) = A.

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

6. [23] В языке PL/I допускается использование структур данных, которые во многом подобны структурам языка COBOL, но без применения ограничения (с). Вместо этого получим правило, по которому квалифицированная ссылка (3) является однозначной, если указана "полная" квалификация, т. е. если Aj+i -родитель Aj для О < j < п и если An не имеет родителя. Ограничение (с) теперь сведено к простому условию, согласно которому никакие два элемента данных группы не могут иметь одно и то же имя. На второе появление СС в (2) можно было бы недвусмысленно сослаться с помощью ссылки "СС OF АА", а на три элемента данных

2 А 3 А

можно было бы в соответствии с соглашениями, принятыми в языке PL/I, сослаться в такой форме: "А", "А OF А", "А OF А OF А". [Замечание. На самом деле "OF" заменяется точкой в языке PL/L а порядок является реверсивным. Так, вместо "СС OF АА" в языке PL/I используется обозначение "АА. СС", но для данного упражнения это несущественно.] Покажите, как можно модифицировать алгоритм В, чтобы он удовлетворял соглашениям, принятым для языка PL/L

7. [15] Что означает в языке COBOL команда MOVE CORRESPONDING SALES ТО PURCHASES по отношению к структуре данных (1)?

8. [10] При каких условиях команда MOVE CORRESPONDING а 10 /3 означает то же самое, что и команда MOVE се ТО /3, в соответствии с данным в этом разделе определением?

9. [М23] Докажите корректность алгоритма С.

10. [23] (а) Как можно было бы выполнить проверку условия NAME(S) = Рк на шаге В6, если бы в узлах таблицы данных не было связи NAME? (b) Как можно было бы выполнить проверку NAME(P) = NAME(Q) на шаге СЗ, если бы в узлах таблицы данных не было связи NAME? (Предположим, что все другие связи присутствуют, как описано в этом разделе.)

► 11. [23] Какие дополнительные связи или изменения в стратегии создания алгоритмов могли бы ускорить работу алгоритма В или С?

12. [25] (Задача Д. М. Дама (D. М. Dahm).) Рассмотрим представление таблицы данных в последовательных ячейках памяти с помощью всего двух связей для каждого элемента данных:

PREV (так же, как в данном разделе);

SCOPE (связь с последним простейшим элементом в данной группе).

Получим SCOPE (Р) = Р тогда и только тогда, когда NODE(P) представляет собой простейший элемент. Например, таблица данных (5) будет заменена таким представлением.

(Ср. с (5) из раздела 2.3.3.) Обратите внимание, что NODE(P) является частью дерева под узлом NODE(Q) тогда и только тогда, когда Q < Р < SCOPE(Q). Создайте алгоритм, который выполняет функции алгоритма В, если таблица данных имеет такой формат.

► 13. [24] Предложите вместо алгоритма А другой алгоритм для работы с таблицей данных с форматом, описанным в упр. 12.

► 14. [28] Предложите вместо алгоритма С другой алгоритм для работы с таблицей данных с форматом, описанным в упр. 12.

15. [25] (Задача Дэвида С. Вайса (David S. Wise).) Измените алгоритм А так, чтобы для стека не использовалось никакое дополнительное пространство. [Указание. Поля SIB всех узлов с указателями в стеке в этой формулировке равны Л.]