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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

22
В алгоритме будет использована последовательная таблица X[1],
X[2], …, X[n], любой k-й узел которой имеет формат:
COUNT[k] TOP[k]
где COUNT[k] – количество непосредственных предшественников объек-
та k (количество встретившихся среди входной информации пар j < k),
TOP[k] – связь с началом списка непосредственных преемников объек-
та k. Список непосредственных преемников содержит элементы формата:
SUC NEXT
где SUC – непосредственный преемник объекта k, NEXT – связь со сле-
дующим элементом этого списка.
Для входной информации (22) будем иметь следующую модель па-
мяти:
Рис. 6. Машинное представление для отношений (22)
Алгоритм будет заключаться в выводе узлов, у которых поле
COUNT равно нулю, и последующем уменьшении на один поля COUNT у
всех преемников этих узлов. Для избежания поиска узлов с нулевым зна-
чением поля COUNT организуется очередь из этих узлов. Связи для оче-
реди размещаются в поле COUNT, которое к данному моменту уже вы-
полнило свою предыдущую функцию. Для большей наглядности в алго-
ритме используется обозначение QLINK[k] вместо COUNT[k], когда это
поле уже не используется как счётчик.
Алгоритм T. (Топологическая сортировка.) Здесь вводятся пары от-
ношений j < k (1 ≤ j ≤ n, 1 ≤ k ≤ n, j ≠ k), говорящие, что объект j предше-
ствует объекту k в некотором отношении упорядочения. Результатом яв-
ляется множество всех объектов, расположенных в линейном порядке.
Используются внутренние таблицы QLINK[0], COUNT[1] = QLINK[1],
COUNT[2] = QLINK[2], …, COUNT[n] = QLINK[n]; TOP[1], TOP[2], …,
TOP[n]; пул памяти с одним узлом (с полями SUC и NEXT) для каждой
вводимой пары; P – переменная связи для ссылки на узлы в пуле памяти;
F и R – целочисленные переменные, используемые для ссылок в начало и
0 1 1 1 2 1 2 2
3 8 7 6 8
4
6
5
0
5
2
k
1 2 3 4 5 6 7 8 9
COUNT[k]
TOP[k]
SUC
NEXT
SUC
NEXT

Страницы