ния "=", отношение конгруэнтности (по модулю т) для целых чисел, отношение подобия между деревьями, которое определяется в разделе 2.3.1, и т. д.

Задача эквивалентное заключается в считывании нескольких пар эквивалентных элементов и определении с их помощью эквивалентности двух заданных элементов. Например, предположим, что множество S содержит элементы {1,2,3,4,5,6,7,8,9} и что даны пары

1 = 5, 6 = 8, 7=2, 9 = 8, 3 = 7, 4 = 2, 9 = 3. (11)

Тогда отсюда следует, например, что 2 = 6, так как 2 = 7 = 3 = 9 = 8 = 6. Но при этом нельзя установить, справедливо ли утверждение, что L = 6. Действительно, пары (И) делят множество S на два таких класса

{1,5} и {2,3,4,6,7,8,9}, (12)

что два элемента будут эквивалентны тогда и только тогда, когда они принадлежат одному классу. Нетрудно доказать, что любое отношение эквивалентности разбивает множество S на такие непересекающиеся классы эквивалентности {equivalence classes), что два элемента будут эквивалентны тогда и только тогда, когда они принадлежат одному и тому же классу.

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

{1} {2} {3} {4} {5} {6} {7} {8} {9}. (13)

Затем, если дано отношение 1 = 5, элементы {1,5} можно разместить вместе в одном классе. После обработки первых трех отношений 1 = о,6 = 8и7 = 2 вместо исходного набора классов (13) получим

{1,0} {2,7} {3} {4} {6,8} {9}. (14)

На основе отношения 9=8 разместим в одном классе элементы {6, 8,9} и т. д.

Теперь наша задача состоит в поиске удобного способа представления ситуаций наподобие (12)-(14) внутри ко.мпьютера для того, чтобы можно было эффективно выполнять операции, слияния классов и проверки принадлежности двух заданных элементов одно.м} классу. Для этого в приведенном ниже алгоритме используются ориентированные древовидные структуры. В нем предполагается, что элементы множества S являются узлами ориентированного леса. Причем два узла эквивалентны вследствие эквивалентности считанных ранее пар тогда и только тогда, когда они принадлежат одному дереву. Эту проверку можно довольно просто выполнить, так как два элемента принадлежат одному и тому же дереву тогда и только тогда, когда они являются наследниками одного корня. Более того, слияние двух ориентированных деревьев легко вьшолняется за счет простого присоединения одного дерева в качестве нового поддерева к корню другого дерева.

Алгоритм Е {Обработка отношений эквивалентности). Пусть S является множеством чисел {1,2,...,7?,} и пусть PARENT[1], PARENT[2], PARENT[n] являются целочисленными переменными. В качестве ввода в этом алгоритме используется множество отношений наподобие (И), а для представления множества ориентированных деревьев используется таблица PARENT, так что два элемента считаются

эквивалонтными вследствие заданных отношений эквивалентности тогда и только тогда, когда 01ш относятся к одному и тому же дереву. (Замечание. В более общем случае элементы мьюжества S могут быть представлены в виде символьных имен, а НС просто в виде набора чисел от 1 до гг. Тогда программа поиска, кото])ая более под])обно описывается в главе 6, нашла бы узлы, соответствующие эле.мептам множества S, а элемент таблицы PARENT соответствовал бы полю в этих узлах. Модн(1)икация данного алгоритма для такого более общего случая может быть выполнена достаточно просто.)

Е1. [Инидпа-лизация.] Установить PARENT [А;] -f- О для 1 < А; < гг. (Это значит, что все деревья в исходном состоянии содержат только корень, как в (13).)

Е2. [Ввод новой па])ы.] Получить следуюшую пару эквивалентных элементов "j = fc" из входного потока. Если входной поток исчерпан, прекратить выполнение алгоритма.

