COUNT[fc] TQPCfc]

NEXT

NEXT

Рис. 8. Компьютерное представление показанной на рис. 6 последовательности элементов с отношениями (18).

Например, поток ввода может содержать следующие объекты с такими отношениями между ними:

9ч2, ЗЧ7, 75, 58, 8 Ч б, 4 ч б, 1 Ч 3, 7 Ч 4, 9 Ч 5, 2 ч 8. (18)

Здесь необязательно приводить какие-то дополнительные отношения для характеристики искомого частичного упорядочения. Например, дополнительные отношения типа 9 8 (которые можно вывести из отношений 9 -< 5 и 5 -< 8) можно без какого-либо влияния на конечный результат опустить или добавить во входной поток данных. В общем случае необходимо указать только те отношения, которые соответствуют стрелкам на диаграмме, показанной на рис. 6.

В приведенном ниже алгоритме используется последовательно упорядоченная таблица X [1], X [2], ..., X [п], в которой каждый узел X [fc] имеет вид

Здесь COUNT [fc] обозначает количество прямых предшественников объекта fc (т. е. количество отношений j ч fc во входном потоке данных), а TOP[fc] -связь с началом списка прямых потомков объекта fc. Последний список содержит элементы в формате

NEXT

где sue - прямой потомок объекта fc и NEXT-следующий элемент списка. Для демонстрации этих условных обозначений на рис. 8 схематически показано содержимое памяти, соответствующее входному потоку данных (18).

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

свое назначение. Для ясности в приведенном ниже алгоритме обозначение QLINK [fc] используется вместо COUNT [fc], когда это поле больше не применяется для хранения значений счетчика.

Алгоритм Т {Топологическая сортировка). В этом алгоритме в качестве входного потока используется последовательность отношений j -< fc, обозначающих, что объект j предшествует объекту fc в некотором частичном упорядочении при условии, что I < j,k < п. Выходной поток состоит из множества и объектов, расположенных в линейном порядке. При этом используются следующие внутренние таблицы: QLINK[0], COUNT[1] = QLINK[1], COUNT[2] = QLINK[2], COUNT[n] = QLINK[n]; T0P[1], TOP[2], TOP[n]; пул с одним узлом для каждого отношения входного потока и с указанными выше полями SUC и NEXT; переменная связи Р, которая используется для ссылки на узлы в пуле; целочисленные переменные F и R, применяемые для ссылок на начало и конец очереди, связи которых находятся в таблице QLINK; и, наконец, переменная N, позволяющая подсчитать количество объектов, которые необходимо поместить в выходной поток.

Т1. [Инициализация.] Ввести значение п. Установить COUNT [fc] О и TOP[fc] Л для 1 < fc < п. Установить N п.

Т2. [Следующее отношение.] Получить отношение j -< fc из входного потока. Если

входной поток исчерпан, перейти к шагу Т4. ТЗ. [Запись отношения.] Увеличить на единицу значение COUNT [fc]. Установить

Р <= AVAIL, SUC(P) fc, NEXT(P) TOP[j], TOP[j] P.

(Это операция (8).) Вернуться к шагу Т2. Т4. [Поиск нулей.] (В этом месте завершается ввод, и входной поток (18) теперь имеет понятный для компьютера вид, представленный на рис. 8. Следующий шаг заключается в инициализации очереди выходного потока, который связан с помощью поля QLINK.) Установить R О и QLINK [0] 0. Для 1 < fc < п проверить значение COUNT [fc] и, если оно равно нулю, установить QLINK [R] fc и R fc. После выполнения этого действия для всех fc установить F QLINK [0] (теперь оно будет содержать первое значение fc, для которого COUNT [fc] равно нулю).

Т5. [Вывод начала очереди.] Вывести значение F. Если F = О, перейти к шагу Т8, в противном случае установить N N - 1 и установить Р ТОР [F]. (Так как таблицы QLINK и COUNT перекрываются, получим QLINK [R] = 0. Следовательно, условие F = О выполняется, когда очередь пуста.)

