Несколько элегантных алгоритмов копирования и перемещения Списков основаны на гораздо более слабых предположениях о представлении Списка; см. D. W. Clark, САСМ 19 (1976), 352-354; J. М. Robson, САСМ 20 (1977), 431-433.

11. Выполним это упражнение вручную с помощью карандаша и бумаги, хотя можно было бы привести и более формальное решение. Сначала зададим уникальное имя (например, с помощью заглавных букв) для каждого Списка рассматриваемого множества. В данном примере получим А = {а:С,Ь,а: F), F = {b:D), В = {а: F,b,a: Е), С = (6:G), G = (а: С), D = (a:F), Е - (b:G). Теперь построим список из пар имен Списков, эквивалентность которых необходимо доказать. Последовательно будем добавлять пары в этот список до тех пор, пока не получим противоречие из-за наличия противоречивых пар на первом уровне (тогда исходные Списки не эквивалентны), или до тех пор, пока из списка пар не будут следовать никакие другие пары (тогда исходные Списки не эквивалентны). В данном примере список пар в исходном состоянии содержит только заданную пару, АВ\ затем в него будут добавлены пары CF, EF (при сравнении А к В), DG (следует из CF), после чего получится непротиворечивое множество.

Для доказательства корректности этого метода обратите внимание на то, что (i) при получении ответа "не эквивалентны" заданные Списки не эквивалентны; (ii) если заданные Списки не эквивалентны, то будет получен ответ "не эквивалентны"; (iii) работа алгоритма всегда завершается.

12. Если список AVAIL содержит N узлов, где N - константа, выбор которой обсуждается ниже, то следует вызвать другую сопрограмму, которая использует вычислительные ресурсы вместе с основной программой и выполняет следующие действия: (а) маркирует все N узлов списка AVAIL; (b) маркирует другие узлы, которые свободны для этой программы; (с) связывает все немаркированные узлы вместе для подготовки нового списка AVAIL, который будет использоваться при опустошении текущего списка AVAIL; (d) сбрасывает маркировочные биты во всех узлах. Нужно выбрать такое N и такое отношение разделения времени, чтобы операции (a)-(d) гарантированно завершались до того, как N узлов будут извлечены из списка AVAIL, даже если основная программа выполняется достаточно быстро. При этом на этапе (Ь) необходимо убедиться в том, что маркированы все узлы, "доступные для данной программы", по мере ее выполнения; остальные подробности здесь опускаются. Если в созданном на этапе (с) списке содержится менее N узлов, то в конце концов может потребоваться прекратить работу приложения из-за того, что в памяти будет исчерпано все свободное пространство. Более подробные сведения по этой теме приводятся в работах Guy L. Steele Jr., САСМ 18 (1975), 495-508; P. Wadler, CACM 19 (1976), 491-500; E. W. Dijkstra, L. Laniport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, CACM 21 (1978), 966-975; H. G. Baker, Jr., CACM 21 (1978), 280-294.

РАЗДЕЛ 2.4

1. В прямом порядке.

2. Оно прямо пропорционально количеству создаваемых элементов таблицы данных.

3. Заменить операции шага А5 такими действиями.

А5. [Удаление верхнего уровня.] Удалить верхний элемент стека; и если номер нового уровня на вершине стека равен > L, то пусть (Ll, Р1) - новый элемент на вершине стека. Повторить этот шаг. В противном случае установить SIB(Pl) <- Q. Тогда пусть (L1,P1) является новым элементом на вершине стека.

4. (Решение Дэвида С. Вайса (David S. Wise).) Правило (с) нарушается тогда и только тогда, когда существует элемент данных, полная квалификация Ао OF ... OF An которого в языке COBOL также является ссылкой на некоторый элемент данных. Так как и родитель

Al OF ... OF An должен удовлетворять правилу (с), можно предположить, что этот другой элемент данных является наследником некоторого родителя. Значит, алгоритм А следует расширить таким образом, чтобы при добавлении в таблицу данных каждого нового элемента данных выполнялась проверка, является ли его родитель предком любого другого элемента данных с таким же именем или есть ли в стеке родитель любого другого элемента с таким же именем. (Когда родитель равен Л, он является предком всех других элементов и всегда располагается в стеке.)

С другой стороны, если оставить алгоритм А в прежнем состоянии, программист при выполнении COBOL-программы получит сообщение об ошибке со стороны алгоритма В при попытке использования недопустимого элемента. И только при выполнении команды MOVE CORRESPONDING элементы данных могут применяться без вывода сообщения об ошибке.

5. Следует выполнить такие изменения.

На шаге команду заменить командой

81 P<-LINK(Po) Р<-LINK (INFO (Т))

82 А; <- О К <- Т

83 к<п RLINK (К) / Л

84 ki-k + 1 K<-RLINK(K) Вб MnE(S)Pk NAME(S) = INFO(K)

6. Простое изменение алгоритма В позволяет выполнять поиск только полных ссылок (если к = п и PARENT(S) / Л на шаге ВЗ или если NAME(S) / Рк на шаге Вб, то в таком случае следует установить Р <- PREV(P) и перейти к шагу В2). Основная идея здесь заключается в том, чтобы сначала выполнить модифицированную версию алгоритма В, а затем, если ссылка Q все еще равна Л, - его немодифицированную версию.

7. MOVE MONTH OF DATE OF SALES TO MONTH OF DATE OF PURCHASES. MOVE DAY OF DATE OF SALES TO DAY OF DATE OF PURCHASES. MOVE YEAR OF DATE OF SALES TO YEAR DF DATE OF PURCHASES. MOVE ITEM OF TRANSACTION OF SALES TO ITEM OF TRANSACTION OF PURCHASES. MOVE QUANTITY OF TRANSACTION OF SALES TO QUANTITY OF TRANSACTION OF PURCHASES. MOVE PRICE OF TRANSACTION OF SALES TO PRICE OF TRANSACTION OF PURCHASES. MOVE TAX OF TRANSACTION OF SALES TO TAX OF TRANSACTION DF PURCHASES.

