степени даже более естественный альтернативный способ, а в конце этой главы приводятся другие методы. Действительно, ни одна из перечисленных выше операций не может рассматриватьса как единственный возможный способ реализации того или иного действия. Они представляют собой лишь примеры основных приемов работы со связанными списками. Читателю, который не обладает богатым опытом работы с такими методами, прежде чем продолжить чтение этой книги, будет полезно еще раз перечитать приведенный выше материал данного раздела.

До сих пор в настоящей главе обсуждались способы вьшолнения некоторых операций с таблицами, но форма обсуждения всегда была достаточно "абстрактной" в том смысле, что никогда не демонстрировались реальные программы, в которых использовались бы данные методы. Человек не станет изучать абстрактные модели некоторой проблемы, если его не заинтересовали примеры. Рассмотренные до сих пор операции, т. е. вставка и удаление данных в списках с изменяемыми размерами, а также использование таблиц в виде стеков или очередей имеют настолько широкое применение, что читатель наверняка еще не раз встретится с ними и сможет оценить их важность. Однако в остальной части данной главы мы покинем область абстрактных рассуждений и приступим к изучению важных практических примеров использования этих методов.

Первый пример такой практической задачи называется топологической сортировкой {topological sorting), которую часто приходится выполнять при проектировании сетей, в так называемых PERT-диаграммах, и даже в лингвистике. Действительно, она может быть очень полезной всегда, когда приходится выполнять частичное упорядочение {partial ordering). Частичным упорядочением некоторого множества 5 называется такое отношение между элементами множества 5, которое может быть обозначено символом ":" и обладает следующими свойствами для любых X, у и Z (причем необязательно разных) элементов множества 5.

i) Если X :<у и у :< z,TO X :< Z. (Транзитивность.) п) Если X :< у и у :< X, то X = у. (Антисимметричность.) iii) X <х. (Рефлексивность.)

X < у можно трактовать так: "а; предшествует или равно у". Если х < у и х ф у, будем обозначать это отношение через х у и трактовать его как "х предшествует у". Легко видеть, что из (i)-(iii) можно получить следующее.

i) Если хуиуг,тох г. (Транзитивность.) ii) Если X у, то у X. (Антисимметричность.) iii) X -х. (Нерефлексивность.)

Отношение, обозначенное через у х, трактуется так: "у не предшествует х". Если сначала определить отношение -< со свойствами (i)-(iii), то описанный выше процесс можно вьшолнить в обратной последовательности, т. е. определить отношение X -<у, как такое, для которого х у или х = у. Тогда для него должны выполняться условия (i)-(iii). Следовательно, свойства (i)-(iii) и (i)-(iii) можно рассматривать как определения частичного упорядочения. Обратите внимание на то, что свойство (ii) на самом деле является следствием свойств (i) и (iii), однако свойство (ii) не следует из свойств (i) и (iii).

Частичное упорядочение довольно часто встречается не только в математике, но и в повседневной жизни. Примерами его использования в математике являются отношение х < у между действительными числами х и у, отношение х С у между множествами, отношение х\у {х делит у) между положительными целыми числами. В PERT-диаграммах S - это набор заданий, которые следует выполнить, а отношение X -< у означает "а; должно быть выполнено раньше у".

Рис. 6. Частичное упорядочение.

Вполне естественно было бы предположить, что S является конечным множеством, поскольку оно используется в компьютере. Частичное упорядочение конечного множества всегда можно представить в виде диаграммы, изображенной на рис. 6, на которой объекты изображены маленькими квадратиками, а отношение между ними - стрелками между этими квадратиками. В таком случае х у означает, что от квадратика с ярлыком х к квадратику с ярлыком у проходит некоторый путь, указанный стрелками. Свойство (ii) частичного упорядочения означает, что в такой схеме не существует замкнутых петель (т. е. не существует путей, замкнутых на себя). Например, если в схеме на рис. 6 провести стрелку от квадратика 4 к квадратику 1, то для них нельзя будет установить отношение частичного упорядочения.

