AOP_Tom1 (1021736), страница 101
Текст из файла (страница 101)
В заключение раздела приведем пример модифицированной дважды связанной циклической структуры, которая используется для рассмотренной выше задачи, а именно — для полиномиэльной арифметики. Алгоритм 2.2.4А выполняет сложение одного полинома с другим прн условии, что оба полинома представлены в виде циклических списков. А остальные алгоритмы того же раздела соответствуют другим операциям над полиномами.
Полиномы в разделе 2.2.4 содержали не более трех переменных, в то время как при работе с болыпим количеством переменных удобнее использовать не линейный список, а древовидную структуру. Полипом либо представляет гобой константу, либо имеет вид дух ' э<э<я где х — переменная, и > О, О = ее < е, « .. еьч де,..., д„— полиномы по другим переменным, символьные имена которых в алфавитном порядке располагаются до переменной х, а полиномы д„..., д„отличны от нуля.
Это рекурсивное определение полиномов подходит для представления деревьев, как показано на рнс. 28. Узлы имеют по шесть полей, которые в случае использования компьютера Н1Х можно разместить в трех словах: (17) Здесь 1.ЕРТ, НТСНТ, ОР и РОИ~ †свя, ЕХР— целое число, которое указывает степень, а СЧ вЂ” либо константа (коэффициент), либо символьное нмя переменной. Для корневого узла ОР = Л, ЕХР = О, ЕЕРТ = Е16НТ = * (связан с самим собой). Е' Я у о ~о о о о Р»' о л м о х о Б х 01 + Ф, + 4л о Ф !! ь о х О х й о з й ! ч + Ч + л о о о о о о.
= Ы о. о х х, д Б о о о о' о х й о И И М Ф о х о й о о о О О О О х о х о Я о о 3 о х о х Ю (Ч О» с~ В следующем алгоритме показано, как в таком дереве со связями по четырем направлениям можно организовать операции обхода, вставки и удаления. А потому он заслуживает особого внимания. Алгоритм А (Слоэсение полнноалов). Этот алгоритм складывает полипом (Р) с полиномом (Ц) при условии, что Р и Ц являются указательными перел~сивыми, которые указывают на корни различных полнномиальных деревьев, подобных показанным на рис. 28. По завершении работы этого алгоритма полипом (Р) останется в исходном неизменном виде, а полнном (Ц) будет содержать искомую сумму. А1.
[Проверка тина полинома.] Если ООММ(Р) = Л (т. е .если Р указывает на константу), то ни разу не устанавливать нли устанавливать Ц е- ООЫМ(Ц) до тех пор, пока не выполнится условие 00ЧМ(Ц) = Л, и перейти к шагу АЗ. Если ООММ(Р) ~ Л, то прн ООЧМ(Ц) = Л нлн СЧ(Ц) < СЧ(Р) перейти к шагу А2. В противном случае, если СЧ(Ц) = СЧ(Р), установить Р е- ООЫМ(Р), Ц е- ООЫМ(Ц) и повторить этот шаг. Если СЧ(Ц) > СЧ(Р), установить Ц е- ООЧМ(Ц) и повторить этот шаг. (На шаге А1 будут найдены два подобных члена в складываемых полиномах или указано на необходимость вставки новой переменной в текущем месте полинома (Ц),) А2.
[Вставка по направлению вниз,] Установить К ~ АЧА1Е, Я е- ООЫМ(Ц). Если Я ~ Л, установить ОР(Я) е- К, Я +- К10НТ(Я) и, если ЕХР(Я) ф О, повторять эту операцию до тех пор, пока не получится ЕХР(Я) = О. Установить ОР(К) +- Ц, ООММ(К) +- НОЕМ(Ц), 1.ЕРТ(К) +- К, К10НТ(К) е- К, СЧ(К) +- СЧ(Ц) и ЕХР(К) +- О, Наконец. установить СЧ(Ц) е- СЧ(Р) и ООЧМ(Ц) +- К. а затем вернуться к шагу А1. (кФиктивныйч нулевой полипом вставляется сразу под узлом МООЕ(Ц), чтобы составить пару с полиномом, найденным внутри дерена Р.
Обработка связей на этом шаге выполняется очень просто и может быть легко выведена с помощью схемы "до и после", как показано в разделе 2.2.3.) АЗ..[Пара найдена.] (Здесь Р и Ц указывают на соответствующие члены данных полиномов, поэтому можно приступать к сложению.) Установить СЧ(Ц) е— СЧ(Ц) +СЧ(Р). Если сулллла равна нулю и если ЕХР(Ц) ф. О, перейти к шагу АЯ. Если ЕХР(Ц) = О, перейти к шагу А7. А4. [Продвижение влево.] (После успешного сложения одного члена перейдем к следующему члену, который нужно сложить.) Установить Р е — 1.ЕГТ(Р).
Если ЕХР(Р) = О, перейтн к шагу Аб. В противном случае ни разу не устанавливать или устанавливать ц +- АЛЕЕТ(Ц) до тех пор, пока не выполнится условие ЕХР(Ц) < ЕХР(Р). Затем, если ЕХР(Ц) = ЕХР(Р), вернуться к шагу А1. Аб. [Вставка справа.] Установить К ~ АЧА1Е. Установить ОР(К) +- ОР(Ц), ООЫМ(К) е- Л, СЧСК) е- О, АЛЕЕТ(К) +- Ц, К10НТ(К) е- К10НТ(Ц), АЛЕЕТ(К10НТ(К) ) е — К, К10НТ(Ц) +- К, ЕХР(К) е- ЕХР(Р) и Ц е- К. Вернуться к шагу А1. (Необходилю вставить новый член в текущей строке справа от узла МОНЕ(Ц) в соответствии со степенями текущего члена полинома (Р). Как и на шаге А2, эту операцию легче понять, если составить схему "до н после".) А6.
[Возвращение вверх.] (Обход строки полинома (Р) полностью завершен.) Установить Р е- ОР(Р). АТ. [Перевод Ц на соответствующий уровень.] Если СР(Р) = Л, перейти к шагу А11. В противном случае ни разу не устанавливать или устанавливать Ц е- ОР(Ц) до тех пор, пока не выполнится условие СЧ(ОР(Ц) ) = СЧ(ОР(Р) ). Вернуться к шагу А4. А8.[Удаление нулевого члена.] Установить й е- Ц, Ц +- М1СНТ(Н), Б е- 1.ЕРТ(Н), 1.ЕРТ(Ц) е- Б, Н1СНТ(Б) +- Ц и АЧА11 х= Н.
(Удаление выполнено, поэтому удаляется строка полинома (Ц).) Если теперь ЕХР(1ЕРТ(Р)) = О и Ц = Б, перейти к шагу А9; в противном случае вернуться к шагу А4. А9. [Удаление полинома-константы.] (Аннулирование членов вызвало сокращение полинома до константы, поэтому строка полинома (Ц) удаляется.) Установить й е- Ц. Ц х- СР(Ц), 00ММ(Ц) е- ООЫМ(Н), СЧ(Ц) е- СЧ(Е) н яЧА11 х- й. Установить Б е- ООММ(Ц).
Если Б ф Л, установить 0Р(Б) +- Ц, Б +- Н1СНТ(Б) и, если ЕХР(Б) ~ О, повторять эту операцию до тех пор, пока не получится ЕХР(Б) = О. А10. [Обнаружение нуля?) Если РОММ(Ц) = Л, СЧ(Ц) = 0 и ЕХР(Ц) ф О, установить Р +- ОР(Р) и перейти к шагу А8, в противном случае перейти к шагу Аб. А11. [Прекращение выполнения алгоритма.] Ни разу не устанавливать или устанавливать ц +- СР(Ц) до тех пор, пока не получится ОР(ц) = Л (с переводом указателя Ц на корень этого дерева). $ Данный алгоритм выполняется гораздо быстрее, чем алгоритм 2.2.4А, если полинам (Р) имеет мало членов, а полипом (Ц) — много, так как в процессе сложения совершать обход всего полинома (Ц) необязательно.
Читателю будет очень полезно вручную выполнить алгоритм А, складывая полинам ху — х' — х໠— » + Зх» с 2 з з полпномом, показанным на рнс. 28. (Этот случай ие предназначен для демонстрации эффективности данного алгоритма, но позволяет ознакомиться со вселли его шагами и представить все сложные ситуации, которые следует обработать.) Дальнейшее обсуждение алгоритма А приводится в упр, 12 и 13.
Показанное на рис. 28 представление для полиномов от произвольного количества переменных не является "наилучшим". Например, в главе 8 будет рассмотрен другой формат представления полиномов, а также некоторые арифметические алгоритмы па основе вспомогательного стека, которые по сравнению с алгорнтлюм А обладают существенными преимуществами в отношении концептуальной простоты. Алгоритм А интересен для нас в основном тем, как в нем организована обработка деревьев с большим количеством связей. УПРАЖНЕНИЯ 1.
[НР] Можно лн восстановить связи ьь1ИК, зная только поля ьтКС, 1ИРО и ИТКС узлов в паслсдаватслыюм порядке уровней, подобном (8)? (Иначе говоря, нс являются ли полн ль1ИК избыточными в представлении (8) и паля 10.1ИК вЂ” в представлении (3)?) 2. [99] (Задача Бернса, Уоррена н Райта, К(ялЬ. Сашр. 8 (1954), 53-57.) Пустьдеревья(2) хранятся и памяти в прямо.м порядке с указанием степеней ОЕСИЕЕ 2 О 1 О 3 1 О 1 О О 1ИРО А В С К В В Н с д С [Ср.
с (9), где анн привалены в абратналл порядке.) Создайте алгоритм, аналогичный алгоритму Г, для апспки локально определенной функции узлов, выполнив обход этого прслстянлспнм справя налево. 3. [84] Измените алгоритм 2 3 2П, используя ццею алгоритма Г промежуточные производные размещались в стеке, а их адреса не записываются таким необычным способом, который применяется на шаге 113 (см упр 2 3 2-21) Управление стеком может осуществляться на основе поля Ы.1ИК а корне каждой производной 4. [18] Деревья (2) содержат 10 узлов, пять из которых являются концевыми Представление этих деревьев в виде нормальных бинарных деревьев включает 10 полей ььТИК и 10 палей КС1ИК (по одному для каждого узла) Для представления этих деревьев в виде (10), где 11.1ИК и 1ИГО совместна используют одно и то же пространство внутри узла, требуется 5 полей ШИК и 15 палей Ы.1ИК В каждом случае имеется по 10 палей 1ИРО Для леса с и узламн, гп из которых являются концевыми, сравните общее количество полей ШИК я КЫИК, которые необходимы для каждого из этих двух методов представления дерева 5.
[18] Трижды связанное дерево, аналогичное показанному на рис 26, содержит в каждом узле поля РАКЕИТ, ьСН150 и Ы.1ИК, причем при отсутствии узла, на который могли бы указать поля РАНЕИТ, ЕСН1ЕО и Нь1ИК, в них применяются связи Л Стоит ли расширять это представление да првшитвги дерева, применяя связи-нити вместо пустых связей ЬСНТьО и Ы.1ИК, как показано в разделе 2 3 1э 6. [84] Предположим, что узлы ириенгпированногв леса имеют по три паля связи РАНЕИТ, ьСН110 и Ы.1ИК, но талька одна связь РАНЕИТ используется для обозначения древовидной структуры Поле ЬСН150 каждого узла равно Л, а поля Ы.ТИК расположены в линейном списке, который просто связывает узлы вместе в некотором порядке Переменная связи Г156Т указывает на первый узел, а в последнем узле Ы.1ИК = Л Создайте алгоритм обхода этих узлов и заполнения палей ьСН110 и Ы.1ИК в соответствии со значениями связей РАНЕИТ, чтобы в результате можно было получить представление трижды связанного дерева, подобное показанному на рис 26 Кроме того, установите для Г1НЯТ значение которое будет указывать на корень первого дерева в этом представлении Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
