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

Процедуры INITIAL, MERGE и FIND представлены в листинге 5.14. На рис. 5.10 показан пример описанной структуры данных, состоящей из множеств 1 = {1, 3, 4}, 2 - {2} и 5 = {5, 6}.

Листинг 5.14. Операторы АТД MFSET

procedure INITIAL ( А: nametype; х: elementtype; var С: MFSET );

{ инициализирует множество с именем А, содержащее элемент х } begin

C.names[x].setname:= А; C.names[x] .nextelement:= 0;

{ нулевой указатель на конец списка элементов А } C.setheadersiA].count:= 1; С. setheaderslA] . firstelement: = к

end; { INITIAL }

procedure MERGE ( A, B: nametype; var C: MFSET ) ;

{ Слияние множеств A и В. Результат присваивается меньшему множеству }

1: О. .ц; (используется для нахождения конца меньшего списка} begin

if C.setheaderstA].count > С.setheaders[В].count then begin

{ A большее множество, поэтому сливается В в А j { находится конец В, изменяется имя на А } i:= C.setheaders[B].firstelement; while C.names[i].nextelement <> 0 do begin

C.namesti] .setna;ne:= A;

i: = C:names[i].nextel&nent

end;

{ список A добавляется в конец списка В,

результату слияния присваивается имя А } { теперь i - индекс последнего элемента В } C.names[i].setname:= А;

C.namesli].nextelement:= C.setheadersiA].firstelement; C.setheadersiA].firstelement:=

C. setheaders [B] .firstelement; C.setheadersiA].count:= C.setheaders[A].count +

С. setheaders IB] .count;

C.setheadersIB].count:= 0; C.setheaders[B].firstelement:= 0

{ последние два шага необязательны, т.к.

множества В больше не существует }

else { В по крайней мере не меньше А } { код для этого случая такой же,

как и выше, с заменой местами А и В }

end; { MERGE }

function FIND ( x: 1..Л; var C: MFSET );

{ возвращает имя множества, которому принадлежит элемент х } begin

return (С. names [х] . setname)

end; { FIND }



s"

count firstelement setheaders

2 3" 4"

б"

setname nextelement names

Рис. 5.10. Пример структуры данных MFSET

Реализация АТД MFSET посредством деревьев

Другой, полностью отличный о ранее рассмотренных, подход к реализации АТД MFSET применяет деревья с указателями на родителей. Мы опишем этот подход неформально. Основная идея здесь заключается в том, что узлы деревьев соответствуют элементам множеств и есть реализация, посредством массивов или какая-либо другая, отображения множества элементов в эти узлы. Каждый узел, за исключением корней деревьев, имеет указатель на своего родителя. Корни содержат как имя компонента-множества, так и элемент этого компонента. Отображение из множества имен к корням деревьев позволяет получить доступ к любому компоненту.

На рис. 5.11 показаны множества А = {1, 2, 3, 4}, В = {5, 6} и С = {7), представленные в описанном виде. На этом рисунке прямоугольники являются частью корней, а не отдельными узлами.


имя = с

9 ©

©

Рис. 5.11. Представление АТД MFSET набором деревьев

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

Операция слияния делает корень одного дерева сыном корня другого. Например, при слиянии множестве и В (см. рис. 5.11), когда результат слияния получает имя А, узел 5 становится сыном узла 1. Результат слияния показан на рис. 5.12. Однако неупорядоченные слияния могут привести к результату в виде дерева из и узлов, которое будет простой цепью узлов. В этом случае выполнение оператора FIND для любого узла такого дерева потребует времени порядка О(л). В этой связи заметим, что



хотя слияние может быть выполнено за 0(1) шагов, но в обшей стоимости всех выполняемых операций может доминировать операция поиска. Поэтому, если надо просто выполнить т слияний и п поисков элементов, данный подход может быть не самым лучшим выбором.


Рис. 5.12. Слияние множества А в множество В

Однако есть способ, гарантируюший при наличии и элементов выполнение операции поиска не более чем за O(logn) шагов. Надо просто в кавдом корне хранить количество элементов данного множества, а когда потребуется слияние двух множеств, корень меньшего дерева станет сыном корня большего дерева. В этом случае при пе-ремешении узла в новое дерево расстояние от этого узла до корня увеличится на единицу, а новое дерево содержит, по крайней мере, в два раза больше узлов, чем дерево, которому принадлежал данный узел ранее. Поэтому, если всего п элементов, то нет узла, который перемешался более чем logn раз, поскольку расстояние от любого узла до корня никогда не превышает logn. Отсюда вытекает, что кавдое выполнение оператора FIND требует времени не больше O(logn).

Сжатие путей

Сжатие путей еше один метод ускорения выполнения операторов АТД MFSET. В этом методе в процессе поиска при прохождении пути от некоторого узла до корня все узлы, расположенные вдоль этого пути, становятся сыновьями корня дерева. Эта операция выполняется в два этапа: сначала проходится путь от узла до корня, а затем при осушествлении обратного хода по уже пройденному пути каждый узел поочередно становится сыном корня.

Пример 5.7. На рис. 5.13,а показано дерево перед выполнением поиска узла с элементом 7, а на рис. 5.13,6 - результат перемешения узлов 5 и 7 в сыновья корня. Узлы 1 и 2 не перемешаются, так как узел 1 - это корень, а узел 2 уже является сыном корня. П

Сжатие путей не влияет на выполнение оператора MERGE, поскольку этот оператор выполняется за фиксированное время, но ускоряет последуюшие выполнения оператора FIND, так как укорачиваются пути от узлов к корню и вместе с тем на это затрачивается относительно немного усилий.

К сожалению, анализ среднего времени выполнения операторов FIND с использованием сжатия путей очень труден. Будем исходить из того, что если не требовать, чтобы меньшие деревья сливались в большие, то на выполнение и операторов FIND потребуется время, не превышаюшее 0(п logn). Конечно, на выполнение первых операторов FIND может потребоваться время порядка 0(п) на один оператор, если деревья состоят из одной цепочки узлов. Но сжатие путей может очень быстро изменить





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

0.0027