Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [ 70 ] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

числа (необязательно последовательные от 1 до п). Дн гично множество последователей каждого элемента можь представить в виде связанного списка. Каждый элемен списка последователей неким образом идентифицирова* и связан со следующим элементом этого списка. Если мы нд зовем дескрипторы главного списка, в котором каждый эле' мент из S содержится ровно один раз, ведущими {leaders) & дескрипторы списка последователей ведомыми {trailers),-1-мы получим такие описания типов данных:

type Iref = \leader; =

tref = frailer;

leader - record Are;, count: integer; trail: tref;

next: Iref (4.28)

end;

trailer - record id: Iref;

next: tref

Предположим, что множество S и отношения порядка на нем первоначально заданы в виде последовательности пар kjiio-чей во входном файле. Входные данные для примера, изображенного на рис. 4.13, показаны в (4.29), где символы <( добавлены для ясности:

1<2 2<4 4<6 2<10 4<8 6<3

1<3 3<5 5<8 7<5 7<9 9<4 (4.29)

9< 10

Первая часть программы топологической сортировки должна прочитать входной файл и преобразовать входные данные в структуру списка. Это производится последовательным чтением пар ключей х и у (x<<t/). Обозначим ссылки на их представления в списке ведущих через р и д. Эти записи ищутся в списке и, если их там нет, добавляются к нему. Эту задачу выполняет функция, называемая {located). Затем к списку ведомых для элемента х добавляется новый дескриптор, идентифицированный как у, счетчик предшественников для у увеличивается на 1. Такой алгоритм соответствует фазе ввода (4.30). На рис. 4.15 показан -структура, сформированная при обработке входных даннЫ' (4.29) с помощью алгоритма (4.30). В этом фрагменте программы есть обращения к функции Х(ш), дающей ссылку компоненту списка с ключом w (см. также программу 4.2)-Мы предполагаем, что последовательность входных пар кдК'*



count

next

trail


Рис. 4,15. Список, построенный программой топологической сортировки.



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

{фаза ввода ] read(x); newQiead); tail := head; г :== 0; while X 5 О do

begin readiy); p := Цх); q := Цу); new(t); tl.id ;= q; tl.neXt := p\.trail; p].trail := t; q[.count q\.comt + 1; read(x)

(4,30)

После того как на фазе ввода построена структура flaHHbij показанная на рис. 4.15, можно провести саму топологиче скую сортировку, описанную выше. Но поскольку она состоит в последовательном выборе элемента с нулевым счетчико!! предшественников, видимо, разумно вначале собрать все

head

Рис. 4.16. Список ведущих с нулевыми счетчиками.

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

[поиск ведущих с О предшественников} Р := head; head := nil; while p Ф tail do

begin q :== p; p ;= qt.next; if q],count - 0 then begin [включение qf в новую цепочку) q\.next := head; head ;= q

Если обратиться к рис. 4.15, то мы увидим, что цепочк next ведущих заменяется на цепочку, изображенную рис. 4.16. Связи, отсутствующие на этом рисунке, осталйС прежними.

(4.31)




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [ 70 ] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133