Д. Кнут - Искусство программирования том 1 (1119450), страница 76
Текст из файла (страница 76)
(1) Предположим, что узел содержит два поля, 1МРО и ЫИК, как и в предыдущем разделе. Ссылочная переменная РТК указывает на крайний справа узел списка; при этом в поле ЫИК(РТК) будет содержаться адрес крайнего слева узла. Наиболее важными являются следующие простейшие операции.
а) Вставка элемента У слева: Р ~= АЧА11., 1ИРО(Р) +- Ч, ЫМК(Р) с — ЫИК(РТК), ЫИК(РТК) +- Р. Ь) Вставка элемента Ч справа: встйвить У слева, а затем — РТК с — Р. с) Передать в Ч содержимое левого узла и удалить этот узел из списка: Р <— ЫИК(РТК), Ч.с в 1ИРО(Р), ЫИК'(РТК) +- 1.1МК(Р), АЧА11.
4а Р. Операция (Ь), на первый взгляд, выглядит несколько необычно. Операция РТК с- ЫИК(РТК) на самом деле перемещает крайний слева узел в схеме (1), и это довольно легко можно представить, если рассмотреть список как замкнутое кольцо, а не прямую линию со связанными концами. Внимательный читатель заметит, что в операциях (а)-(с) допущена серьезная ошибка. Какая? Ответи: не предусмотрена возможность опустошения списка.
Если, например., операция (с) применяется пять раз по отношению к списку (1), получится, что РТК указывает на узел в списке АЧА10, а это может привести к серьезным осложнениям. Например, попробуем применить операцию (с) еще раз! Если предположить, что указатель РТК равен Л в случае полного опустошения списка, эту ошибку можно устранить, вставив дополнительные команды "если РТК = Л; то РТК с — ЫИК(Р) < — Р; в противном случае ..." после команды "1ИРО(Р) +- Ч" в (а), предвосхитив операцию (с) проверкой "если РТК = Л, то ОИОЕКР001с"' и завершив операцию (с) командой "если РТК = Р, то РТК с — Л".
Обратите внимание, что операции (а)-(с) представляют собой действия, выполняемые с деком с ограниченным выводом, который рассматривался в разделе 2.2.1. Следовательно, циклический список может использоваться либо как стек, либо как очередь. Операции (а) и (с)' представляют функциональную часть стека, а операции (Ь) и (с) — очереди. Эти операции не твк очевидны, как их аналоги из предыдущего раздела, в котором показано, что операции (а) — (с) могут выполняться с линейными списками с помощью указателей Р и В. Для циклических списков гораздо эффективнее выполняются другие важные операции. Например, очень просто выполняется операция удаления списка, т. е. размещения всего циклического списка в стеке АЧАХ1:.
Если РТВ ф Л, то АЧА1Ь +э ЫИК(РТК). (2) [Напомним, что операция "+э" обозначает обмен наподобие Р +- АЧА1Ь, АЧА1Ь +- ЫВК(РТК), ЫвК(РТВ) +- Р.) Очевидно, что операция (2) будет корректно выполняться, если РТК указывает на произвольный элемента циклического списка. После чего, конечно, следует установить РТК ~ — Л.
Используя этот же метод, если РТК~ и РТВл указывают на отдельные циклические списки Ь| и 1 р соответственно, можно вставить список Ьз целиком справа в список Хл: Если РТВв ф Л, то (если РТВ~ ЭА Л, то ЫМК(РТК~) <+ ЫМК(РТКз); (3) установить РТКд +- РТВю РТВз +- Л). Другим примером легко выполнимой операции является расщепление самыми разными способами одного циклического списка на два подсписка.
Эти операции соответствуют конкатенации (сцеплению) и деконкатенации (разбиению) строк. Таким образом, циклический список можно использовать не только для представления исходно циклических структур, но и для линейных структур. Циклический список с одним указателем на конечный узел эквивалентен линейному списку с двумя указателями на начало и конец. Естественный вопрос в данном случае формулируется так: "Как, имея дело с циклически симметричной структурой, найти конец списка?". Ведь для обозначения конца не существует никакого специального объекта типа Л! Ответ заключается в том, что при обработке всего списка, перемещаясь от одного узла к другому, прекратить обработку следует по достижении стартовой позиции (при условии, конечно же, что такая позиция существует в данном списке).
Альтернативным решением только что поставленной задачи было бы использование в каждом циклическом списке в качестве конечной позиции особого легко распознаваемого узла. Такой особый узел называется заголовком списка (11л1 Леад). Как можно будет вскоре убедиться, в приложениях часто очень удобно придерживаться такого правила: каждый циклический список должен содержать один узел, который является заголовком этого списка. Одним из преимуществ подобной структуры является то, что такой циклический список никогда не опустошается.
При использовании заголовка списка схема (1) будет выглядеть так: Заголовок списка (4) Обращение к списку (4) обычно выполняется с помощью заголовка списка, который часто располагается в некоторой фиксированной ячейке памяти. Недостатком применения структуры с заголовком списка является то, что в нем нет никакою указателя на правый конец, поэтому при работе с таким списком придется пожертвовать описанной выше операцией (Ь). Схему (4) можно сравнить со схемой 2.2.3 — (1), приведенной в начале предыдущего раздела, в которой связь с "элементом 5" теперь указывает на 1.ОС(Р1ВЯТ), а не на Л. Переменная РХКБТ рассматривается как ссылка внутри узла, а именно — как ссылка, которая находится внутри МОВЕ(ЬОС(РПБТ) ).
Принципиальным отличием между (4) и 2.2.3-(1) является то, что схема (4) предоставляет возможность (хотя н необязательно эффективную) получения доступа к любому элементу списка из любого элемента списка. В качестве примера использования циклических списков рассмотрим ариФметические действия над полиномами от переменных х, у и х с целыми коэффициентами.
Для решения многих проблем часто приходится вместо чисел манипулировать многочленами. Например, умножив (х'+ 2х'у+ Зх'у'+ 4ху'+ 5у~) на (х' — 2ху+ у'), получим (хв — бхув + 5ув) Для этого вполне естественно было бы применить связанное распределение, поскольку размер многочленов может непредсказуемо возрасти и может возникнуть необходимость хранить в памяти сразу несколько таких многочленов.
Рассмотрим здесь только две операции: сложение и умножение. Предположим, что многочлен представлен в виде списка, каждый узел которого обозначает ненулевой член многочлена, а сам узел состоит из двух слов и имеет следующий вид: СОЕР (5) А В С Ь1МК Здесь СОЕР является коэффициентом члена х"увгс. Допустим, что коэффициенты и степени никогда не выходят за рамки диапазона, заданного в используемом формате, а потому проверять соответствие диапазону необязательно.
Обозначение АВС будет использоваться для обозначения полей х А В С узла (5) как единого целого. Знак АВС, а именно — знак второго слова в узле (5), всегда положителен, за исключением особого угла в конце каждого многочлена, для которого АВС = — 1 и СОЕР = О. Такой особый узел очень удобно использовать по аналогии с заголовком списка, так как он выполняет функции признака конца и это позволяет решить проблему опустошения списка (что соответствует многочлену О). Узлы списка всегда располагаются в порядке убывания поля АВС, если следовать в направлении заданных связей, но особый узел (у которого АВС = — 1) связан с наибольшим узлом АВС.
Например, многочлен хв — бхув + 5ув будет иметь такое представление: гтв "в +1 о о + в ос +гво + о во Алгоритм А (Сложение многочленов). Этот алгоритм складывает многочлен (Р) с многочленом (Ц) при условии, что Р и Ц вЂ” указатели описанного выше вида. Список Р останется неизменным, а список Ц будет содержать сумму многочленов. По завершении алгоритма ссыпочным переменным Р и Ц возвращаются их прежние значения. Кроме того, в алгоритме используются вспомогательные переменные Ц1 и Ц2. А1. [Инициализация.] Установить Р <- Е1МК(Р), Ц1 +- Ц, Ц ~ — Е1ИК(Ц). (Теперь Р и Ц указывают на первые члены многочленов. На протяжении почти всего этого алгоритма переменная Ц1 будет на один шаг отставать от переменной Ц в том смысле, что Ц = ЫИК(Ц1).) А2.
[АВС(Р):АВС(Ц).] Если АВС(Р) < АВС(Ц), установить Ц1 +- Ц и Ц ~- Е1ИК(Ц) и повторить этот шаг. Если АВС(Р) = АВС(Ц), перейти к шагу АЗ. Если АВС(Р) > АВС(Ц), перейти к шагу Аб. АЗ. [Сложение коэффициентов.) (Найдены члены с одинаковыми степенями.) Если АВС(Р) < О, выполнение алгоритма прекращается. В противном случае установить СОЕК(Ц) < — СОЕР(Ц) + СОЕР(Р). Теперь, если СОЕР(Ц) = О, перейти к шагу А4; в противном случае установить Р +- ЫИК(Р), Ц1 < — Ц, Ц ~- ЫИК(Ц) и перейти к шагу А2.
(Любопытно, что последние операции идентичны шагу А1.) А4. [Удаление нулевого члена.] Установить Ц2 <- ц, ЫИК(Ц1) +- Ц ~ — ЫИК(Ц) и АЧА1Е ~ Ц2. (Порожденный на шаге АЗ нулевой член удален из многочлена (Ц).) Установить Р +- ЫИК(Р) и вернуться к шагу А2. Аб. [Вставка нового члена.] (Многочлен (Р) содержит член, который отсутствует в многочлене (Ц), поэтому его необходимо вставить в многочлен (Ц).) Установить Ц2 ~ АЧА1)„СОЕГ(Ц2) +- СОЕК(Р), АВС(Ц2) < — АВС(Р), ЫИК(Ц2) +- Ц, 1.1МК(Ц1) < — Ц2, Ц1+- Ц2, Р < — Е1ИК(Р) н вернуться к шагу А2.
$ Одна из наиболее замечательных особенностей алгоритма А заключается в способе следования указатели Ц1 за указателем Ц в списке. Этот способ типичен для алгоритмов обработки списков, и мы не раз еще встретим алгоритмы с такой же особенностью. Может ли читатель объяснить, почему данная идея использовалась в алгоритме А? Читателю с небольшим опытом работы со связанными списками будет очень полезно внимательно изучить алгоритм А, например в качестве упражнения попробовать сложить многочлены х + у + г и х — 2у — г.
Зная алгоритм А, можно удивительно просто создать следующий алгоритм для операции умножения. Алгоритм М (Умножение многочленов). Этот алгоритм аналогичен алгоритму А и заменяет многочлен (Ц) суммой многочлен (Ц) + многочлен (М) х многочлен (Р). М1. [Следующий множитель.] Установить М < — 1.1МК(М). Если АВС(М) < О, то выполнение алгоритма прекращается. М2. [Цикл умножения.] Выполнить алгоритм А, но всякий раз, когда появляется обозначение "АВС(Р)", заменить его командой "если АВС(Р) < О, то -1; в противном случае АВС(Р) +АВС(Н) У „когда появляется обозначение "СОЕР(Р)", заменить его командой'"СОВР(Р) х СОЕР(М)".
Затем перейти к шагу М1. 1 Программирование алгоритпа А на языке компьютера М1Х вновь демонстрирует легкость, с которой компьютер может манипулировать связанными списками. В приведенном ниже коде предполагается, что при возникновении переполнения (07ЕЕРООМ) вызывается подпрограмма, которая либо завершает выполнение программы (из-за нехватки памяти), либо находит свободное пространство и выходит на г1 — 2. Программа А (Сложение иногочленов). Эта подпрограмма (рис. 10) создана так, чтобы ее можно было использовать вместе с подпрограммой умножения (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