Т6. [Удаление отношений.] Если Р = Л, перейти к шагу Т7. В противном случае уменьшить на единицу значение COUNT [SUC(P)], а если оно уже равно нулю, установить QLINK[R] SUC(P) и R SUC(P). Установить Р NEXT(P) и повторить этот шаг. (Таким образом удаляем из системы все отношения вида F -< fc для некоторого fc и располагаем новые узлы в очереди, когда все их предшественники уже выведены.)

Т7. [Удаление из очереди.] Установить F QLINK [F] и вернуться к шагу Т5.

Т8. [Конец процесса.] Прекращение работы алгоритма. Если N = О, получим в результате искомое "топологическое упорядочение" пронумерованных объектов.

за которыми следует нуль. В противном случае N пронумерованных объектов не будут выведены из-за того, что они образуют замкнутую петлю, а это нарушает гипотезу о частичномупорядочении. (В упр. 23 рассмотрен алгоритм печати содержимого такой петли.)

Читателю наверняка будет полезно попробовать вручную применить этот алгоритм для входного потока (18). Алгоритм Т демонстрирует прекрасное взаимодействие между методами организации последовательной и связанной памяти. Последовательная память используется для основной таблицы Х[1], Х[п], которая содержит объекты COUNT [fc] и ТОР [fc], поскольку на шаге ТЗ предстоит ссылаться на "произвольно выбранные" части этой таблицы. (Однако, если входной поток является символьным, для более быстрого поиска следует использовать другой тип таблицы, который описывается в главе 6.) Связанная память применяется для таблиц, в которых "один объект непосредственно следует за другим" (immediate successors), так как во входном потоке эти объекты никак не упорядочены. Очередь ожидаюш;их вывода узлов хранится внутри последовательной таблицы, связывая, таким образом, узлы в порядке их вывода. Для этого связывания вместо адресов используется индекс таблицы. Иначе говоря, если X[fc] -начало очереди, получим F = fc вместо F = LOC(X[fc]). Операции обработки очереди, используемые на шагах Т4, Т6 и Т7, не идентичны операциям (14) и (17), так как в данном случае используются преимущества особых свойств очереди. Во время выполнения этой части алгоритма никакие узлы не придется создавать или возвращать в свободное пространство памяти.

При программировании алгоритма Т на языке ассемблера компьютера MIX следует учесть несколько интересных особенностей. Так как в данном алгоритме в таблице не предпринимается никаких удалений (поскольку не требуется освобождать память для ее последующего использования), операция Р <= AVAIL может быть выполнена чрезвычайно просто, т. е. так, как показано ниже, в строках 19 и 32. В такой ситуации не потребуется содержать связанный пул памяти, а новые узлы можно выбирать последовательно. Ввод и вывод данных в программе предполагается выполнять с магнитной ленты согласно упомянутым выше соглашениям, но для упрощения кода в данном случае опущена буферизация. Читатель вряд ли столкнется с какими-либо трудностями при чтении этого кода, поскольку код полностью соответствует алгоритму Т. Здесь также показано, насколько эффективно может быть организовано использование индексных регистров , что является важным аспектом обработки связанной памяти.

Программа Т (Топологическая сортировка). В этой программе (рис. 9) нужно учесть следующие равенства: г16 = N, г15 = указатель буфера, г14 = fc, г13 = j и R, г12 = AVAIL и Р, г11 = F, TOP[j] =X4-j(4:5), COUNT [fc] = QLINK[fc] = X-l-fc(2:3).

01 ♦ БУФЕРИЗАЦИЯ И ОПРЕДЕЛЕНИЕ ПОЛЕЙ

02 COUNT EQU 2:3 Определение символьных

03 QLINK EQU 2:3 имен полей.

04 TOP EQU 4:5

05 sue EQU 2:3

06 NEXT EQU 4:5

07 TAPEIN EQU 1 Ввод с ленты 1.

08 TAPEOUT EQU 2 Вывод на ленту 2.