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

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

тдосйтельно длинным текстам, затем сравнивались методы идейного упорядочения (4.21) и переупорядочения списков

sentinel


w2 wl

Рйс. 4.12. Список после переупорядочения.

(4.26). Результаты измерений приводятся в табл. 4.2. К сожалению, наибольший выигрыш достигается в случаях, когда

Таблица 4.2. Сравнение методов поиска по списку

Тест 1

Тест 2

Число различных ключей

Число появлений ключей

14 341

Время поиска с упорядочением

6 207

3 200 622

Время поиска с переупорядочением

4 529

681 584

Коэффициент улучшения

1,37

4,70

почему-либо требуется другая организация данных. Мы вернемся к этому примеру в разд. 4.4.

3.3. Приложение: топологическая сортировка

Хороший пример использования гибких, динамических структур данных -процесс топологической сортировки. Имеется в виду сортировка элементов, для которых определен частичный порядок, т. е. упорядочение задано не на всех, 3 только на некоторых парах элементов. Это довольно типичная ситуация. Приведем несколько таких примеров.

- В толковом словаре слова определяются с помощью других слов. Если слово V определено с помощью другого слова w, Ыы обозначим это как v w. Топологическая сортировка слов в словаре означает расположение их в таком порядке. Чтобы все слова, участвующие в определении данного сло-

jBa, находились раньше его в словаре.



4. В программе некоторые процедуры могут содержать вы-зовы других процедур. Если процедура v вызывается в про-цедуре W, мы обозначаем это как v-w. Топологическая сортировка предполагает расположение описаний процедур в таком порядке, чтобы вызываемые процедуры описывались раньше тех, которые их вызывают*).

В общем виде частичный порядок на множестве 5 - это отношение между элементами этого множества. Оно обозначается символом <(, читается предшествует и удовлетворяет трем следующим свойствам (аксиомам) для любых различных элементов х, у и 2 из S:

(1) если л;<( г/ и У'г, то x-z (транзитивность),

(2) если х<г/, то не t/-<x (асимметричность), (4.27)

(3) к& х-К,х (иррефлексивность).

По понятным соображениям мы будем считать, что мно' жество S, которое нужно топологически рассортировать, является конечным. Поэтому отношение частичного порядка можно проиллюстрировать с помощью диаграммы или графа, в котором вершины обозначают элементы S, а стрелки изображают отношение порядка. Пример приведен на рис. 4.13.

Цель топологической сортировки-преобразовать частичный порядок в линейный. Графически это означает расположение вершин графа в ряд так, чтобы все стрелки были направлены вправо, как показано на рис. 4.14. Свойства (1). и (2) частичного порядка обеспечивают отсутствие циклов-Это как раз и есть то необходимое условие, при котором воз- можно преобразование к линейному порядку.

*) Очевидно, что использование рекурсии делает невозможным такое упорядочение. - Прим. перев.

2. Задача (например, технический проект) разбивается ряд подзадач. Выполнение одних подзадач обычно дол5кв предшествовать выполнению других подзадач. Если jiq задача v должна предшествовать подзадаче w, мы пище vw. Топологическая сортировка означает выполнени подзадач в таком порядке, чтобы перед началом выподне^ ния каждой подзадачи все необходимые для этого подзд', дачи были уже выполнены.

3. В университетской программе одни предметы опираются на материал других, поэтому некоторые курсы студенты должны прослушать раньше других. Если курс v содержит материал для курса w, мы пишем w tw. Топологическая сортировка означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того, на материале кото-рого он основан.



4.d. Линейные списки 213 - -1-

j(aK найти одно из возможных линейных упорядочений? цепт достаточно прост. Мы начинаем с того, что выбираем акой-либо элемент, которому не предшествует никакой дру- ой (хотя бы один такой элемент существует, иначе имелся L цикл). Этот элемент помещается в начало списка и исклю-ается из множества S. Оставшееся множество по-прежнему


Рис. 4.13. Частично упорядоченное множество.

частично упорядочено; таким образом, можно вновь примерить тот же самый алгоритм, пока множество не станет пустым.

Для того чтобы подробнее сформулировать этот алгоритм, нужно описать структуры данных, а также выбрать представление S и отношения порядка. Это представление зависит от


Рис. 4.14. Линейное расположение частично упорядоченного множества, приведенного на рис. 4.13.

выполняемых действий, особенно от операции выбора элемента без предшественников. Поэтому каждый элемент Удобно представить тремя характеристиками: идентифицирующим ключом, множеством следующих за ним элементов последователей ) и счетчиком предшествующих элементов Предшественников ). Поскольку п - число элементов в 5 задано а priori, это множество удобно организовать в виде Связанного списка. Следовательно, каждый дескриптор элемента содержит еще поле, связывающее его со следующим Цементом списка. Мы будем считать, что ключи - это целые




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