Д. Кнут - Искусство программирования том 1 (1119450), страница 73
Текст из файла (страница 73)
е. количество отношений у -ч сс во входном потоке данных), а ТОР [сс] — связь с началом сииска прямыс потомков объекта lс. Последний список содержит элементы в формате где ЗОС вЂ” прямой потомок объекта к и ИЕХТ вЂ” следующий элемент списка. Для демонстрации этих условных обозначений на рис. 8 схематически показано содержимое памяти, соответствующее входному потоку данных (18). Используя такую организацию памяти, нетрудно создать искомый алгоритм.
Для этого следует вывести узлы, в которых значение поля СОРИТ равно нулю, и на единицу уменьшить значения полей СОРИТ для всех потомков таких узлов. Уловка здесь заключается в том, чтобы избежать "поиска" узлов, в которых значение поля СОРИТ равно нулю, и это можно выполнить за счет организации очереди, содержащей такие узлы. Связи для этой очереди хранятся в поле СОРИТ, которое уже выполнило свое назначение. Для ясности в приведенном ниже алгоритме обозначение ЦЕ1ИК [й] используется вместо СООИТЩ, когда это поле больше не применяетгя для хранения значений счетчика. Алгоритм Т (Топологическал сортировка). В этом алгоритме в качестве входного потока используется последовательность отношений ] .< А, обозначающих, что объект у' предшествует объекту Й в некотором частичном упорядочении при условии, что 1 < у, А < п.
Выходной поток состоит из множества п объектов, расположенных в линейном порядке. При этом используются следующие внутренние таблицы: ЦЫИК[0], СООИТ[1] = Ц11ИК[1], СООИТ[2] = ЦЕ1ИК[2], ..., СООИТ[п] = ЦЕ1ИК[п]; ТОР [ц, ТОР[2], ..., ТОР [и]; пул с одним узлом для каждого отношения входного потока и с указанными выше полями ЕОС и ИЕХТ; переменная связи Р., которая используется для ссылки на узлы в пуле; целочисленные переменные Р и й, применяемые для ссылок на начало и конец очереди, связи которых находятся в таблице Ц1,1ИК; и, наконец, переменная М, позволяющая подсчитать количество объектов, которые необходимо поместить в выходной поток. Т1.
[Инициализация.] Ввести значение п, Установить СООМТ[А] с — 0 и ТОРЫ е- Л для 1 < /с < п. Установить И е- п. Т2. [Следующее отношение.) Получить отношение ] -с /с из входного потока. Если входной поток исчерпан, перейти к шагу Т4. ТЗ. [Запись отношения.) Увеличить на единицу значение СООИТ[А]. Установить Р с= АУА11, БОС(Р) +- Й, ИЕХТ(Р) +- ТОР[)], ТОР[у] +- Р. [Это операция (8).) Вернуться к шагу Т2.
Т4. [Поиск нулей.) (В этом месте завершается ввод, и входной поток (18) теперь имеет понятный для компьютера вид, представленный на рис. 8. Следующий шаг заключается в инициализации очереди выходного потока, который связан с помощью поля ЦЫИК.) Установить Е е- 0 и Ц11ИК[0] е- О. Для 1 < А < п проверить значение СООИТ [А] и, если оно равно нулю, установить Ц11ИК [И] < — А и К +- й. После выполнения этого действия для всех А установить Р е- ЦЕ1ИК [0] [теперь оно будет содержать первое значение /с, для которого СООИТ[А] равно нулю), Тб.
[Вывод начала очереди.] Вывести значение Р. Если Р = О, перейти к шагу Т8, в противном случае установить М е- И вЂ” 1 и установить Р с- ТОР[Р]. [Так как таблицы ЦЕ1ИК и СООИТ перекрываются, получим Ц11ИК [Е] = О. Следовательно, условие Р = 0 выполняется, когда очередь пуста.) Тб. [Удаление отношений.] Если Р = Л, перейти к шагу Т7. В противном случае уменьшить на единицу значение СООИТ[БОС(Р)], а если оно уже равно нулю, установить ЦЕ1ИК[Е] с — БОС(Р) и Е 1 — ЯОС(Р). Установить Р +- МЕХТ(Р) и повторить этот шаг.
(Таким образом удаляем из системы все отношения вида Р -С й для некоторого /с и располагаем новые узлы в очереди, когда все их предшественники уже выведены.) ТТ. [Удаление из очереди.] Установить Р ~- Ц11МК [Р] и вернуться к шагу Т5. Т8. [Конец процесса.] Прекращение работы алгоритма. Если И = О, получим в результате искомое "топологическое упорядочение" пронумерованных объектов, Программа Т (Топологичвскал сврглироека). В этой программе (рнс. 9) нужно учесть следующие равенства: г16 = М, г15 = указатель буфера, г14 = А, г13 = 1' и Е, г12: — АЧА1Е и Р, г11 = Р, ТОР[1] = Х+1(4:5), СОПИТ[А] = ОЫМК[А] = Х+ А(2:3).
01 э БУФЕРИЗАЦИЯ И ОПРЕДЕЛЕНИЕ ПОЛЕЙ ОЯ СООМТ ЕОО 2:3 Определение символьных ОУ ОьТИК ЕОО 2:3 имен полей. 04 ТОР ЕОО 4: Б Об ЗОС ЕОО 2:3 Об ИЕХТ ЕОО Ф:Б 07 ТАРЕ1И ЕОО 1 08 ТАРЕООТ ЕОО 2 Ввод с ленты 1. Вывод на ленту 2 за которыми следует нуль. В противном случае М пронумерованных объектов не бувут выведены из-за того, что они образуют замкнутую петлю, а это нарушает гипотезу о частичном'упорядочении. (В упр. 23 рассмотрен алгоритм печати содержимого такой петли,) ! Читателю наверняка будет полезно попробовать вручную применить этот алгоритм для входного потока (18). Алгоритм Т демонстрирует прекрасное взаимодействие между методами организации последовательной и связанной памяти. Последовательная память используется для основной таблицы Х[Ц, ..., Х[я], которая содержит объекты СОПИТ[А] и ТОР [А], поскольку на шаге ТЗ предстоит ссылаться на "произвольно выбранные" части этой таблицы.
(Однако, если входной поток является символьным, для более быстрого поиска следует использовать другой тип таблицы, который описывается в главе 6.) Связанная память применяется для таблиц, в которых "один объект непосредственно следует за другим" (ипше61аге эиссеээогэ), так как во входном потоке эти объекты никак не упорядочены, Очередь ожидающих вывода узлов хранится внутри последовательной таблицы, связывая, таким образом, узлы в порядке их вывода. Для этого связывания вместо адресов используется индекс таблицы. Иначе говоря, если Х [А] — начало очереди, получим Р = А вместо Р = ЕОС(Х[А]).
Операции обработки очереди, используемые на шагах Т4, Т6 и Т7, не идентичны операциям (14) н (17), так как в данном случае используются преимущества особых свойств очереди. Во время выполнения этой части алгоритма никакие узлы не придется создавать или возвращать в свободное пространство памяти. При программировании алгоритма Т на языке ассемблера компьютера МТХ следует учесть несколько интересных особенностей. Так как в данном алгоритме в таблице не предпринимается никаких удалений (поскольку не требуется освобождать память для ее последующего использования), операция Р ~ АЧА11. может быть выполнена чрезвычайно просто, т.
е, так, как показано ниже, в строках 19 и 32. В такой ситуации не потребуется содержать связанный пул памяти, а новые узлы можно выбирать последовательно. Ввод и вывод данных в программе предполагается выполнять с магнитной ленты согласно упомянутым выше соглашениям, но для упрощения кода в данном случае опущена буферизация. Читатель вряд ли столкнется с какими-либо трудностями при чтении этого кода, поскольку код полностью соответствует алгоритму Т. Здесь также показано, насколько эффективно может быть организовано использование индексных регистров, что является важным аспектом обработки связанной памяти.
Рис. О. Топологическая сортировка, Буферная область. Метка конца буфера. в+100 -1 1 1 и+1 и+1 и+1 1 1 т+Ь т+Ь Ь Ь вЂ” 1 Ь вЂ” 1 Ь вЂ” 1 т т т 99 ВОГГЕЕ 10 11 е ФАЗА 13 ТОРБОЕТ 18 14 1Н 18 1б 17 18 19 30 31 2Н 33 38 34 38 Бб 37 38 ЗН 39 80 81 83 88 84 88 88 87 88 ОЕ10 СОИ ВВОДА 1И 1ВОБ 1ЛБ ЕИТ4 ЯТЕ ОЕС4 14ИИ ЕИТ2 ЕНТБ 103 1ЗР 1ЗХ ХН 1ВОБ ЕИТБ 1НР 104 ЬОА ХИСА БТА 1НС2 10А БТА БТ4 БТ2 1ИСБ 1НР ВОРГХ3(ТАРЕХИ) с (ТАРЕХИ) ВОРГЕВ+1 0,6 Х,4 1 е 2 Х,Б ВОРГЕВ+2 О,Б ЗГ ВОГГЕЕ(ТАРЕ1И) «(ТАРЕ1И) ВОРГЕЕ 2В 1,6 Х.4(СООИТ) 1 Х,4(СООИТ) 1 Х.З(ТОР) 0,2(ИЕХТ) 0,2(БОС) Х,З(ТОР) 2 2В ~~~.
и« . с РЬ блок ленты; доискаться завершения. И+- и. Установить СООИТ[)с) +- 0 и ТОР[?с) +- й для О < )с < н. (Учесть, что 01.1ИХ[0) +-0 на шаге Т4.) Свободная область начинается после Х Ы. Приготовиться к чтению первой пары (у,?с). Т2. Сл ю ее отношение. Верно ли, что 1 > О? Входной поток исчерпан? Метка конца замечена; считать другой блок с ленты, дождаться завершения. Переустановить указатель буфера. ТЗ. Зались отношения, СОВЕТ [А) +1 -+ СООВТ[Ы. АТА11 С вЂ” АТА11+ 1.
ТОР Ц] -+ ИЕХТ(Р) . )с -+ БОС(Р). Р -+ ТОР [1З. Увеличить указатель буфера. и > А > 1. и+1 и+1 и с — 1 с — 1 и — а и — а и 1 1 1 99 4В 46 41 49 49 4Н 44 45 46 47 46 49 50 51 БИ 59 59 54 55 56 57 56 59 бб 61 бН 69 69 64 65 66 67 68 69 70 ?Н 71 79 БН 7Э 74 75 Х 100 О(ТАРЕХИ) ЕИТ4 0,6 ЕИТБ -100 ЕИТЗ О Ы)А Х,4(СООИТ) зи «+3 БТ4 Х,З(ЦЫМЕ) ЕНТЗ 0,4 ОЕС4 1 14Р 4В ФАЗА СОРТИРОВКИ Ы)1 Х(Ць1НК) .)ВОБ «(ТАРЕООТ) БТ1 ВОРРЕЕ+100,6 112 ВР 1ИСБ 1 ЗБИ «+3 ООТ ВОРРЕЕ(ТАРЕООТ) ЕИТБ -100 ОЕСБ 1 Ы)2 Х,1(ТОР) 122 7Р 104 0,2(БОС) 1,0А Х,4(СООИТ) РЕСА 1 БТА Х,4(ОООН?) ЭАР «+3 БТ4 Х,З(ЦХТМК) ЕМТЗ 0,4 1.02 0,2(ИЕХТ) 12Р 6В «01 1,1(СЫНК) ЛМР 68 СОТ ВОРРЕМ(ТАРЕООТ) 10С 0(ТАРЕООТ) Ньт 0,6 ЕМО ТОРБОЕТ Перемотать ленту ввода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