8. Тогда и только тогда, когда q или Р является простейшим элементом. (Может быть, следует отметить, что автору не удалось должным образом обработать этот случай в первом черновом варианте алгоритма С, что существенно усложнило этот алгоритм.)

9. Если ни q, ни р не является простейшим элементом, то команда MOVE CORRESPONDING q ТО эквивалентна набору команд MOVE CORRESPONDING А OF q ТО А OF , выполненному над всеми именами А, общими для групп а и р. (Этот способ определения элегантнее, чем более традиционное и тяжеловесное определение команды MOVE CORRESPONDING, которое предлагается в тексте.) Можно убедиться, что алгоритм С удовлетворяет такому определению, доказав по индукции, что после выполнения шагов С2-С5 в конце концов получится Р = РО и Q = Q0. Далее доказательство проводится точно так, как оно выполнялось много раз прежде, в "индукции по дереву" (см. например, доказательство алгоритма 2.3.IT).

10. (а) Установить S1 <- ЫШСРк). Затем повторно ни разу не устанавливать или устанавливать S1 •(- PREV(Sl) до тех пор, пока либо S1 = Л (NAME(S) / Рк), либо S1 = S (NAME(S) = Рк). (Ь) Установить Р1 <- Р, а затем ни разу не устанавливать или устанавливать Р1 <- PREV(Pl) до тех пор, пока не выполнится условие PREV(Pl) = Л. Выполнить аналогичную операцию для переменных Q1 и Q; затем проверить Р1 = Q1. Иначе, если позиции таблицы данных упорядочены так, что PREV(P) < Р для всех Р, более быструю проверку, очевидно, можно выполнить следующим образом: выяснить, что Р > Q, или.

наоборот, пройти по связям PREV большего из них и обнаружить, встречается ли меньший из них.

11. Незначительного повышения скорости выполнения шага С4 можно достичь за счет добавления нового поля связи SIBl(P) = CHILD(PARENT(Р)). Увеличение скорости будет более существенным, если модифицировать связи CHILD и SIB таким образом, чтобы NAME(SIB(P)) > NAME(P). Это позволит значительно ускорить поиск на шаге СЗ, поскольку для этого потребуется выполнить только один проход по каждому семейству для поиска подобных членов Следовательно, такое изменение позволяет исключить единственную операцию поиска в алгоритме С. Алгоритмы А и С можно легко модифицировать с предложенной интерпретацией, а читателю будет полезно выполнить ее в качестве интересного упражнения. (Однако, если рассмотреть относительную частоту команд MOVE CORRESPONDING и обычный размер семейных групп, полученное в результате повышение скорости будет не таким уж значительным после трансляции реальных COBOL-программ.)

12. Шаги В1-ВЗ остаются прежними, а другие шаги будут выглядеть так

84. Установить fc <- fc -Н 1, R <- LINK(Pfc).

85. Если R = Л, то соответствия нет; установить Р <- PREV(P) и перейти к шагу В2. Если R < S < SCOPE(R), установить S 4- R и перейти к шагу ВЗ. В противном случае установить R <- PREV(R) и повторить шаг В5.

Этот алгоритм не адаптирован для соглашений, принятых для языка PL/I в упр. 6.

13. Используйте тот же алгоритм, но без операций установки связей NAME, PARENT, CHILD и SIB. При каждом удалении верхнего элемента стека на шаге А5 следует устанавливать SCOPE (Р1) 4- Q - 1. После исчерпания входного потока на шаге А2 следует просто установить L 4- О и продолжить выполнение алгоритма. Затем необходимо прекратить выполнение алгоритма, если L = О на шаге А7.

14. Шаги приведенного ниже алгоритма со вспомогательным стеком пронумерованы так же, как шаги алгоритма С, приведенного в данном разделе, для упрощения их сравнительного анализа.

Cl. Установить Р РО, Q Q0 и опустошить стек.

С2. Если SCOPE(Р) = Р или SCOPE (Q) = Q, вывести (Р, Q) как одну из искомых пар и перейти к шагу С5. В противном случае поместить (Р, Q) в стек и установить Р<-Р-Н1, Q<-Q-t-l.

СЗ. Определить, указывают ли Р и Q на элементы с тем же именем (см. упр 10, (Ь)). Если указывают, то перейти к шагу С2. Если не указывают, то поместить (Р1, Q1) в верхнюю часть стека; если SCOPE(Q) < SCOPE(Ql), то установить Q <- SCOPE(Q) + 1 и повторить шаг СЗ

С4. Поместить (Р1, Q1) в верхнюю часть стека. Если SCOPE(P) < SCOPE(Pl), то установить Р <-SCOPE(P)-t-l, Q <-Ql-t-1 и перейти к шагу СЗ. Если8С0РЕ(Р) =SC0PE(P1), то установить Р 4- Р1, Q 4- Q1 и удалить верхний элемент стека.

С5. Если стек пуст, прекратить выполнение алгоритма. В противном случае перейти к шагу С4. I

РАЗДЕЛ 2.5

1. В столь благоприятных ситуациях можно воспользоваться стековыми операциями следующим образом. Пусть область пула памяти имеет адреса от О до М - 1 и пусть AVAIL указывает на нижний свободный адрес. При выделения N слов, если AVAIL -t- N > М, сообщается о невозможности выделения необходимого количества памяти, в противном случае