(за исключением последнего элемента, который описывается ниже), где SUB -загружаемая подпрограмма и BASE - величина перемещения. Данные элементы должны быть расположены в том же порядке, в коэгором они располагаются на ленте. Ниже показано одно из возможных рещений задачи из приведенного выще примера.

Последний элемент содержит значение адреса первой неиспользуемой ячейки памяти.

(Очевидно, что это не единственный способ работы с библиотекой подпрограмм. Соответствующая ему организация библиотеки в значительной степени зависит от типа используемого компьютера и выполняемых приложений. При работе с мощными современными компьютерами для организации библиотеки подпрограмм потребуется соверщенно другой подход. Тем не менее рассмотренный выще метод является прекрасным примером использования интересных приемов работы с последовательными и связанными данными.)

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

27. [25] Напишите программу для компьютера MIX, реализующую алгоритм из упр. 26.

28. [40] Приведенная ниже конструкция демонстрирует способ "решения" достаточно общей задачи - игры для двух лиц, например шахматы, ним или другие более простые игры. Рассмотрим конечное множество узлов, каждый из которых представляет собой возможное состояние игры. Существует несколько шагов (или ни одного), которые позволяют преобразовать каждое состояние в некоторое другое. Назовем состояние х предшественником состояния у (а у - наследником состояния х), если существует такой шаг, который переводит состояние х в состояние у. Состояния без наследников называются проигрышем или выигрышем. Игрок, делающий ход с переходом в состояние х, является соперником игрока, который делает ход с переходом от состояния х к состояниям-наследникам.

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

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

Такая процедура вычисления полного набора выигрышных и проигрышных состояний может быть сформулирована для компьютера в виде алгоритма, подобного алгоритму Т. Для этого можно сохранять для каждого состояния количество его состояний-наследников, которые не отмечены как "выигрышные", а также список всех его предшественников.

Назначение этого упражнения состоит в создании конкретного алгоритма, который лишь приблизительно описан выше, и в его применении для некоторых интересных игр, не содержащих слишком большого количества возможных состояний [подобных "военной

игре": Ё. Lucas, Recreations Mathematiques 3 (Paris, 1893), 105-116; E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways 2 (Academic Press, 1982), Chapter 21]. ► 29. [21] (a) Предложите алгоритм "удаления" всего списка (1) с размещением всех его узлов в стеке AVAIL, если известно только значение FIRST. При этом алгоритм должен иметь оптимизированную скорость выполнения. (Ь) Решите задачу из п. (а) для списка (12) при условии, что известны значения F и R.

30. [17] Предположим, что очереди выглядят так, как (12), но с пустой очередью, представленной значением F = Л и неопределенным значением R. Как в таком случае следует изменить операции вставки и удаления, представленные правилами (14) и (17)?

2.2.4. Циклические списки

Немного изменив способ связывания, можно ввести новый метод, альтернативный предложенному в предыдущем разделе.

Циклически связанный список (circularly linked list) (или короче - циклический список)-это связанный список, в котором последний узел связан с первым узлом, а не с А. Поэтому всегда существует возможность доступа к любому элементу списка, начиная с произвольно выбранного элемента. К тому же повышается степень симметрии структуры списка, и при работе со списком можно не заботиться о том, где находится последний или первый узел.

Типичная схема циклического списка выглядит так:

PTR . (1)

Предположим, что узел содержит два поля, INFO и LINK, как и в предыдущем разделе. Ссылочная переменная PTR указывает на крайний справа узел списка; при этом в поле LINK(PTR) будет содержаться адрес крайнего слева узла. Наиболее важными являются следующие простейшие операции.

a) Вставка элемента Y слева: Р <!= AVAIL, INFO(P) Y, LINK(P) LINK (PTR), LINK (PTR) <- P.

b) Вставка элемента Y справа: вставить Y слева, a затем - PTR <- P.

c) Передать в Y содержимое левого узла и удалить этот узел из списка: Р LINK(PTR), Y.f- INFO(P), LINK-(PTR) <- LINK(P), AVAIL <= P.

