BI. Инициализация

ВЗ. Соответствие найдено

Вторично.

Наверху

В5. Продвижение вверх по дереву

Ошибка

Да/ В6. Ак соот-

ветствует

Рис. 40. Алгоритм для проверки ссылок в языке COBOL.

Р 7 А, установить S Р и А; 0. (S - переменная-указатель, значения которой меняются от Р и ведут вверх по дереву по связям PARENT; к - целочисленная переменная, которая принимает значения от О к гг. На практике указатели Ро,... ,Р„ часто содержатся в связанном списке, и тогда вместо к используется переменная-указатель, которая совершает обход этого списка; см. упр. 5.)

83. [Соответствие найдено?] Если А; < гг, то перейти к шагу В4. В противном случае найдена соответствующая позиция таблицы данных. Если Q Л, то найдена вторая такая позиция, и поэтому нужно отослать сообщение об ошибке. Установить Q Р, Р PREV(P) и перейти к шагу В2.

84. [Увеличение к!\ Установить к к + \.

85. [Продвижение вверх по дереву.] Установить S PARENT(S). Если S = А, то соответствие найти не удалось; установить Р = PREV(P) и перейти к шагу В2.

86. \Ak соответствует?] Если NAME(S) = Р, перейти к шагу ВЗ; в противном случае перейти к шагу Во.

Обратите внимание, что связи CHILD и SIB в этом алгоритме не использовались.

Третий, и последний, из нужных нам алгоритмов имеет отношение к ко.манде MOVE CORRESPONDING. Прежде чем приступить к созданию алгоритма, нужно четко сформулировать его назначение. В языке COBOL выражение

MOVE CORRESPONDING а ТО Д,

где а и - ссылки наподобие (6) на элементы данных, обозначает сокращенную запись множества всех выражений типа

MOVE о! ТО

для которых существует такое целое число гг > О и такие п имен Ло, Aj,..., A„ i, что

ос = Ло OF Al OF ... OF Л,г 1 OF a, = Ло OF Al OF ... OF Л„-1 OF

и либо a, либо является простейшим элементом (а не группой элементов). Более того, необходимо, чтобы в (8) была указана полная квалификация первых уровней, а именно - что Aj+i является родителем Aj для О < j < гг. а и должны располагаться в дереве на п уровней ниже, чем q и .

Для рассматриваемого здесь примера (4) выражение

MOVE CORRESPONDING А ТО Н

является сокращенной формой записи выражений

MOVE В OF А ТО В OF Н

MOVE G OF F OF А ТО G OF F OF Н

АлгоритА! для распознавания соответствующих пар а, 0 несмотря на свою простоту довольно интересен, т. е. необходимо совершить обход дерева с корнем а в прямом порядке, одновременно выискивая в дереве 0 совпадающие имена и пропуская подп,еревья, в которых появление соответствующих элементов невозможно. Имена Ао,. •., Ап-\ из (8) располагаются в обратном гюрядке: A„ i,..., Ао.

Алгоритм С [Поиск соответствующих пар). Для заданных РО и Q0, которые указывают на позиции таблицы данных для а и 0 соответственно, этот алгоритм последовательно находит все пары указателей (P,Q) на элементы [a,l3), удовлетворяющие упомянутым выше требованиям.

С1. [Инициализация.] Установить Р РО, Q <- Q0. (В оставшейся части этого алгоритма указательные переменные Р и Q совершают обход деревьев с корнями а и Р соответственно.)

С2. [Простейший э.лемент?] Если CHILD(Р) = А или CHILD (Q) = Л, то вывести (Р, Q) как одну из искомых пар и перейти к шагу С5. В противном случае установить Р <г- CHILD(Р), Q <г- CHILD (Q). (На этом шаге Р и Q указывают на элементы а и /?, удовлетворяющие (8), а команду MOVE а ТО Р необходимо вьшолнять тогда и только тогда, когда либо а, либо Р (или оба сразу) - простейший элемент.)

