Структуры данных и алгоритмы (1021739), страница 43
Текст из файла (страница 43)
Вязыках программирования, подходящих для таких структур, можно было бы использовать указатели на последний массив, но язык Pascal не разрешает указателейвнутрь массивов.В специальном случае, когда имена множеств и элементы являются целыми числами из интервала от 1 до п, можно использовать массив для реализации отображения, описанного выше.
В таком случае возможно следующее объявление:typenametype = 1. .л;elementtype = 1..л;MFSET =' recordsetheaders: array[l..n] of record{ заголовки списков множеств }count: 0 . . л ;firstelement: Q..n;end;names: array[1..л] of record{ массив имен множеств }setname: nametype;nextelement: O..nendend;1Отметим здесь полезность и важность присваивания результата слияния наименьшемумножеству, хотя в более простых реализациях результат слияния обычно присваивается первому аргументу оператора MERGE.Здесь "намекается" на то, что если последовательность применений оператора MERGE представить в виде дерева, то это дерево по своей структуре будет приближаться к полному дереву.Отсюда вытекает утверждение следующего предложения о "1 + logn шагах".
— Прим. ред.170ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВПроцедуры INITIAL, MERGE и FIND представлены в листинге 5.14. На рис. 5.10показан пример описанной структуры данных, состоящей из множеств 1 = {1, 3, 4},2 - {2} и 5 = {5, 6}.> :"•:. - : :' ' : " . . - . • ' . • . . . . - '",..-i.'••.::-'<,...-:•• .--•-.• • •• : , .:...:..,-,;,,:.Листинг 5.14.
Операторы АТД MFSETprocedure INITIAL ( A: nametype; x: elementtype; var С: MFSET );{ инициализирует множество с именем А, содержащее элемент х }beginC.names[x].setname:= A;С.names[x].nextelement:= 0;{ нулевой указатель на конец списка элементов А }C.setheaders[A].count:= 1;С.setheaders[A].firstelement: = хend; { INITIAL }.procedure MERGE ( A, B: nametype; var C: MFSET );{ Слияние множеств А и В. Результат присваиваетсяменьшему множеству }vari: О..п; {используется для нахождения конца меньшего списка}beginif С.setheaders[A].count > С.setheaders[В].count then begin{ А большее множество, поэтому сливается В в А }{ находится конец В, изменяется имя на А }i:= С.setheaders[В].firstelement;while C.names[i].nextelement <> 0 do beginC.names[i].setname:- A;i: = C:names[i].nextelementend;{ список А добавляется в конец списка В,результату слияния присваивается имя А }{ теперь i — индекс последнего элемента В }С.names[i].setname:= А;С.names[i].nextelement:» C.setheaders[A].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{ последние два шага необязательны, т.к.множества В больше не существует }endelse { В по крайней мере не меньше А }{ код для этого случая такой же,как и выше, с заменой местами А и В }end; { MERGE }function FIND ( x: l..n; var С: MFSET );{ возвращает имя множества, которому принадлежит элемент х }beginreturn(С.names[x].setname)end; { FIND }<•' ' ••'••5.5.
МНОЖЕСТВА С ОПЕРАТОРАМИ MERGE И FIND•'171count firstelementsetheaderssetname nextelementnamesРис. 5.10. Пример структуры данных MFSETРеализация АТД MFSET посредством деревьевДругой, полностью отличный о ранее рассмотренных, подход к реализации АТДMFSET применяет деревья с указателями на родителей. Мы опишем этот подход неформально. Основная идея здесь заключается в том, что узлы деревьев соответствуютэлементам множеств и есть реализация, посредством массивов или какая-либо другая, отображения множества элементов в эти узлы.
Каждый узел, за исключениемкорней деревьев, имеет указатель на своего родителя. Корни содержат как имя компонента-множества, так и элемент этого компонента. Отображение из множестваимен к корням деревьев позволяет получить доступ к любому компоненту.На рис. 5.11 показаны множества А = {1, 2, 3, 4}, В = {5, 6} и С = {7}, представленные в описанном виде. На этом рисунке прямоугольники являются частью корней, а не отдельными узлами.имя = Аимя = Вимя = СРис. 5.11.
Представление АТД MFSET набором деревьевЧтобы определить имя компонента, которому принадлежит элемент х, мы сначала с помощью отображения (т.е. массива, который не показан на рис. 5.11) получаемуказатель на узел, соответствующий элементу х. Далее следуем из этого узла к корню дерева и там читаем имя множества.Операция слияния делает корень одного дерева сыном корня другого. Например,при слиянии множеств А и В (см.
рис. 5.11), когда результат слияния получает имяА, узел 5 становится сыном узла 1. Результат слияния показан на рис. 5.12. Однаконеупорядоченные слияния могут привести к результату в виде дерева из п узлов, которое будет простой цепью узлов. В этом случае выполнение оператора FIND для любого узла такого дерева потребует времени порядка О(пг). В этой связи заметим, что172ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВхотя слияние может быть выполнено за О(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потребуется время, не превышающее О(п logn). Конечно, на выполнение первых операторов FIND может потребоваться время порядка О(п) на один оператор, если деревья состоят из одной цепочки узлов.
Но сжатие путей может очень быстро изменить5.5. МНОЖЕСТВА С ОПЕРАТОРАМИ MERGE И FIND173дерево, поэтому порядок, в котором применяется оператор FIND к элементам любогодерева при выполнении подряд л операторов FIND, несуществен. Но отметим, чтосуществуют последовательности из операторов MERGE и FIND, которые требуютвремени порядка П(п logn).бРис. 5.13. Пример сжатия путиАлгоритм, использующий как сжатие путей, так и слияние меньших множеств вбольшие, — асимптотически наиболее эффективный метод (из известных) реализации АТД MFSET. На практике л выполнений оператора поиска требует времени, непревышающего О(п сс(л)), где а(л) — функция, которая при возрастании л растетзначительно медленнее, чем logn.
Мы определим функцию о(л) ниже, но анализ, который приводит к такой оценке, выходит за рамки этой книги.Функция а(п)Функция а(л) тесно связана с очень быстро растущей функцией А(х, у), известнойкак функция Аккермана. Эта функция рекуррентно определяется следующими соотношениями:А(0, у) = 1 для любого у > О,А(1, 0) = 2,А(х, О) = х + 2 для любого х > 2,А(х, у) = А(А(х - 1, у), у - 1) для всех х, у > 1.Фиксированное значение у определяет функцию одной переменной. Например,третье вышеприведенное соотношение для у = О определяет функцию "прибавить 2".Для у = 1 и х > 1 имеем А(х, 1) = А(А(х - 1, 1), 0) = А(х - 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
