Главная Промышленная автоматика. Операторы АТД, основанные на множествах Рассмотрим операторы, выполняемые над множествами, которые часто включаются в реализацию различных абстрактных типов данных. Некоторые из этих операторов имеют общепринятые (на сегоднящний день) названия и эффективные методы их реализации. Следующий список содержит наиболее общие и часто используемые операторы множеств (т.е. выполняемые над множествами). 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. Эта блок-схема соответствует алгоритму Евклида (вычисление наибольшего обшего делителя двух "чисел), но в данном примере детали этого алгоритма нас не интересуют.
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 |