Главная Промышленная автоматика.

begin

1. Т0;

2. VS<-0;

3. for каждый узел vV йо добавить одноэлементное множе-

ство {v} к VS;

4. while VS> 1 do

begin

5. выбрать из Е ребро {v, w) наименьшей стоимости;

6. удалить (у, w) из Е;

7. и V а w принадлежат разным множествам W, и

из VS then begin

8. заменить и в VS на Ui U W;

9. добавить (v, w) к Т end

Рис. 4.1. Алгоритм для нахождения остовного дерева наименьшей стоимости.

дерева сливаются, а в строке 9 ребро (v, w) добавляется к окончательному остовному дереву.

Строка 7 предполагает, что мы можем найти имя того множества в VS, которое содержит конкретный узел. (Вид имен, действительно используемых для множеств в VS, не важен, так что можно употреблять произвольные имена.) По существу, строка 7 предполагает, что мы можем эффективно выполнить основную операцию НАЙТИ. Аналогично строка 8 предполагает, что над непересекающимися множествами узлов мы можем выполнить операцию ОБЪЕДИНИТЬ.

Отыскать структуру данных, на которой быстро выполняется операция ОБЪЕДИНИТЬ или НАЙТИ, довольно легко. Но здесь требуется, чтобы на одной структуре данных можно было легко реализовать обе операции ОБЪЕДИНИТЬ и НАЙТИ. Более того, поскольку выполнение операции ОБЪЕДИНИТЬ в строке 8 зависит от результата выполнения операций НАЙТИ в строке 7, требуемая последовательность операций ОБЪЕДИНИТЬ и НАЙТИ должна выполняться в префиксном режиме. Две такие структуры изучаются в разд. 4.6 и 4.7.

Рассмотрим последовательность операций, выполняемых на множестве ребер Е. В строке 5 применяется основная операция M1N, а в строке 6 - операция УДАЛИТЬ. Хорошая структура данных для этих двух операций нам уже встречалась - сортирую-

S* 131



щее дерево из разд. 3.4. (Хотя там с помощью сортирующего дерева разыскивался наибольший элемент, должно быть ясно, что с его помощью можно также найти и наименьший элемент.)

Наконец, множество Т ребер остовного дерева нуждается только в операции ВСТАВИТЬ в строке 9 для добавления к Т нового ребра. Здесь достаточно простого списка. □

4.2. МЕТОД РАССТАНОВКИ

Кроме вопроса о том, какие операции появляются в данной последовательности о, возникает еще один важный вопрос, связанный с выбором подходящей структуры данных для выполнения а. Это вопрос о размере базы данных (универсального множества), на которой работают операции из о. Например, в гл. 3 мы видели, что с помощью сортировки вычерпыванием можно упорядочить последовательность из п элементов за линейное время, если элементами рассматриваемого множества являются целые числа, заключенные между подходящими границами. Однако если эти элементы берутся из произвольного линейно упорядоченного множества, то наилучшим временем, которого мы смогли добиться, было время 0(п log п).

В данном разделе мы исследуем задачу о том, как поддержать определенную структуру в изменяющемся множестве S. Новые элементы будут добавляться к S, старые - удаляться из S, и время от времени надо будет отвечать на вопрос: "Принадлежит ли в данный момент элемент х множеству S?" Эта задача естественно моделируется словарем; нам нужна структура данных, которая позволит удобно выполнять последовательности, состоящие из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ. Мы будем предполагать, что элементы, которые могут появиться в S, берутся из очень большого универсального множества, так что представлять S в виде двоичного вектора неразумно с практической точки зрения.

Пример 4.2. Транслятор или ассемблер следит за "таблицей символов" всех идентификаторов, которых он встретил в транслируемой программе. Для большинства языков программирования множество всех возможных идентификаторов очень велико. Например, в Фортране около 1,62x10» возможных идентификаторов. Поэтому нереально представить таблицу символов массивом с одним входом для каждого возможного идентификатора независимо от того, появляется он в программе на самом деле или нет.

Операции, производимые транслятором с таблицей символов, относятся к двум типам. Во-первых, надо добавлять в таблицу новые идентификаторы, когда они появляются. Эта работа включает в себя образование той ячейки в таблице, где запоминается конкретный идентификатор и где можно запомнить данные о нем (например, вещественный он или целый). Во-вторых, время от времени трансля-



4.2. МЕТОД РАССТАНОВКИ

тор может затребовать информацию о каком-нибудь идентификаторе (например, имеет ли этот идентификатор тип "целое").

Таким образом, структура данных, способная обеспечить выполнение операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, вероятно, достаточна для реализации таблицы символов. И действительно, структура данных, обсуждаемая в этом разделе, часто используется для реализации таблицы символов. □

Мы рассмотрим способ расстановки, обеспечивающий выполнение не только операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, необходимых для построения таблицы символов, но и операции УДАЛИТЬ. Известно много вариантов этого способа, но мы обсудим здесь только основную идею.

Схема расстановки показана на рис. 4.2. Функция расстановки h отображает элементы универсального множества (например, в случае таблицы символов все возможные идентификаторы) в множество целых чисел от О до т-1. Мы будем предполагать, что для всех элементов а значение h{a) можно вычислить за постоянное время. Компонентами массива А размера т служат указатели на списки элементов множества 5. Список, на который указывает Л [i], состоит из всех тех элементов aS, для которых h(a)=i.

Чтобы выполнить операцию ВСТАВИТЬ (а, S), надо вычислить h(a) и затем просмотреть список, на который указывает Л [Л (а)] Если элемента а в этом списке нет, его надо добавить к концу списка. Чтобы выполнить операцию УДАлИТЬ(а, S), надо также просмотреть список A[h{a)\ и удалить элемент а, если он там есть. Аналогично просматривается список Л [Л (а)] и в случае операции ПРИНАДЛЕЖАТЬ (а, S).

Вычислительную сложность этой схемы расстановки легко проанализировать. С точки зрения работы в худшем случае она не очень хороша. Например, допустим, что последовательность а состоит из п различных операций ВСТАВИТЬ. Может случиться, что на всех элементах, которые надлежит вставить, А принимает одинаковые значения, так что все элементы оказываются в одном и том же спис-

Л7-1

- Список для h (a)=Q Список для Л (ah 1

•Список ff/w /У-л!?-1

Рис. 4.2. Схема расстановки.





0 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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0038