СЗ. [Сравнение имен.] (Р и Q указывают на элементы данных, которые соответственно имеют квалификацию в виде

Ло OF Al OF ... OF Л„ 1 OF a

Во OF Al OF ... OF Л„ 1 OF p.

Теперь задача заключается в том, чтобы узнать, можно ли сделать так, чтобы Во = Ао, проверяя все имена в группе Ai OF ... OF A„-i OF p.) Если NAME(P) = NAME(Q), to перейти к шагу C2 (найдено совпадение). В противном случае, если SIB(Q) ф Л, установить Q +- SIB(Q) и повторить шаг СЗ. (Если SIB(Q) = Л, значит, в этой группе нет соответствующего имени и следует перейти к ша-гу С4.)

С4. [Продвижение.] Если SIB(P) ф Л, то установить значения Р <г- SIB(P), Q CHILD(PARENT(Q)) и вернуться к шагу СЗ. Если SIB(P) = Л, то установить Р <- PARENT(Р) и Q PARENT(Q).

С5. [Готово?] Если Р = РО, то прекратить выполнение алгоритма; в противном случае перейти к шагу С4.

Блок-схема этого алгоритма показана на рис. 41. Доказательство корректности алгоритма можно легко получить с помощью метода индукции по размеру обрабатываемых деревьев (см. упр. 9).

Cl. Инициализация

Простейший \элемент?

Соответствие найдено

Pv-SIB(P)

Рис. 41. Алгоритм для выполнения команды MOVE CORRESPONDING.

Теперь рассмотрим способы применения пяти полей связи (PREV, PARENT, NAME, CHILD и SIB) в алгоритмах В и С. Замечательно то, что эти связи образуют "полный набор" в том смысле, что алгоритмы В и С действительно выполняют минимальный объем работы при продвижении по таблице данных. И всякий раз, когда нужно сослаться на другую позицию таблицы данных, ее адрес сразу же становится доступным, поэтому нет необходимости проводить дополнительный поиск. Трудно представить, как можно было бы сделать алгоритмы В и С более быстрыми, включив в таблицу дополнительную информацию о связях (см., однако, упр. 11).

Каждое поле связи может рассматриваться как ключ к этой программе, который используется для ускорения работы алгоритмов, (Конечно, алгоритм для построения таблиц, т. е, алгоритм А, выполняется медленнее, поскольку он имеет больше связей, которые необходимо заполнить. Но таблица строится лишь один раз.) С другой стороны, ясно, что в построенной вьпце таблице данных содержится гораздо больше избыточной информации. Посмотрим, что произойдет, если удалить некоторые поля связи.

Связь PREV, хотя она и не используется в алгоритме С, имеет большое значение в алгоритме В и, похоже, является существенной частью любого компилятора языка COBOL, за исключением случаев, когда требуется выполнять длительные операции поиска. Следовательно, поле, которое связывает все элементы с одинаковыми именами, имеет большое значение для эффективной работы. Поэтому стратегию действий э такой ситуации можно слегка модифицировать и вместо связи А в конце каждого списка применить циклическое связывание. Но этого не стоит делать, когда поля связи не изменяются и не удаляются.

Связь PARENT используется в алгоритмах В и С, хотя можно обойтись и без нее, если в алгоритме С применить вспомогательный стек или добавить связь SIB так, чтобы задействовать связи-нити (как в разделе 2.3.2). Таким образом, становится ясно, что связь PARENT используется только в алгоритме В. Если бы поле SIB было связью-нитью, чтобы элементы со значением поля связи SIB = Л содержали вместо него значение SIB = PARENT, можно было бы найти родителя любого элемента данных, следуя по связям SIB, Добавленные связи-нити можно отличить либо с помощью нового поля TAG в каждом узле, в котором указывалось бы, что поле SIB содержит связь-нить, либо с помощью условия SIB(P) < Р, если позиции таблицы данных хранятся последовательно в памяти в порядке появления, Это значит, что на шаге В5 придется выполнить короткий поиск, а сам алгоритм соответственно станет работать медленнее.

Связь NAME используется в этих алгоритмах только на шагах В6 и СЗ. В обоих случаях можно было бы вьшолнить проверку NAME(S) = Pk и NAME(P) = NAME(Q)