Задача топологической сортировки заключается в установлении частичного порядка среди объектов, упорядоченных в линейном порядке, т. е. в таком расположении объектов линейной последовательности ai02...a„, чтобы для любых Uj -< Ofc выполнялось условие j < к. Графически это означает, что квадратики следует расположить на одной линии так, чтобы все стрелки были направлены вправо (рис. 7). Такое переупорядочение не всегда возможно, хотя совершенно ясно, что его нельзя выполнить при наличии замкнутых петель. Следовательно, искомый алгоритм интересен не только тем, что он позволяет выполнить очень полезную операцию, но и тем, что он доказывает, что данная операция возможна для любого частичного упорядочения.

Рис. 7. Отношение упорядочения, показанного на рис. 6, после выполнения топологической сортировки.

в качестве примера топологической сортировки представим себе большой словарь с определениями технических терминов. Запишем, что W2 -<wi, если определение термина wi пмо или косвенно зависит от определения термина шг- Это отношение является частичным упорядочением при условии, что не существует никаких "циклических определений". Тогда задача топологической сортировки зэг ключается в поиске такого способа упорядочения терминов в $том словаре, чтобы никакой термин не использовался до того, как он будет определен. Аналогичные проблемы возникают при создании программ для обработки объявлений в некоторых ассемблерных и компилируемых языках, а также при создании руководства пользователя с описанием языка программирования или при написании учебников об информационных структурах.

Существует очень простой способ выполнения топологической сортировки. Сортировку следует начать с объекта, которому не предшествует никакой другой объект данного множества. Этот объект удаляется из исходного множества S и располагается первым в итоговой последовательности. Таким образом итоговая последоваг тельность частично упорядочивается и процесс снова повторяется до тех пор, пока все множество не будет рассортировано. Например, на рис. 6 сортировку можно было бы начать, удалив элемент 1 или 9, затем (после удаления элемента 1) - удалив элемент 3 и т. д. Этот алгоритм может оказаться бесполезным только тогда, когда найдется такое непустое частично упорядоченное множество, каждому элементу которого предшествует другой элемент. Но если каждый элемент имеет предшественника, то можно построить последовательность произвольной длины ЬьЬз) Ьз,..., в которой bj+i -< bj. Так как S является конечным множеством, для некоторого j < к должно выполняться условие bj = bk. Но тогда предполагается, что выполняется условие Ь :< bj+i, а это противоречит свойству (ii).

Для эффективной реализации рассмотренного процесса на компьютере необходимо организовать выполнение перечисленных выше действий, т. е. поиск объектов без предшественников, а также их удаление из множества. На окончательный вид алгоритма также повлияют заданные характеристики операций ввода и вывода. В общем случае программа должна уметь воспринимать символьные имена объектов и обрабатывать гигантские множества, размер которых может даже превышать размер оперативной памяти компьютера. Однако обсуждаемые здесь основные идеи могут легко затеряться среди таких усложнений. Поэтому более подробно методы эффективной обработки символьных данных описываются в главе 6, а задачу управления большими сетями читателю предлагается обдумать самостоятельно в качестве интересного упражнения.

Далее предположим, что сортируемые объекты пронумерованы от 1 до п в произвольном порядке. Вводная часть программы будет находиться на накопителе на магнитной ленте 1. Каждая магнитная запись содержит 50 пар чисел, где пара (j, к) означает, что объект j предшествует объекту к. Однако первая пара выглядит как (0,п), где п - это количество объектов. Ввод завершается парой (0,0). Предположим, что и и все пары помещаются в памяти компьютера, а потому необязательно проверять наличие свободного места в памяти во время ввода этих данных. Выводиться объекты будут уже в отсортированном порядке на накопитель на магнитной ленте 2, причем за ними будет следовать значение 0.