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

Операторы АТД, основанные на множествах

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

1-3. Первые три процедуры UNION(A, В, С), INTERSECTION(A, В, С) и DIFFERENCE(A, В, С) имеют "входными" аргументами множества Л и В, а в качестве результата - "выходное" множество С, равное соответственно А и В, А г, В аА \ В.

4. Иногда мы будем использовать оператор, который называется слияние (merge), или объединение непересекающихся множеств. Этот оператор (обозначается MERGE) не отличается от оператора объединения двух множеств, но здесь предполагается, что множества-операнды не пересекаются (т.е. не имеют общих элементов). Процедура MERGE(A, В, С) присваивает множеству С значение А и В, но результат будет не определен, если А Ъ Ф Q, т.е. в случае, когда множества А и В имеют общие элементы.

5. Функция MEMBER(ar, имеет аргументами множество и объект х того же типа, что и элементы множества, и возвращает булево значение true (истина), если х £ , и значение false (ложь), если х i А.

6. Процедура MAKENULL(A) присваивает множеству значение пустого множества.

7. Процедура INSERT(ar, где объект х имеет тот же тип данных, что и элементы множества А, делает х элементом множества А. Другими словами, новым значением множества А будет А и {х}. Отметим, что в случае, когда элемент х уже присутствует в множестве А, это множество не изменяется в результате выполнения данной процедуры.

8. Процедура DELETE(ar, А) удаляет элемент х из множества А, т.е. заменяет множество А множеством А \ {х). Если элемента х нет в множестве А, то это множество не изменяется.

9. Процедура ASSIGN(A, В) присваивает множеству А в качестве значения множество В.

10. Функция MIN(A) возвращает наименьший элемент множества А. Для применения этой функции необходимо, чтобы множество А было параметризировано и его элементы были линейно упорядочены. Например, MIN({2, 3, 1}) = 1 и МШ({о, Ъ,с))- о. Подобным образом определяется функция МАХ.

11. Функция EQUAL(A, В) возвращает значение true тогда и только тогда, когда множества А и В состоят из одних и тех же элементов.

12. Функция FIND(ar) оперирует в среде, где есть набор непересекающихся множеств. Она возвращает имя (единственное) множества, в котором есть элемент х.

4.2. АТД с операторами множеств

Мы начнем с определения АТД для математической модели "множество" С определенными тремя основными теоретико-множественными операторами объединения, пересечения и разности. Сначала приведем пример такого АТД и покажем, как его можно использовать, а затем обсудим некоторые простые реализации этого АТД.

Названия процедур переводятся как "Объединение", "Пересечение" и "Разность". - Прим. перев.



Пример 4.1. Напишем программу, выполняюшую простой "анализ потока данных" по блок-схемам представленных процедур. Программа будет использовать переменные абстрактного типа данных SET (Множество), для этого АТД операторы UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL определены в предыдушем разделе.

В блок-схеме на рис. 4.1 блоки-прямоугольники помечены By, Bg, а операторы определения данных (операторы объявления данных и операторы присваивания) пронумерованы от 1 до 9. Эта блок-схема соответствует алгоритму Евклида (вычисление наибольшего обшего делителя двух "чисел), но в данном примере детали этого алгоритма нас не интересуют.


7:р 8:q

GEN=(1,2,3} KILL=(4,5,6,7,8,9}

GEN={4,5i KILL={2,3,7.8}

GEN=KILL=0

GEN= KILL=/

1.9}

GEN=(7,8} KILL=(2,3,4,5}


GEN=KILL=0

GEN=KILL=0

GEN= KILL=

9} 1.6}

Рис. 4.1. Блок-схема алгоритма Евклида



в общем случае анализ потока данных относится к той части компилятора, которая проверяет блоковую структуру исходной программы (подобную рис. 4.1) и собирает информацию о выполнении операторов каждого прямоугольника блок-схемы. Блоки (прямоугольники) блок-схемы представляют совокупность операторов, через которые последовательно "проходит" поток данных. Информация, полученная в результате анализа потока данных, помогает повысить качество генерируемого компилятором кода программы. Если, например, в процессе анализа потока данных обнаружено, что при каждом прохождении блока в переменная х принимает значение 27, то можно подставить 27 для всех вхождений х в блоке в вместо выполнения оператора присваивания этой переменной. Если доступ к константам осуществляется быстрее, чем к значениям переменных, то описанная замена приводит к более эффективному коду программы, полученному в процессе компиляции.

В нащем примере мы хотим определить, где переменная последний раз принимала новое значение. Другими словами, мы хотим для каждого блока В, вычислить множество DEFlN[i] определений d таких, которые сделаны в блоках от до В,, но в последующих блоках нет других определений для той же переменной, которая определялась в определении d.

Чтобы проиллюстрировать необходимость такой информации, рассмотрим блок-схему на рис. 4.1. Первый блок Bi, являясь "холостым" блоком, содержит три определения, присваивающих переменным t, р и q "неопределенные" значения. Если, например, множество DEF1N[7] включает в себя определение 3, которое присваивает переменной q "неопределенное" значение, значит, программа содержит ошибку, поскольку будет предпринята печать этой переменной без присваивания ей "настоящего" значения. К счастью, в данной блок-схеме нетрудно проверить, что невозможно достигнуть блока В, минуя операторы присвоения значений этой переменной, поэтому множество DEFlN[7yie будет содержать определение 3.

При вычислении множества DEFIN[ipyji.eM придерживаться нескольких правил. Сначала для каждого блока В, предварительно вычислим два множества GENfiJ и KILL[i\. GEN[i\- это множество определений, сделанных в блоке Д. Если в этом блоке есть несколько определений одной переменной, то только последнее из них заносится в множество GENfiJ. Другими словами, GENfiJ является множеством определений, "генерируемых" блоком Д.

Множество if7LL[i]содержит определения (из всех блоков, кроме Д) тех же переменных, которые определены в блоке В,. Например, на рис. 4.1 GEN[4]- {6), поскольку в блоке Bi содержится определение 6 (переменной t). В свою очередь KILL[4] {1, 9}, так как существуют определения 1 и 9 той же переменной t и которые не входят в блок В.

Кроме множеств ВЕР1Щ1],аля каждого блока Д также будем вычислять множества DEFOUT[i]. Так же, как i5£F7ЛГ[i]являeтcя множеством определений, действие которых достигает блока Д, так и DEFOUT[i]- это множество определений, действие которых распространяется за блок В,. Существует простая формула, связывающая множества DEFlNJiJ и DEFOUT[i]:

DEFOUT[i]= (DEFINJiJ - KILL[i])U GEN[i\ (4.1)

Таким образом, определение d распространяет свое действие за блок В, только в двух случаях: если его действие начато до блока Д и не "убито" в этом блоке или если оно генерировано в блоке В,. Вторая формула, связывающая множества DEFIN[i]n DEFOVT[i], показывает, что ВЕР1Щ1\можно вычислить как объединение тех множеств DEFOUT[p], для которых определяющие их блоки В, предшествуют блоку В,.

DEFIN[i]= \J DEFOUT[p] (4.2)

Bp предшествует Д

Из формулы (4.2) следует очевидный вывод, что определения данных регистрируются в блоке В, тогда и только тогда, когда их действие начинается в одном из предшествующих блоков. В особых случаях, когда Д не имеет предшественников (как блок Bi на рис. 4.1), множество D£FJV[]:читaeтcя равным пустому множеству.





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.0022