(d) Пример; 3 + + xyz + - 3xz

Корень

Я) (

±

Рис. 28. Представление полиномов на основе связей, направленных в четыре стороны. Заштрихованные поля узлов обозначают данные, которые не имеют никакого отношения к рассматриваемому вопросу.

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

Алгоритм А {Сложение полиномов). Этот алгоритм складывает полином (Р) с полиномом (Q) при условии, что Р и Q являются указательными переменными, которые указывают на корни различных полиномиальных деревьев, подобных показанным на рис. 28. По завершении работы этого алгоритма полином (Р) останется в исходном неизменном виде, а полином (Q) будет содержать искомую сумму.

А1. [Проверка типа полинома.] Если DOWN(P) = Л (т. е. .если Р указывает на константу), то ни разу не устанавливать или устанавливать Q -f- DOWN(Q) до тех пор, пока не выполнится условие DOWN(Q) = А, и перейти к шагу A3. Если DOWN(P) ф Л, то при DOWN(Q) = А или CV(Q) < CV(P) перейти к шагу А2. В противно.м случае, если CVCQ) = CV(P), установить Р DOWN(P), Q <-DOWN(Q) и повторить этот шаг. Если CV(Q) > CV(P), установить Q DOWN(Q) и повторить этот шаг. (На шаге Al будут найдены два подобных члена в складываемых полиномах нли указано на необходилюсть вставки новой переменной в текущем месте полинома (Q).)

А2. [Вставка по направлению вниз.] Установить R AVAIL, S -f- DOWN(Q). Если S ф А, установить UP(S) <- R, S -f- RIGHT(S) и, если EXP(S) ф О, повторять эту операцию до тех пор, пока не получится EXP(S) = 0. Установить UP(R) <- Q, DOWN(R) DOWN(Q), LEFT(R) R, RIGHT(R) R, CV(R) f-CV(Q) и EXP(R) -f- 0. Наконец, установить CV(Q) CV(P) и DOWN(Q) -f- R, a затем вернуться к шагу Al. ("Фиктивный" нулевой полином вставляется сразу под узлом NODE(Q), чтобы составить пару с полиномо.м, найденным внутри дерева Р. Обработка связей на этом шаге выполняется очень просто и может быть легко выведена с помощью схемы "до и после", как показано в разделе 2.2.3.)

A3..[Пара найдена.] (Здесь Р и Q указывают на соответствующие члены данных полиномов, поэтому можно приступать к сложению.) Установить CV(Cl) <- CV(Q) -bCV(P). Если сумма равна нулю и если EXP(Q) ф О, перейти к шагу А8. Если EXP(Q) = О, перейти к шагу А7.

А4. [Продвижение влево.] (После успешного сложения одного члена перейдем к следующему члену, который нужно сложить.) Установить Р LEFT(P). Если ЕХР(Р) = О, перейти к шагу А6. В противном случае ни разу не устанавливать или устанавливать Q <- LEFT(C)) до тех пор, пока не выполнится условие EXP(Q) < ЕХР(Р). Затем, если EXP(Q) = ЕХР(Р), вернуться к шагу А1.

А5. [Вставка справа.] Установить R <= AVAIL. Установить UP(R) UP(Q), DOWN(R) Л, CV(R) <- О, LEFT(R) <- Q, RIGHT(R) RIGHT(Q), LEFT (RIGHT (R)) R, RIGHT(Q) r- R, EXP(R) EXP(P) и Q R. Вернуться к шагу Al. (Необходимо вставить новый член в текущей строке справа от узла NODE(Q) в соответствии со степенями текущего члена полинома (Р). Как и на шаге .Л.2, эту операцию легче понять, если составить схему "до и после".)

А6. [Возвращение вверх.] (Обход строки полинома (Р) полностью завершен.) Установить Р UP(P).

А7. [Перевод Q на соответствующий уровень.] Если UP(Р) =Л, перейти к шагу ЛИ. В противном случае ни разу не устанавливать или устанавливать Q 4- UP(Q) до тех пор, пока не выполнится условие CV(UP(Q)) = CV(UP(P)). Вернуться к шагу А4.

А8. [Удаление нулевого члена.] Установить R <- Q, Q <- RIGHT(R), S <- LEFT(R), LEFT(Q) <- S, RIGHT(S) <- Q и AVAIL < R. (Удаление выполнено, поэтому удаляется строка полинома (Q).) Если теперь EXP(LEFT(P)) = О и Q = S, перейти к шагу А9; в противном случае вернуться к шагу А4.

А9. [Удаление полинома-константы.] (Аннулирование членов вызвало сокращение полинома до константы, поэтому строка полинома (Q) удаляется.) Установить R 4- Q, Q <- UP(Q), DOWN(Q) DOWN(R), CV(Q) CV(R) и AVAIL R. Установить S DOWN(Q). Если S ф A, установить UP(S) <- Q, S <- RIGHT(S) и, если EXP(S) Ф 0, повторять эту операцию до тех пор, пока не получится EXP(S) = 0.

А10. [Обнаружение нуля?] Если DOWN(Q) = Л, CV(Q) = О и EXP(Q) ф О, установить Р UP(P) и перейти к шагу А8, в противном случае перейти к шагу А6.

All. [Прекращение вьшолнения алгоритма.] Ни разу не устанавливать или устанавливать Q <- UP(Q) до тех пор, пока не получится UPCQ) = Л (с переводом указателя Q на корень этого дерева).

Данный алгоритм вьшолняется гораздо быстрее, чем алгоритм 2.2.4А, если полином (Р) имеет мало членов, а полином (Q) -много, так как в процессе сложения совершать обход всего полино.ма (Q) необязательно. Читателю будет очень полезно вручную выполнить алгоритм А, складывая полином ху - - xyz - + Zxz с полиномом, показанным на рис. 28. (Этот случай пе предназначен для демонстрации эффективности данного алгоритма, но позволяет ознакомиться со всеми его шагами и представить все сложные ситуации, которые следует обработать.) Дальнейшее обсуждение алгоритма А приводится в упр. 12 и 13.

Показанное на рис. 28 представление для полиномов от произвольного количества переменных не является "наилучшим". Например, в главе 8 будет рассмотрен другой формат п])едставления полиномов, а также некоторые арифметические алгоритмы па основе вспомогательного стека, которые по сравнению с алгоритмом А обладают существенными преимуществами в отношении концептуальной простоты. Алгоритм А интересен для нас в основно.м тем, как в нем организована обработка деревьев с большим количеством связен.

УПРАЖНЕНИЯ

* 1. [20] Можно ли восстановить связи LLINK, зная только поля LTAG, INFO и RTAG узлов в последовательном порядке уровней, подобном (8)? (Иначе говоря, не являются ли поля LLINK избыточными в представлении (8) и поля RLINK - в представлении (3)?)

2. [22] (Задача Бсркса, Уоррена и Ранта, Afath. Сотр. 8 (1954), 53-57.) Пусть деревья (2) хранятся в памяти в прямом порядке с указанием степеней

DEGREE 2 0 1 0 3 1 0 1 0 0 INFO ABCKDEHFJG [Ср. с (9), где они приведены в обратном порядке.] Создайте алгоритм, аналогичный алгоритму F, для оценки локально определенной функции узлов, выполнив обход этого прсдставлс1шя справа налево.