Обращение к списку (4) обычно выполняется с помощью заголовка списка, который часто располагается в некоторой фиксированной ячейке памяти. Недостатком применения структуры с заголовком списка является то, что в нем нет никакого указателя на правый конец, поэтому при работе с таким списком придется пожертвовать описанной выше операцией (Ь).

Схему (4) можно сравнить со схемой 2.2.3-(1), приведенной в начале предыдущего раздела, в которой связь с "элементом 5" теперь указывает на LOC(FIRST), а не на Л. Переменная FIRST рассматривается как ссылка внутри узла, а именно - как ссылка, которая находится внутри NODE(LOC(FIRST)). Принципиальным отличием между (4) и 2.2.3-(1) является то, что схема (4) предоставляет возможность (хотя и необязательно эффективную) получения доступа к любому элементу списка из любого элемента списка.

В качестве примера использования циклических списков рассмотрим арифметические действия над полиномами от переменных х,у w z с целыми коэффициентами. Для решения многих проблем часто приходится вместо чисел манипулировать многочленами. Например, умножив

{x+ 2xy + Zxy+Аху+ Ьу) на {х - 2ху + у),

получим

{х-Ьху+ Ъу).

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

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

Здесь COEF является коэффициентом члена xyz. Допустим, что коэффициенты и степени никогда не выходят за рамки диапазона, заданного в используемом формате, а потому проверять соответствие диапазону необязательно.

Обозначение ABC будет использоваться для обозначения полей ± А В С узла (5) как единого целого. Знак ABC, а именно - знак второго слова в узле (5), всегда положителен, за исключением особого узла в конце каждого многочлена, для которого ABC = - 1 и COEF = 0. Такой особый узел очень удобно использовать по аналогии с заголовком списка, так как он выполняет функции признака конца и это позволяет решить проблему опустошения списка (что соответствует многочлену 0). Узлы списка всегда располагаются в порядке убывания поля ABC, если следовать в направлении заданных связей, но особый узел (у которого ABC = -1) связан с наибольшим узлом ABC. Например, многочлен х - бху -\- Ъу будет иметь такое представление: ptr

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

А1. [Инициализация.] Установить Р •(- LINK(P), QI •(- Q, Q Ч- LINK(Q). (Теперь P и Q указывают на первые члены многочленов. На протяжении почти всего этого алгоритма переменная Q1 будет на один шаг отставать от переменной Q в том смысле, что Q = LINK(Ql).)

А2. [АВС(Р) :ABC(Q).] Если АВС(Р) < ABC(Q), установить Q1 Ч- Q и Q LINK(Q) и повторить этот шаг. Если АВС(Р) = ABC(Q), перейти к шагу A3. Если АВС(Р) > ABC(Q), перейти к шагу А5.

A3. [Сложение коэффициентов.] (Найдены члены с одинаковыми степенями.) Если АВС(Р) < О, выполнение алгоритма прекращается. В противном случае установить COEF(Q) <г- COEF(Q) --COEF(P). Теперь, если COEF(Q) = О, перейти к шагу А4; в противном случае установить Р ч- LINK(P), Q1 •(- Q, Q ч- LINK(Q) и перейти к шагу А2. (Любопытно, что последние операции идентичны шагу А1.)

А4. [Удаление нулевого члена.] Установить Q2 ч- Q, LINK(Ql) ч- Q ч- LINK(Q) и AVAIL <= Q2. (Порожденный на шаге A3 нулевой член удален из многочлена (Q).) Установить Р •(- LINK(P) и вернуться к шагу А2.

А5. [Вставка нового члена.] (Многочлен (Р) содержит член, который отсутствует в многочлене (Q), поэтому его необходимо вставить в многочлен (Q).) Установить Q2 AVAIL, C0EF(Q2) <- COEF(P), ABC(Q2) Ч- ABC(P), LINK(Q2) Ч- Q, LINK(Ql) <r- Q2, QI -f- Q2, P LINK(P) и вернуться к шагу А2.

Одна из наиболее замечательных особенностей алгоритма А заключается в способе следования указателя Q1 за указателем Q в списке. Этот способ типичен для алгоритмов обработки списков, и мы не раз еще встретим алгоритмы с такой же особенностью. Может ли читатель объяснить, почему данная идея использовалась в алгоритме А?

Читателю с небольшим опытом работы со связанными списками будет очень полезно внимательно изучить алгоритм А, например в качестве упражнения попробовать сложить многочлены х + у + z и - 2у - z.

Зная алгоритм А, можно удивительно просто создать следующий алгоритм для операции умножения.

Алгоритм М {Умножение многочленов). Этот алгоритм аналогичен алгоритму А и заменяет многочлен (Q) суммой

многочлен (Q) -- многочлен (М) х многочлен (Р).

Ml. [Следующий множитель.] Установить М <г- LINK(M). Если АВС(М) < О, то выполнение алгоритма прекращается.

М2. [Цикл умножения.] Выполнить алгоритм А, но всякий раз, когда появляется обозначение "АВС(Р)", заменить его командой "если АВС(Р) < О, то -1;

в противном случае АВС(Р)--АВС(М)"; когда появляется обозначение "COEF(P)", заменить его командой"COEF(Р) х COEF(M)". Затем перейти к шагу Ml.

Программирование алгоритма А на языке компьютера MIX вновь демонстрирует легкость, с которой компьютер может манипулировать связанными списками. В приведенном ниже коде предполагается, что при возникновении переполнения (OVERFLOW) вызывается подпрограмма, которая либо завершает выполнение программы (из-за нехватки памяти), либо находит свободное пространство и выходит на rJ - 2.

Программа А (Сложение многочленов). Эта подпрограмма (рис. 10) создана так, чтобы ее можно было использовать вместе с подпрограммой умножения (см. упр. 15).

Вызов:

Состояние до вызова: Состояние после вызова:

JMP ADD.

rll = Р, rI2 = Q.

Многочлен (Q) заменяется суммой: многочлен (Q) -- многочлен (Р); гП и г12 остаются неизменными; все другие регистры имеют неопределенное содержимое.

а1. Иннциг1лизация

A3. Сложение коэффициентов

а2. АВС(р) :ABC(Q)

а4. Удг1ление нулевого члена

а5. Вставка нового члена

Рис. 10. Сложение многочленов.