Топологическая сортировка
Автор: Илья Зелепукин • Июнь 15, 2019 • Лабораторная работа • 2,191 Слов (9 Страниц) • 278 Просмотры
Министерство образования и науки Российской Федерации
О Т Ч Е Т
о лабораторной работе № 3 на тему
«ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА»
Выполнил:
Проверил:
Тамбов 2017
Цель работы: Знакомство с понятием связанного распределения памяти при хранении линейных списков и программированием алгоритма топологической сортировки.
Вариант № 16
Задание: Выполнить по алгоритму Т топологическую сортировку элементов 1, 2, 3, ..., 9 для заданных отношений между ними:
2<6, 8<2, 3<7, 7<1, 6<5, 4<9, 6<4, 8<9, 1<2, 3<8.
Теоретическая часть
Рассмотрим реализацию топологической сортировки на машине. При этом будем полагать, что сортируемые элементы пронумерованы числами от 1 до n в любом порядке. Информация вводится парами чисел вида (j,k) или j<k. Это означает, что j-й элемент предшествует k-му элементу.
Входной информацией применительно к нашему примеру могут быть такие пары:
9 < 2, 3 < 7, 7 < 5, 5 < 8,
8 < 6, 4 < 6, 1 < 3, (1)
7 < 4, 9 < 5, 2 < 8.
В алгоритме будет использоваться последовательная таблица X[1], X[2], …, X[n], любой k-й узел которой имеет формат:
COUNT[k] | TOP[k] |
где COUNT[k] – количество непосредственных предшественников объектаk(количество встретившихся среди входной информации пар j
SUC | NEXT |
где SUC – непосредственный преемник k, NEXT – связь со следующим элементом этого списка.
Для входной информации (1) будем иметь следующую модель памяти:
k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||||||||
COUNT[k] | 0 | 1 | 1 | 1 | 2 | 2 | 1 | 2 | 0 | ||||||||
TOP[k] | [pic 1] | ||||||||||||||||
SUC | 3 | 8 | 7 | 6 | 8 | 4 | 6 | 5 | |||||||||
NEXT | |||||||||||||||||
SUC | 5 | 2 | |||||||||||||||
NEXT |
Рис. 1. Машинное представление, соответствующее отношениям (1)
Алгоритм будет заключаться в выводе узлов, у которых поле COUNT равно нулю, и последующему уменьшению на один поля COUNT у всех преемников этих узлов. Для избежания поиска узлов с нулевым значением COUNT организуется очередь из этих узлов. Связи для очереди размещаются в поле COUNT, которое к данному моменту уже выполнило свою предыдущую функцию. Для большей наглядности в алгоритме используется обозначение QLINK[k] вместо COUNT[k], когда это поле уже не используется как счетчик.
...