Структуры данных и алгоритмы (1021739), страница 26
Текст из файла (страница 26)
Например, если А = {а, Ь, с] и В = (b, d}, то А и В ={а, Ь, с, d}, A n В = {Ь} и А \ В = {а, с}.1Для обозначения "множества с повторениями" иногда используется термин мультимножество. Мультимножеством будет набор элементов {1, 4, 1}. Мультимножество также не является списком и даже в большей степени, чем простое множество, поскольку для мультимножества можно писать {4, 1, 1} и {1, 1, 4}.104ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВОператоры АТД, основанные на множествахРассмотрим операторы, выполняемые над множествами, которые часто включаются в реализацию различных абстрактных типов данных. Некоторые из этих операторов имеют общепринятые (на сегодняшний день) названия и эффективные методыих реализации.
Следующий список содержит наиболее общие и часто используемыеоператоры множеств (т.е. выполняемые над множествами).1-3. ПервыетрипроцедурыUNION(A, В, С),INTERSECTION^, В, С)иDIFFERENCE(A, В, С)1 имеют "входными" аргументами множества Л и В, а вкачестве результата — "выходное" множество С, равное соответственно А и В,А п В и А \ В.4. Иногда мы будем использовать оператор, который называется слияние (merge),или объединение непересекающихся множеств.
Этот оператор (обозначаетсяMERGE) не отличается от оператора объединения двух множеств, но здесь предполагается, что множества-операнды не пересекаются (т.е. не имеют общих элементов). Процедура MERGE(A, В, С) присваивает множеству С значение А и В,но результат будет не определен, если А п В * 0, т.е.
в случае, когда множестваА и В имеют общие элементы.5. Функция MEMBER(.r, А) имеет аргументами множество А и объект х того же типа, что и элементы множества А, и возвращает булево значение true (истина), если х £ А, и значение false (ложь), если х i. A.6. Процедура MAKENULL(A) присваивает множеству А значение пустого множества.7. Процедура INSERT(x, А), где объект х имеет тот же тип данных, что и элементымножества А, делает х элементом множества А. Другими словами, новым значением множества А будет А и {х}. Отметим, что в случае, когда элемент х ужеприсутствует в множестве А, это множество не изменяется в результате выполнения данной процедуры.8.
Процедура DELETED, А) удаляет элемент х из множества А, т.е. заменяет множество А множеством А \ {х}. Если элемента х нет в множестве А, то это множество не изменяется.9. Процедура ASSIGN(A, В) присваивает множеству А в качестве значения множество В.10. Функция МШ(А) возвращает наименьший элемент множества А. Для применения этой функции необходимо, чтобы множество А было параметризировано иего элементы были линейно упорядочены. Например, MIN({2, 3, 1}) = 1 иМШ({'а', 'Ь', 'с'}) — 'а'.
Подобным образом определяется функция МАХ.11. Функция EQUAL(A, В) возвращает значение true тогда и только тогда, когдамножества А и В состоят из одних и тех же элементов.12. Функция FIND(jc) оперирует в среде, где есть набор непересекающихся множеств. Она возвращает имя (единственное) множества, в котором есть элемент х.1 '•••'* 1 ' '! , •-..•'.' •4.2. АТД с операторами множествМы начнем с определения АТД для математической модели "множество" С определенными тремя основными теоретико-множественными операторами объединения,пересечения и разности.
Сначала приведем пример такого АТД и покажем, как егоможно использовать, а затем обсудим некоторые простые реализации этого АТД.1Названия процедур переводятся как "Объединение", "Пересечение" и "Разность". —Прим. перев.4.2. АТД С ОПЕРАТОРАМИ МНОЖЕСТВ105Пример 4.1. Напишем программу, выполняющую простой "анализ потока данных" по блок-схемам представленных процедур. Программа будет использовать переменные абстрактного типа данных SET (Множество), для этого АТД операторыUNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL определеныв предыдущем разделе.В блок-схеме на рис. 4.1 блоки-прямоугольники помечены Ъ\, ..., Ва, а операторы определения данных (операторы объявления данных и операторы присваивания) пронумерованы от 1 до 9.
Эта блок-схема соответствует алгоритму Евклида(вычисление наибольшего общего делителя двух 'чисел), но в данном примере детали этого алгоритма нас не интересуют.GEN={1,2,3}KILL={4.5A7,8,9}GEN={4,5}KILL^.3,7,8}GEN=KILL=0GEN={6}KILL={1,9}GEN={7,8}KILL=(2,3,4,5}=(2,3,4,GEN=KILL=0GEN=KILL=0GEN={9}KILL={1,6}Рис. 4.1. Блок-схема алгоритма Евклида106ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВВ общем случае анализ потока данных относится к той части компилятора, которая проверяет блоковую структуру исходной программы (подобную рис.
4.1) и собирает информацию о выполнении операторов каждого прямоугольника блок-схемы.Блоки (прямоугольники) блок-схемы представляют совокупность операторов, черезкоторые последовательно "проходит" поток данных. Информация, полученная в результате анализа потока данных, помогает повысить качество генерируемого компилятором кода программы. Если, например, в процессе анализа потока данных обнаружено, что при каждом прохождении блока В переменная х принимает значение27, то можно подставить 27 для всех вхождений х в блоке В вместо выполнения оператора присваивания этой переменной.
Если доступ к константам осуществляетсябыстрее, чем к значениям переменных, то описанная замена приводит к более эффективному коду программы, полученному в процессе компиляции.В нашем примере мы хотим определить, где переменная последний раз принимала новое значение. Другими словами, мы хотим для каждого блока В, вычислитьмножество DEFIN[i] определений d таких, которые сделаны в блоках от Вг до Д, нов последующих блоках нет других определений для той же переменной, которая определялась в определении d.Чтобы проиллюстрировать необходимость такой информации, рассмотрим блоксхему на рис. 4.1.
Первый блок В\, являясь "холостым" блоком, содержит три определения, присваивающих переменным t, p и q "неопределенные" значения. Если, например, множество DEFIN[7] включает в себя определение 3, которое присваиваетпеременной q "неопределенное" значение, значит, программа содержит ошибку, поскольку будет предпринята печать этой переменной без присваивания ей"настоящего" значения. К счастью, в данной блок-схеме нетрудно проверить, что невозможно достигнуть блока В7, минуя операторы присвоения значений этой переменной, поэтому множество DEFIN[7] не будет содержать определение 3.При вычислении множества DEFIN[i] будем придерживаться нескольких правил.Сначала для каждого блока В, предварительно вычислим два множества GEN[i] иKILL[i]. GEN[f\ — это множество определений, сделанных в блоке Д.
Если в этомблоке есть несколько определений одной переменной, то только последнее из них заносится в множество GEN[i]. Другими словами, GEN[i] является множеством определений, "генерируемых" блоком Д.Множество KILL[i] содержит определения (из всех блоков, кроме Д) тех же переменных, которые определены в блоке В,.
Например, на рис. 4.1 GEN[4] — {6}, поскольку в блоке В4 содержится определение 6 (переменной t). В свою очередьKILL[4:] = {1, 9}, так как существуют определения 1 и 9 той же переменной t и которые не входят в блок В4.Кроме множеств DEFIN[i], для каждого блока Д также будем вычислять множества DEFOUT[i]. Так же, как DEFIN[i] является множеством определений, действиекоторых достигает блока Д, так и DEFOUT\i] — это множество определений, действие которых распространяется за блок В,. Существует простая формула, связывающая множества DEFIN[i] и DEFOUT[i]:DEFOUT[i] = (DEFIN[i] - KILL[i\) U GEN[i\(4.1)Таким образом, определение d распространяет свое действие за блок Д только в двухслучаях: если его действие начато до блока Д и не "убито" в этом блоке или если оно генерировано в блоке Д.
Вторая формула, связывающая множества DEFIN[i\ и DEFOUT[i],показывает, что DEFIN[i] можно вычислить как объединение тех множеств DEFOUT[p],для которых определяющие их блоки В„ предшествуют блоку Д.DEFIN[i]=UDEFOUT[p](4.2)Вр предшествует ДИз формулы (4.2) следует очевидный вывод, что определения данных регистрируются в блоке В, тогда и только тогда, когда их действие начинается в одном из предшествующих блоков. В особых случаях, когда Д не имеет предшественников (как блок Btна рис. 4.1), множество DEFIN[i] считается равным пустому множеству.4.2. АТД С ОПЕРАТОРАМИ МНОЖЕСТВ107Хотя в этом примере введено много новых понятий, мы не будем обобщать этотматериал для написания общих алгоритмов вычисления областей действия определений в произвольных блок-схемах.
Вместо этого мы напишем часть программы вычисления множеств DEFIN[i] и DEFOUT[i] 0 = 1 , ..., 8) для блок-схемы рис. 4.1,предполагая, что множества GEN[i\ и KILL[i] определены заранее. Отметим, чтопредлагаемый фрагмент программы предполагает существование АТД SET(Множество) с операторами UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGNи MAKENULL, позднее мы покажем, как реализовать этот АТД.В создаваемом программном фрагменте (листинг 4.1) процедура propagate(GEN,KILL, DEFIN, DEFOUT) использует формулу (4.1) для вычисления множестваDEFOUT указанного блока. Если программа свободна от циклов и повторяющихся структур, то в этом случае множества DEFOUT можно вычислить непосредственно. При наличии в программе циклов или повторяющихся структур для вычисления DEFOUT применяются итерационные процедуры. Сначала для всех iположим DEFIN[i] = 0 и DEFOUT[i] = GEN[i], затем последовательно применимформулы (4.1) и (4.2) несколько раз, пока не "стабилизируются" (не перестанутизменяться) множества DEFIN и DEFOUT.
Поскольку каждое новое значениемножеств DEFIN[i\ и DEFOUT[i] содержит свои предыдущие значения, а количество всех определений в программе ограничено, то процесс должен сходиться крешению уравнений (4.1) и (4.2).Последовательные значения множеств DEFINli] после каждой итерации циклапоказаны в табл. 4.1. Заметим, что операторы 1, 2 и 3 присваивания переменным"неопределенных" значений не распространяются на блоки, где эти переменные используются. Отметим также, что в листинге 4.2 сначала выполняются вычисленияпо формуле (4.2), а затем по формуле (4.1); в общем случае это обеспечивает сходимость процесса вычисления DEFIN[i\ всего за несколько итераций.
ПЛистинг 4.1. Программа вычисления областей действий операторов определенияпеременныхvarGEN, KILL, DEFIN, DEFOUT: array[1..8] of SET;{ Предполагается, что GEN и KILL вычисляютсявне этой программы }i: integer;changed: boolean;procedure propagate( G, K, I: SET; var O: SET ) ;.{- Вычисления по формуле (4.1), переменная changed принимаетзначение true, если есть изменения в DEFOUT }varTEMP: SET;.beginDIFFERENCE(I, K, TEMP) ;UNION ( TEMP, G, TEMP) ;if not EQUAL (TEMP, O) do beginASSIGN(O, TEMP);changed:= trueendend; { propagate }beginfor i:= • 1 to 8 doASSIGN(DEFOUT[i] , GEN[i]);repeat108ГЛАВА 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