ЕЗ. [Поиск корней.] Если PARENT [j] > О, установить j <- PARENT [j] и повторить этот шаг. Если PARENT [fc] > О, установить fc -f- PARENT [fc] и повторить этот шаг. (Поело вьпюлпепия оне]>ации j н к переходят к корням двух деревьев, которые сло;уот сделать эквипалоитпыми. Отношение на входе j = к избыточно тогда и только тогда, когда j = fc.)

Е4. [Слияние деревьев.] Если j ф fc, установить PARENT [j] fc. Вернуться к шагу Е2. I

Читателю рскомондуется применить этот алгоритм гга отношению к входному гютоку (11). После обработки отпошспнй 1 = 5, 6 = 8, 7 = 2 и 9 = 8 получим соответствия

PARENT[fc]: 500008208 fc: 12 3450789 кото])ыс представляют такие деревья:

© © 0 О

(15)

© О

(16)

С этого момента обработка ост;и1ьных отношений (И) представляется особенно интересной (см. ynj). 9).

На п])актике ;?адача эквивалентности возникает довольно часто. В разделе 7.4.1 при изучешш связности ri)acl)oi? будут расс:люгрены некоторые существенные усовершенствования алгоритма Е. В более общей с})ормули])овке эта задача встречается при ()б])а.ботке компилятором "объявлений эквивалентности" в языках наподобие FORTR.MN, которая пол]юбно обсуждается в упр. 11.

Помимо перс"П1(лепиых, существует неско.лько других способов представления деревьев в па.мяги ко.мш.ютсра. Наполшнм три основных .метода представления линейных списков, кого])ыо ])ассматривались выше, в разделе 2.2: простейший одно-направлепный список с концевой связью Л, циклически связанные списки и дважды связанные списки. П])сдставление непрошитых бинарных деревьев, рассмотренных в разделе 2.3.1, соответствует простейшему представлению па основе как полей LLINK, так и полей RLINK. Восемь других представлений бинарных деревьев можно получить пезавнси.мо, используя любой из этих трех методов на основе полей LLINK

Рис. 27. Кольцевая структура.

и RLINK. Например, на рис. 27 показан результат циклического связывания, которое применяется в обоих направлениях. При использовании циклических связей в обоих направлениях так, как показано на этом рисунке, мы получим кольцевую структуру {ring structure). Они оказались достаточно гибкими для целого ряда приложений. Оптимальный выбор представления зависит, как обычно, от типов операций вставки, удаления и обхода, которые необходимы в алгоритмах обработки таких структур. Читателю, который внимательно изучил приведенные выше примеры из этой главы, будет нетрудно выбрать и применить на практике какой-либо из вариантов представления.

В заключение раздела приведем пример модифицированной дважды связанной циклической структуры, которая используется для рассмотренной выше задачи, а именно - для полиномиальной арифметики. Алгоритм 2.2.4А выполняет сложение одного полинома с другим при условии, что оба полинома представлены в виде циклических списков. А остальные алгоритмы того же раздела соответствуют другим операциям над полиномами. Полиномы в разделе 2.2.4 содержали не более трех переменных, в то время как при работе с большим количеством переменных удобнее использовать не линейный список, а древовидную структуру.

Полином либо представляет собой константу, либо имеет вид

0<j<n

где X - переменная, п > О, О = ео < ei < < е„, о, • • ,ffn -полиномы по другим переменным, символьные имена которых в алфавитном порядке располагаются до переменной х, а полиномы gi,. ,дп отличны от нуля. Это рекурсивное определение полиномов подходит для представления деревьев, как показано на рис. 28. Узлы имеют по шесть полей, которые в случае использования компьютера MIX можно разместить в трех словах:

(17)

Здесь LEFT, RIGHT, UP и DOWN - связи, EXP - целое число, которое указывает степень, а CV - либо константа (коэффициент), либо символьное имя переменной- Для корневого узла UP = А, ЕХР = О, LEFT = RIGHT = * (связан с самим собой).