yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг5.14.Операторы АТД МFSET

Алгоритмы структуры данных

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

procedure INITIAL   (  A:   nametype;   x:   elementtype;  var C:  MFSET  );

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

begin

C.names[x].setname:= A;

С. names [x] .nextelement : = 0;

{ нулевой указатель на конец списка элементов А }

C.setheaders[A].count:= 1;

C.setheaders[A].firstelement:= x

end; { INITIAL }

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

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

меньшему множеству }

var

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

begin

if C.setheaders[A].count > C.setheaders[B].count then begin

{ А большее множество, поэтому сливается В в А }

{ находится конец В, изменяется имя на А }

i:= C.setheaders[B].firstelement;

while C.names[i].nextelement <> 0 do begin

C.names[i].setname:= A;

i:- C.names[i].nextelement

end;

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

результату слияния присваивается имя А }

{ теперь і — индекс последнего элемента В }

С.names[i].setname:= A;

C.names[i].nextelement:= C.setheadersfA].firstelement; C.setheaders[A].firstelement:=C.setheaders[B].firstelement; C.setheaders[A].count:— C.setheaders[A].count +C.setheaders[B].count; C.setheaders[B] .count:= 0;

C.setheaders[B].firstelement:= 0

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

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

end

else { В по крайней мере не меньше А }

{ код для этого случая такой же,

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

end; { MERGE }

function FIND ( x: 1..n; var С: MFSET );

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

begin

return(С.names[x] .setname)

end; { FIND }

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

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

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

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

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

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

 

80