Структуры данных и алгоритмы (1021739), страница 42
Текст из файла (страница 42)
СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВend;удаление w из множества сыновей узла node;if node имеет только одного сына thendeJetel:= trueif w — третий сын node thenif у — 2-й сын node, имеющий 3-х сыновей then3-й сын у делается 1-м сыном w;else begin { у имеет двух сыновей }сын w делается 3-м сыном у;удаление w из множества сыновей узла node;endendendend; { deletel }Мы оставляем для читателя детализацию кода функции deletel. В качестве ещеодного упражнения предлагаем написать процедуру DELETE(S, ж), которая проверяла бы, не является ли множество S пустым или состоящим из одного элемента, и если это не так, то вызывала бы функцию deletel(S, ж). Если deletel возвратит значение true, то процедура должна удалить корень (узел, на который указывает S) и сделать S указателем на единственного (в данной ситуации) сына корня.5.5.
Множества с операторами MERGE и FINDВ этом разделе мы рассмотрим ситуацию, когда есть совокупность объектов,каждый из которых является множеством. Основные действия, выполняемые надтакой совокупностью, заключаются в объединении множеств в определенном порядке, а также в проверке принадлежности определенного объекта конкретномумножеству. Эти задачи решаются с помощью операторов MERGE (Слить) и FIND(Найти).
Оператор MERGE(A, В, С) делает множество- С равным объединению множеств А и В, если эти множества не пересекаются (т.е. не имеют общих элементов); этот оператор не определен, если множества А и В пересекаются. ФункцияFIND(jc) возвращает множество, которому принадлежит элемент ж; в случае, когдаж принадлежит нескольким множествам или не принадлежит ни одному, значениеэтой функции не определено.Пример 5.6. Отношением эквивалентности является отношение со свойствамирефлексивности, симметричности и транзитивности.
Другими словами, если на множестве S определено отношение эквивалентности, обозначаемое символом "=", то длялюбых элементов а, Ь и с из множества S (не обязательно различных) справедливыследующие соотношения._1.2.а = а (свойство рефлексивности)._Если а = Ь, то Ь = а (свойство симметричности).3.Если a = bmb = c, to а = с (свойство транзитивности).Отношение равенства (обозначается знаком "=") — это пример отношения эквивалентности на любом множестве S. Для любых элементов а, Ь и с из множества Sимеем (1) а — а; (2) если а = Ъ, то Ь = а; (3) если а = Ь и Ь = с, то а = с. Далее мывстретимся с другими примерами отношения эквивалентности.В общем случае отношение эквивалентности позволяет разбить совокупность объектов на непересекающиеся группы, когда элементы а и Ь будут принадлежать однойгруппе тогда и только тогда, когда а =.
Ъ. Если применить отношение равенства(частный случай отношения эквивалентности), то получим группы, состоящие из одного элемента.•,5.5. МНОЖЕСТВА С ОПЕРАТОРАМИ MERGE И FIND167Более формально можно сказать так: если на множестве S определено отношениеэквивалентности, то в соответствии с этим отношением множество S можно разбитьна непересекающиеся подмножества Si, S2,..., которые называются классами эквивалентности, и объединение этих классов совпадает с S.
Таким образом, а = Ъ длявсех а и & из подмножества Sit но а не эквивалентно Ь, если они принадлежат разным подмножествам. Например, отношение сравнения по модулю л1 — это отношение эквивалентности на множестве целых чисел. Чтобы показать это, достаточно заметить, что а - а = 0 (рефлексивность), если а - Ъ = dn, то b - а = (-d)n(симметричность), если а - & = е ( г а и 6 - с = еп, то а - с = (d + e)n (транзитивность).В случае сравнения по модулю п существует га классов эквивалентности, каждое изкоторых является множеством целых чисел.
Первое множество состоит из целых чисел, которые при делении на п дают остаток 0, второе множество состоит из целыхчисел, которые при делении на га дают остаток 1, и т.д., га-е множество состоит изцелых чисел, которые дают остаток п — 1.Задачу эквивалентности можно сформулировать следующим образом. Естьмножество S и последовательность утверждений вида "о эквивалентно Ь". Надопо представленной последовательности таких утверждений определить, какомуклассу эквивалентности принадлежит предъявленный элемент. Например, естьмножество S — {1, 2, ..., 7} и последовательность утверждений1 = 2 5=6 3=4 1=4Необходимо построить классы.эквивалентности множества S.
Сначала полагаем,что все элементы этого множества представляют отдельные классы, затем, применяязаданную последовательность утверждений, объединяем "индивидуальные" классы.Вот последовательность этих объединений:1=2{1,2} {3} {4} {5} {6} {7}5=6{1,2} {3} {4} {5,6} {7}3^4{1,2} {3,4} {5,6} {7}1=4{1,2,3,4} {5,6} {7}Можно "решать" задачу эквивалентности начиная с любого утверждения заданнойпоследовательности утверждений. При "обработке" утверждения а = Ь сначала с помощью оператора FIND находятся классы эквивалентности для элементов а и ft, затем к этим классам применяется оператор MERGE.Задача эквивалентности часто встречается во многих областях компьютерных наук. Например, она возникает при обработке компилятором Fortran "эквивалентныхобъявлений", таких какEQUIVALENCE (A(1),B(1,2),C(3)), (A(2),D,E), (F.G)Другой пример представлен в главе 7, где решение задачи эквивалентности помогает найти остовное дерево минимальной стоимости.
ППростая реализация АТД MFSETНачнем с простейшего АТД, реализующего операторы MERGE и FIND. ЭтотАТД, назовем его MFSET (Множество с операторами MERGE и FIND), можно определить как множество, состоящее из подмножеств-колломек/гаов, со следующими операторами.1.2:3.MERGE(A, В) объединяет компоненты А и В, результат присваивается или А, или В.FINDC*) — функция, возвращающая имя компонента, которому принадлежит х.INITIAL(A, *) создает компонент с именем А, содержащим только элемент х.1Говорят, что а сравнимо с Ь по модулю п, если а и Ь имеют один и тот же остаток от деления на п, или, другими словами, если а — Ь кратно га.168ГЛАВА 5.
СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВДля корректной реализации АТД MFSET надо разделить исходные типы данныхили объявить, что MFSET состоит из данных двух разных типов — типа имен множеств и типа элементов этих множеств. Во многих приложениях можно использоватьцелые числа для имен множеств.
Если общее количество элементов всех компонентравно л, то можно использовать целые числа из интервала от 1 до п для идентификации элементов множеств. Если принять это предположение, то в таком случае существенно, что номерами элементов можно индексировать ячейки массива. Тип именкомпонентов не так важен, поскольку это тип ячеек массива, а не индексов. Но еслимы хотим, чтобы тип элементов множеств был отличным от числового, то необходимо применить отображение, например посредством хеш-функции, ставящее в соответствие элементам множеств уникальные целые числа из заданного интервала. Впоследнем случае надо знать только общее число элементов всех компонентов.После всего сказанного не должно вызывать возражений следующее объявление типов:,••.• •.
•consttype,л = { количество всех элементов };MFSET = array[1..л] of integer;или объявление более общего типаarray[интервал элементов] of (тип имен множеств)Предположим, что мы объявили тип MFSET как массив components (компоненты), предполагая, что components[x] содержит имя множества, которому принадлежит элемент х.
При этих предположениях операторы АТД MFSET реализуются легко, что видно из листинга 5.13 с кодом процедуры MERGE. Процедура ШГПАЦА. х)просто присваивает components[x\ значение А, а функция FIND(x) возвращает значение components[x].;. " - . • ' ' . :••.;-"?-•' :. ч ••:г:::'-.:":••' . • • • •.•_:; :•Листинг 5.13. Процедура MERGE•- -::-.':-; •.;• :•';:• . ':; •.
• '.procedure MERGE ( А, В: integer,- var С: MFSET ) ;varх: 1. . л;beginend;for x:= 1 to л doif C[x] = В thenC[x]:= Л{ MERGE }Время выполнения операторов при такой реализации MFSET легко проанализировать. Время выполнения процедуры MERGE имеет порядок О(га), а для INITIAL иFIND время выполнения фиксированно, т.е. не зависит от п.Быстрая реализация АТД MFSETПрименение алгоритма из листинга 5.13 для последовательного выполнения п - 1раз оператора MERGE займет время порядка О(п2)1. Один из способов ускорения выполнения оператора MERGE заключается в связывании всех элементов компонента вотдельные списки компонентов.
Тогда при слиянии компонента В в компонент Авместо просмотра всех элементов необходимо будет просмотреть только список элементов компонента В. Такое расположение элементов сократит среднее время слияния компонентов. Но нельзя исключить случая, когда каждое i-e слияние выполня1Для слияния п элементов в одно множество потребуется в самом худшем случае не болееп - 1 выполнений оператора MERGE.5.5. МНОЖЕСТВА С ОПЕРАТОРАМИ MERGE И FIND169ется в виде оператора MERGE(A, В), где компонент А состоит из одного элемента, аВ — из i элементов, и результат слияния получает имя компонента А. Выполнениетакого оператора требует O(i) шагов, а последовательность п - 1 таких операторовпотребует времени порядка J^ i = n(n -1)/2 .Чтобы избежать описанной ситуации, можно отслеживать размер каждого компонента и всегда сливать меньшее множество в большее1.
Тогда каждый раз элемент изменьшего множества переходит в множество, которое, по крайней мере, в два разабольше его исходного множества2. Поэтому, если первоначально было п компонентови каждый из них содержал по одному элементу, то любой элемент может перейти влюбой компонент не более чем за 1 + logn шагов. Таким образом, в новой версииоператора MERGE время его выполнения пропорционально количеству элементов вкомпоненте, чье имя изменяется, а общее число таких изменений не большеn(l -I- logn), поэтому время всех слияний имеет порядок О(п logn).Теперь рассмотрим структуру данных, необходимую для такой реализации.
Вопервых, необходимо отображение имен множеств в записи, состоящие из• поля count (счет), содержащего число элементов в множестве, и• поля firstelement (первый элемент), содержащего индекс Ячейки массива с первым элементом этого множества.Во-вторых, необходим еще один массив записей, индексированный элементами.Здесь записи имеют поля:• sctnamc (имя множества), содержащее имя множества;• nextelement (следующий элемент), значение которого указывает на следующийэлемент в списке данного множества.Будем использовать 0 в качестве маркера конца списка, т.е. значения NIL.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
