Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 37
Текст из файла (страница 37)
Мы вер- немся к этому примеру в равд. 4.4. 4.3.3. Прнпоженне: топопогнческак сортировка Хоропгпй пример пспользова~пя гибких, динамических структур данных- — процесс голо,говгшеской сортировки. Имеется в виду сортировка элементов, для которых определен нгстичногг1 порядок, т. е. упорядочение задано не на всех, а только на некоторых парах элементов. Это довольно типичная ситуация. Приведем несколько таких примеров. 1. В толковом словаре слова определяются с помощью других слов, Если слово и определено с помощью другого словам, мы обозначим это как и ~ ю, Топологическая сортировка слов в словаре означает расположение их в таком порядке, чтобы все слова, участвующие в определении данного слова, находплнсь раньше его в словаре.
'4. Динамические информационные стрвктуры 2. Задача (например, технический проект) разоивается на ряд подзадач. Выполнение одних подзадач обычно должно предшествовать выполнснию других подзадач. Если подзадача и должна предшествовать подзадаче ш, мы пишем о ( ш. Топологическпя сортировка означает выполнение подзадач в таком порядке, чтобы перед началом выполне. ния каждой подзадачи все необходимые для этого подзадачи были уже выполнены. 3, В университетской програмьте одни предметы опираются на материал другах, поэтому некоторые курсы студенты должны прослушать раньше других.
Если курс и содержит материал для курса тп, мы пишем п(ю. Топологическая сортировка означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того, на материале которого он основан. 4. В программе некоторые процедуры могут содержать вызовы других процедур. Если процедура и вызывается в процедуре тп, мы обозначаем это как и( ю.
Топологическая сортировка предполагает расположение описаннй процедур в таком порядке, чтобы вызываемые процедуры описывались раньше тех, которые их вызывают "). В общем виде частичный порядок на множестве 5 — это отношение между элементами этого множества. Оно обозначается символом (, читается «предшествует» н удовлетворяет трем следующим свойствам (аксиомам) для любых различных элементов х, и и г из 5: (1) если х(у и у(г, то х(г (транзитивность), (2) если х(у, то не (т(х (асимметричность), (4.2?) (3) не х(х (иррефлексцвность).
По понятным соображениям мы будем считать, что множество 5, которое нужно топологнческп рассортировать, является конечным. Поэтому отношение частичного порядка можно проиллюстрировать с помощью диаграммы пли графа, в котором вершины обозначают элементы 5, а стрелки изображают отношение порядка. Пример приведен на рпс, 4.13. Цель топологической сортировки — преобразовать частич.
ный порядок в линейный. Графически это означает расположеняе вершин графа в ряд так, чтобы все стрелки были направлены вправо, как показано на рпс, 4.14. Свойства (1) и (2) частичного порядка обеспечивают отсутствие циклов. Это как раз н есть то необходимое условие, прп котором возможно преобразование к линейному порядку. ') Очевидно, что непольаованпе рекуренн делает невозможным такое упорядочение. — Прим. перев. 4.3. Линейные списки 2!3 Как найти одно из возможных линейных упорядочснийр Рецепт достаточно прост. Мы начинаем с того, что выбираем капой-либо элемент, которому ие предшествует никакой другой (хотя бы один такой элелтент существует, иначе имелся бы цикл). Этот элемент помсщается в начало списка и искл!очается из множества 5. Оставшееся множество по-прежнему Рис.
4.13 '!астично упоридоченное мноткестао. частично упорядочено; таким образом, можно вновь применить тот тке самый алгоритм, пока множество не станет пустым. Для того чтобы подробнее сформулировать этот алгоритм, нужно описать структуры данных, а также выбрать представление 5 н отношения порядка. Это представление зависит от Рис. 4.!4. Линейное расположение частично упоридочеипого мно;кестаа, прньедеииого на рис.
4.!3. выполняемых действий, особенно от операции выбора элемента без предшественников. Поэтому каждыи элемент удобно представить тремя характеристиками: идентифицирующим ключом, множеством следующих за иим элементов (ипосиьедователейа) и с !етчиком предшествующих элементов («предшествсиников»). Поскольку и — число элементов в нс задано а рг!ог(, это множество удобно организовать в виде связанного списка.
Следовательно, каждый дескриптор элемента содержит сщс поле, связывающее его со следу!ошпм элементом списка. Мы будем считать, что ключи — это целыс 4. Динамические информанионные структуры 2!4 числа (необязательно последовательные от 1 до и). Аналогично множество последователей каждого элемента можно представить в виде связанного списка.
Каждый элемент сшюка послсдователей неким образом идентифицирован и связан со следующим элементом этого списка Если мы назовем дескрипторы главного списка, в котором каждый элемент пз 5 содержится ровно один раз, ведун!пми (1спс/егз), а дескрипторы списка последователей ведожьыш (/гп/!егэ), то мы получим такие опцсапня типов данных: туре !ген — -- (!ерс1сг; гге/ = (ггадег; !еаг/ег = тесовая йеу, соип/; /лгеуеГ; /гад: Пе!"; пгхг: /ге! епй; гга//ег = гесвгй 1д: !ген'; пех/; 1ге/' епв (4.28) 1(2 2(4 4(5 2( !О 4(8 6 (3 1(3 3(5 5(8 7(5 7(9 9(4 (4.29) 9( !О Первая часть программы топологической сортировки должна прочитать входной файл н преобразовать входные данные в структуру списка.
Это производится последовательным чтением пар ключей х н у (х(у). Обозначим ссылки на нх представления в списке ведущих через р и с/. Этн записи ищутся в списке и, сслп их там нег, добавляются к псму. Эту задачу выполняет функция, называемая ! (1оса1ед). Затем к списку ведомых для элемента х добавляется новый дескриптор, идентифицированный как у, счетчик предшественников для у увеличивается на !.
Такой алгоритм соответствует фазе ввода (4,30). На рнс. 4.!5 показана структура, сформированная при обработке входных данных (4.29) с помощью алгоритма (4.30). В этом фрагменте программы есть обращения к функции /,(ш), дающей ссылку па компоненту списка с ключом вч (см. также программу 4.2).
Мы предполагаем, что последовательность входных пар клю* Предположим, что множество 5 н озношения порядка на нем первоначально заданы в виде последовательности пар ключей во входном файле. Входные данные для примера, изображенного на рис. 4,!3, показаны в (4.29), где символы добавлены для ясности: 216 4. Ркинаиикескгге инйориахионнвге структуры чей заканчивается дополнительным нулем.
(Фаза ввода) геад(х); ггеи:(йеаг1); уаг! г йеад; х:=- О; ттЬ11е х ~ О йо Ьек1п геаи(у)' р ' к'(х)' г1 ' х(у)' (4.30) ггега(г); г"1.гд:= д; 11.пех1 г= р'1.1гагу; р1.1гаг1:= 1; 41.соггггг:= 4).соиггу + 1; ге ад(х) епй После того как на фазе ввода построена структура данных, показанная на рнс. 4.15, можно провести саму топологическуго сортировку, описанную выше. Но поскольку она состоит в последовательном выборе элемента с нулевым счетчиком предшественников, видимо, разумно вначале собрать все Рис. 4,16. Сиисок ведущих с иуиевымн счетчиками такие элементы в связанную цепочку.
Поскольку мы знаем, что исходная цепочка ведущих впоследствии не понадобится, то жс самое поле тгех1 можно использовать повторно для связывания в цепочку ведущих, не пмеюнгнх предшественников. Такая замена одной цепочки на другую часто встречается при работе со списками.
Это подробно описано в (4,31); для удобства новая цепочка строится в обратном порядке. (поиск ведущгггс с О иредигесптвенников) р:= Леад; Асад;= п11,' ттЬИе р Ф 1аг'1йо Ьеа1п г1 г =- р; р:=- Ч г мех1; 11 д1,саггггу = О 1йеп (4.31) Ьеа1п (включеиие д1 в новую цепочку) г11лехг:.
Ьеад; аеас( '= д епй епй Если обратиться к рис. 4.15, то мы увидим, что цепочка пеку ведущих заменяется на цепочку, изображенную на рис. 4,16. Связи, отсутствующие на этом рисунке, остались прежними, 4.8. Линейное сниски 2!7 После всех этих подготовительных действий, направлениых иа то, чтобы выработать подходящее представление частпчио упорядочеииого множества 5, мы можем, наконец, перейти к собственно топологической сортировке, т. е. формпроваиию выходкой последовательности. В первом, грубом приблихсеипи это мох!по описать слсдующпм образом: Оператор в (4.32), который осталось уточиить, осуществляет еще один проход по списку 1см.
схему 14,17)). На каждом шаге вспомогательная переменная р указывает иа ведущий дискриптор, счетчик которого нужно умепьшить и проверить иа равенство нулю. пЫ1е г чо пй до Ьеа)в р:= г~.Ы; р!.сввп!:= р).сои!и — 1; Ир).сои>гг = О ейеп Ьев!и !включение р1 в список ведуи4их) р!лехт:= д; д:= р епй; 7:= 41.пехг (4.33) На этом завершается разработка программы топологиче. ской сортировки. Обратите внимание, что был введен счетчик г для подсчета ведущих дескрипторов, сформированных на фазе ввода. Этот счетчик уменьшается каждый раз, когда ведущий дескриптор выводится иа фазе вывода. Поэтому ои должен вновь стать равным О в конце работы программы. Если ов ие смог вернуться к О, это указывает, что в структуре остались элементы и среди аих иет таких, у которых отсутствуют предшественники. Очевидно, что в этом случае миожсство 5 ие является частичпо упорядочеипым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