Операция (b). Ha первый взгляд, выглядит несколько необычно. Операция PTR <- LINK(PTR) на самом деле перемещает крайний слева уз&л в схеме (1), и это довольно легко можно представить, если рассмотреть список как замкнутое кольцо, а не прямую линию со связанными концами.

Внимательный читатель заметит, что в операциях (а)-(с) допущена серьезная ошибка. Какая? Ответ: не предусмотрена возможность опустошения списка. Если, например, операция (с) применяется пять раз по отношению к списку (1), получится, что PTR указывает на узел в списке AVAIL, а это может привести к серьезным осложнениям. Например, попробуем применить операцию (с) еще раз! Если предположить, что указатель PTR равен А в случае полного опустошения списка, эту ошибку можно устранить, вставив дополнительные команды "если PTR = А,- то PTR <г- LINK(P) Р; в противном случае ..." после команды "INFO(P) ч- Y" в (а), предвосхитив операцию (с) проверкой "если PTR = Л, то UNDERFLOW" и завершив операцию (с) командой "если PTR = Р, то PTR <г- Л".

Обратите внимание, что операции (а)-(с) представляют собой действия, выполняемые с деком с ограниченным выводом, который рассматривался в разделе 2.2.1. Следовательно, цикличес1{ий список может использоваться либо как стек, либо как очередь. Операции (а) и (с) представляют функциональную часть стека, а операции (Ь) и (с) -очереди. Эти операции не так очевидны, как их аналоги из предыдущего раздела, в котором показано, что операции (а)-(с) могут выполняться с линейными списками с помощью указателей F и R.

Для циклических списков гораздо эффективнее выполняются другие важные операции. Например, очень просто выполняется операция удаления списка, т. е. размещения всего циклического списка в стеке AVAIL:

Если PTR ф Л, то AVAIL LINK (PTR). (2)

[Напомним, что операция обозначает обмен наподобие Р ч- AVAIL, AVAIL ч- LINK (PTR), LINK (PTR) Ч- P.] Очевидно, что операция (2) будет корректно выполняться, если PTR указывает на произвольный элемент циклического списка. После чего, конечно, следует установить PTR ч- Л.

Используя этот же метод, если PTRi и PTR2 указывают на отдельные циклические списки Ll и L2 соответственно, можно вставить список L2 целиком справа в список Ll:

Если PTR2 ф \,то

(если PTRi ф Л, то LINK(PTRi) Ч-> LINK(PTR2); (3)

установить PTRi ч- PTR2, PTR2 ч- Л).

Другим примером легко выполнимой операции является расщепление самыми разными способами одного циклического списка на два подсписка. Эти операции соответствуют конкатенации (сцеплению) и деконкатенации (разбиению) строк.

Таким образом, циклический список можно использовать не только для представления исходно циклических структур, но и для линейных структур. Циклический список с одним указателем на конечный узел эквивалентен линейному списку с двумя указателями на начало и конец. Естественный вопрос в данном случае формулируется так: "Как, имея дело с циклически симметричной структурой, найти конец списка?". Ведь для обозначения конца не существует никакого специального объекта типа Л! Ответ заключается в том, что при обработке всего списка, перемещаясь От одного узла к другому, прекратить обработку следует по достижении стартовой позиции (при условии, конечно же, что такая позиция существует в данном списке).

Альтернативным решением только что поставленной задачи было бы использование в каждом циклическом списке в качестве конечной позиции особого легко распознаваемого узла. Такой особый узел называется заголовком списка {list head). Как можно будет вскоре убедиться, в приложениях часто очень удобно придерживаться такого правила: каждый циклический список должен содержать один узел, который является заголовком этого списка. Одним из преимуществ подобной структуры является то, что такой циклический список никогда не опустошается. При использовании заголовка списка схема (1) будет выглядеть так: Заголовок

списка

1Н->1 1 1-Н \ Гг1 ()