Методы программирования. Громов Ю.Ю - 23 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

23
конец очереди, связи которой находятся в таблице QLINK; N – перемен-
ная, указывающая число невыведенных объектов.
T1. [Начальная установка.] Ввести значение n. Для k = 1, 2, …, n
COUNT[k] ← 0, TOP[k] ← Λ. N ← n.
T2. [Следующее отношение.] Ввести следующее отношение j < k;
если же входная информация исчерпана, то перейти к шагу T4.
T3. [Регистрация отношения.] Значение COUNT[k] увеличить на
единицу. P ⇐ AVAIL, SUC(P) ← k, NEXT(P) ← TOP[ j ], TOP[ j ] ← P.
Перейти к шагу T2.
T4. [Поиск нулей.] (К этому моменту завершена фаза ввода и входная
информация преобразована в машинное представление, показанное на
рис. 6. Производим теперь начальную установку очереди вывода, которая
связывается по полю QLINK.) R ← 0, QLINK[0] ← 0. Для k = 1, 2, …, n
просмотреть COUNT[k] и, если он нулевой, QLINK[R] ← k, R ← k. После
выполнения этих действий для всех k реализовать F ← QLINK[0] (в нём
окажется первое встреченное значение k, для которого COUNT[k] был
нулевым).
T5. [Вывод из начала очереди.] Вывести значение F. Если F равно 0,
то перейти к шагу T8; в противном случае N ← N – 1, P ← TOP[F]. (По-
скольку таблицы QLINK и COUNT перекрываются, мы имеем QLINK[R] = 0;
следовательно, условие F = 0 выполняется, когда очередь пуста.)
T6. [Стирание отношения.] Если P = Λ, то перейти к шагу Т7; в про-
тивном случае уменьшить COUNT[SUC(P)] на единицу и, если при этом
он стал нулевым, QLINK(R) ← SUC(P) и R ← SUC(P). P ← NEXT(P) и
повторить данный шаг. (Мы исключаем из системы все отношения вида
F < k для некоторого k и помещаем новые узлы в очередь, когда все их
предшественники были выведены.)
T7. [Исключение из очереди.] F ← QLINK[F] и вернуться к шагу Т5.
T8. [Окончание процесса.] Конец алгоритма. Если N = 0, то выведе-
ны все номера элементов в требуемом топологическом порядке и вслед за
ними нуль. В противном случае N невыведенных номеров содержат
цикл. ■
В этом алгоритме удачно сочетаются методы последовательной и
связанной памяти. Для главной таблицы X[1], X[2], …, X[n] используется
последовательная память, поскольку на шаге Т3 алгоритм ссылается на
«произвольные» части этой таблицы. Связанная память используется для
таблиц «непосредственных преемников», поскольку элементы этих таб-
лиц вводятся в произвольном порядке. Очередь узлов, ожидающих выво-
да, хранится внутри последовательной таблицы, причём узлы связывают-
ся в соответствии с порядком их вывода. Для связи вместо адреса исполь-
зуется индекс таблицы, т.е. когда начальным узлом очереди является узел
X[k], то мы имеем F равно k, а не F равно LOC(X[k]). Операции над оче-

Страницы