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

т - количество подобных членов, которые взаимно сокращаются;

т" - количество подобных членов, которые нельзя сократить;

р - количество членов в многочлене (Р), для которых нет подобных членов в многочлене (Q);

q - количество членов в многочлене (Q), для которых нет подобных членов в многочлене (Р).

Анализ программы А с помощью обозначений

т = т + т", р - т+р, q = m + q, x - l + m+p + q

позволяет получить следующую оценку времени ее выполнения на компьютере MIX: (27m -I- 18m" -I- 27p + 8q + 13)u. Минимальное количество узлов в пуле, которые необходимы для вьшолнения алгоритма, равно 2 + р + q, а максимальное - равно 2+p + q + p.

УПРАЖНЕНИЯ

1. [21] В начале этого раздела было предложено представлять пустой циклический список с помощью указателя PTR = А. Однако согласно идеологии создания циклических списков для обозначения пустого списка более последовательно было бы использовать значение PTR = LOC(PTR). Упрощает ли такое условие выполнение операций (а)-(с), которые описаны в начале этого раздела?

2. [20] Нарисуйте схемы состояний "до" и "после", которые демонстрируют результат выполнения операции конкатенагщи (3) при условии, что PTRi и PTR2 не равны А.

► 3. [20] Каким будет результат выполнения операции (3), если оба указателя PTRi и PTRj направлены на узлы одного и тго же циклического списка?

4. [20] Сформулируйте операции вставки и удаления, которые в результате позволят использовать список (4) как cmejfc

► 5. [21] Создайте алгоритм, который обращает циклический список, т. е. направления всех стрелок на схеме (1).

6. [18] Нарисуйте схему представления следующих многочленов в виде списков: (а) XZ - 3; (Ь) 0.

7. [10] В чем заключается преимущество расположения членов многочлена в порядке убывания значений поля ABC?

► 8. [10] В чем заключается преимущество следования указателя Q1 за указателем Q в алгоритме А?

► 9. [23] Будет ли алгоритм А функционировать правильно, если Р = Q (т. е. оба указателя указывают на один и тот же многочлен)? В каком случае алгоритм М будет работать правильно: если Р = М, если Р = Q или если М = Q?

► 10. [20] При создании алгоритмов в данном разделе предполагалось, что в многочленах используются три переменные х, у и z, аих степени по отдельности никогда не превышают 6-1 (где 6 - размер байта в компьютере MIX). Вместо этого предположим, что осуществляется сложение и умножение многочленов от одной переменной, х, степень которой может достигать значения - 1. Какие изменения следует внести в алгоритмы А и М?

11. [24] (Назначение этого упражнения и многих следующих заключается в создании пакета подпрограмм арифметики многочленов для совместной работы с программой А.) Поскольку алгоритмы А и М изменяют многочлен (Q), иногда полезно иметь подпрограмму, которая делала бы копию исходного многочлена. Напишите программу для компьютера MIX со следующими заданными спехщфикахщями.

Вызов: JMP СОРУ.

Состояние до вызова: гП = Р.

Состояние после вызова: г12 указывает на вновь созданный многочлен, равный многочлену (Р); гП остается неизменным; другие регистры не определены.

12. [21] Сравните время выполнения программы из упр. 11 и время выполнения алгоритма А, если многочлен (Q) = 0.

13. [20] Напишите подпрограмму для компьютера MIX со следующими спецификациями.

Вызов: JMP ERASE.

Состояние до вызова: гП = Р.

Состояние после вызова: Многочлен (Р) добавляется в список AVAIL; значения других регистров не определены.

[Замечание. Эта подпрограмма может быть использована вместе с подпрогра.ммой из упр. 11 в последовательности "LD1 Q; JMP ERASE; LDI Р; JMP СОРУ; ST2 Q", чтобы получить "многочлен (Q) i- многочлен (Р)".]

14. [22] Создайте подпрограмму для компьютера MIX со следующими спецификациями.

Вызов: JMP ZERO.

Состояние до вызова: Не обусловлено.

Состояние после вызова: г12 указывает на вновь созданный многочлен, равный 0; значения других регистров не определены.

15. [24] Создайте подпрограмму для компьютера MIX для выполнения алгоритма М со следующими спецификациями.

Вызов: JMP MULT.

Состояние до вызова: rll = Р, rI2 = Q, rI4 = М.

Состояние после вызова: Многочлен(О) <- многочлен(О) + многочлен(М) х многочлен(Р);

значения регистров гП, г12, г14 остаются неизменными; значения других регистров не определены.

[Замечание. Используйте программу А как подпрограмму, изменив значения SW1, SW2 и SW3.]

16. [M.S5] Оцените время выполнения подпрограммы из упр. 15 на основе наиболее важных параметров.

► 17. [8S] В чем заключается преимущество представления многочлена в виде циклического списка (описанного в этом разделе) по сравнению с представлением в виде прямого линейного связанного списка, который завершается А (и описанного в предыдущем разделе)?

► 18. [85] Придумайте способ представления циклических списков внутри компьютера таким образом, чтобы проход списка был эффективным в обоих направлениях, причем чтобы в каждом узле использовалось только одно поле связи. [Указание. Если есть два указателя на два последовательных узла xt-i и ij, то должна существовать возможность доступа к узлам Xi+i и ii-2.]

2.2.5. Дважды связанные списки

Для гибкой работы со связанными списками в каждый узел можно включить даже две связи, которые будут указывать на два соседних элемента:

LEFT

RIGHT

Здесь LEFT и RIGHT обозначают переменные связи, которые указывают на левый и правый концы списка. Каждый узел списка включает две связи, например LLINK и RLINK. Как показано в упр. 1, при таком представлении со списком можно выполнять те же операции, что и с деком общего типа. Однако операции с деком почти всегда гораздо легче выполняются, если в нем присутствует узел с функциями заголовка списка, который рассмотрен в предыдущем разделе. При наличии заголовка списка типичная схема дважды связанного списка выглядит так, как показано ниже:

Заголовок

списка

Поля RLINK и LLINK заголовка списка используются вместо указателей LEFT и RIGHT в схеме (1). Правый и левый концы абсолютно симметричны, поэтому заголовок списка может с таким же успехом располагаться с правой стороны списка на схеме (2). Если список пуст, оба поля связи заголовка списка указывают на сам заголовок. Представление списка в виде (2), очевидно, удовлетворяет условию

RLINK (LLINK (X) ) = LLINK (RLINK (X) ) = X, (3)

где X - адрес любого узла в списке (включая его заголовок). Именно поатому представление списка в виде (2) предпочтительнее, чем в виде (1).

Дважды связанный список обычно занимает гораздо больше места в памяти, чем однократно связанный список (хотя в узле, который не заполняет полностью