Структуры данных и алгоритмы (1021739), страница 27
Текст из файла (страница 27)
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВchanged:= false;{ далее 8 операторов реализуют формулу (4.2), но толькодля блок-схемы рис. 4.1}MAKENULL(DEFIN[l]);ASSIGN(DEFINl2] , DEFOUTl1]) ;ASSIGN(DEFIN[3] , DEFOUT[2]);ASSIGN(DEFIN[4], DEFOUTl3]);UNION(DEFOOT[4] , £>FFOOT[8] , DEFINES] ) ;UNION(DBFOOT[3], DEFOUT[5], DEFIN16]);ASSIGN(DEFIN[7] , DEFOUT[6]);ASSIGN(DEFINl8] , DEFOUTl6]) ;for i:= 1 to 8 dopropagate (GENli] , KILLli] , DEFINl i] , DEFOUTl i] );,,-, лuntilnot changedend.,V.,., ..
........Табл ица 4.1 . Значе*1ИЯ DEFIN[i] после каждой итерацииiПроход 11Проход 2. .,.,:..,,..,. . . :•',..: , •.,.',Проход 3Проход 4''00002U, 2, 3}3{4,5}{1,2,3}{1,4,5}40{4,5}{1,2,3}{1,4,5}{1,4,5}{1,2,3}{1,4,5}{1.4.5}5{6,9}{6,9}{4, 5, 6, 7, 8, 9}6{7,8}{4, 5, 6, 7, 8, 9}70{7,8}{4, 5, 6, 7, 8, 9}{1,4,5,6,7,8,9}{4, 5, 6, 7, 8, 9}80{7,8}{4,5,6,7,8,9}....'{1,4,5,6, 7,8, 9}{1,4,5,6,7,8,9}{1,4,5,6,7,8,9} '4.3.
Реализация множеств посредством двоичныхвекторовНаилучшая конкретная реализация абстрактного типа данных SET (Множество)выбирается исходя из набора выполняемых операторов и размера множества. Есливсе рассматриваемые множества будут подмножествами небольшого универсальногомножества целых чисел 1, ..., N для некоторого фиксированного N, тогда можноприменить реализацию АТД SET посредством двоичного (булева) вектора. В этойреализации множество представляется двоичным вектором, в котором i-й бит равен1 (или true), если i является элементом множества. Главное преимущество этойреализации состоит в том, что здесь операторы MEMBER, INSERT и DELETE можно выполнить за фиксированное время (независимо от размера множества) путемпрямойадресацииксоответствующемубиту.НооператорыUNION,INTERSECTION и DIFFERENCE выполняются за время, пропорциональное размерууниверсального множества.Если универсальное множество так мало, что двоичный вектор занимает не болееодного машинного слова, то операторы UNION, INTERSECTION и DIFFERENCEможно выполнить с помощью простых логических операций (конъюнкции и дизъюнкции), выполняемых над двоичными векторами.
В языке Pascal для представления небольших множеств можно использовать встроенный тип данных set. Максимальный размер таких множеств зависит от конкретного применяемого компилятора4.3. РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ ДВОИЧНЫХ ВЕКТОРОВ109и поэтому не формализуем. Однако при написании программ мы не хотим быть связаны ограничением максимального размера множеств по крайней мере до тех пор,пока наши множества можно трактовать как подмножества некоего универсальногомножества {1, ..., N). Поэтому в данном разделе будем придерживаться представления множества в виде булевого массива А, где A[i] = true тогда и только тогда, когдаi является элементом множества.
С помощью объявлений языка Pascal АТД SETможно определить следующим образом:constN = { подходящее числовое значение };typeSET = packed array[1..W] of boolean;Реализация оператора UNION приведена в листинге 4.2. Для реализации операторов INTERSECTION и DIFFERENCE надо в листинге 4.2 заменить логический оператор ог на операторы and и and not соответственно. В качестве простого упражнениячитатель может самостоятельно написать код для реализации других операторов, перечисленных в разделе 4.1 (за исключением операторов MERGE и FIND, которые неимеют практического смысла при данном представлении множеств).Листинг 4.2. Реализация оператора UNIONprocedure UNION (А, В: SET; var С: SET );vari: integer;beginfor i:= 1 to N doC[i]:= All] or B[i]endПредставление множеств в виде двоичных векторов можно применить не только тогда, когда универсальное множество состоит из последовательных целых чисел, но и вболее общей ситуации, когда универсальное множество конечно.
Для этого достаточноустановить взаимно однозначное соответствие между элементами этого множества и целыми числами 1, ..., N. Например, так, как это сделано в примере 4.1, где вер определения данных мы пронумеровали числами от 1 до 9. В общем случае для реализациитакого отображения используется АТД MAPPING (Отображение), описанный в главе 2.На практике обратное отображение из множества целых чисел в множество элементовуниверсального множества проще выполнить с помощью массива А, где A[i] будет элементом универсального множества, соответствующим числу i.4.4.
Реализация множеств посредством связанныхсписковОчевиден способ представления множеств посредством связанных списков, когдаэлементы списка являются элементами множества. В отличие от представлениямножеств посредством двоичных векторов, в данном представлении занимаемоемножеством пространство пропорционально размеру представляемого множества, ане размеру универсального множества. Кроме того, представление посредством связанных списков является более общим, поскольку здесь множества не обязаны бытьподмножествами некоторого конечного универсального множества.При реализации оператора INTERSECTION (Пересечение) в рамках представлениямножеств посредством связанных списков есть несколько альтернатив.
Если универсальное множество линейно упорядочено, то в этом случае множество можно представить в виде сортированного списка, т.е. предполагая, что все элементы множествасравнимы посредством отношения "<", можно ожидать, что эти элементы в списке110ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВбудут находиться в порядке elt е2, ..., еп, когда ег < ez < еа < ... < е„. Преимуществоотсортированного списка заключается в том, что для нахождения конкретного элемента в списке нет необходимости просматривать весь список.Элемент будет принадлежать пересечению списков L t и L2 тогда и только тогда,когда он содержится в обоих списках.
В случае несортированных списков мы должны сравнить каждый элемент списка L\ с каждым элементом списка Ь2, т.е. сделатьпорядка О(л2) операций при работе со списками длины п. Для сортированных списков операторы пересечения и некоторые другие выполняются сравнительно просто:если надо сравнить элемент е списка LI с элементами списка L2, то надо просматривать список L2 только до тех пор, пока не встретится элемент е или больший, чем е.В первом случае будет совпадение элементов, второй случай показывает, что элемента е нет в списке L 2 - Более интересна ситуация, когда мы знаем элемент d, которыйв списке LI непосредственно предшествует элементу е.
Тогда для поиска элемента,совпадающего с элементом е, в списке L2 можно сначала найти такой элемент /, чтоd <, f, и начать просмотр списка L2 с этого элемента. Используя этот прием, можнонайти совпадающие элементы в списках Ll и L2 за один проход этих списков, продвигаясь вперед по спискам в прямом порядке, начиная с наименьшего элемента.Код процедуры, реализующей оператор INTERSECTION, показан в листинге 4.3.Здесь множества представлены связанными списками ячеек, чей тип определяетсяследующим образом:typecelltype = recordelement: elementtype;next: TcelltypeendВ листинге 4.3 предполагается, что elementtype — это тип целых чисел, которыеможно упорядочить посредством обычного оператора сравнения <. Если elementtypeпредставлен другим типом данных, то надо написать функцию, которая будет определять, какой из двух заданных элементов предшествует другому элементу.Листинг 4.3.
Процедура INTERSECTION, использующая связанные списки(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)procedure INTERSECTION ( ahead, bhead: Tcelltype;var pc: Tcelltype ) ;{ Вычисление пересечения сортированных списков А и В сячейками заголовков ahead и bhead, результат —сортированный список, на чей заголовок указывает рс }varacurrent, bcurrent, ccurrent: Tcelltype;{ текущие ячейки списков А и В и последняя ячейкадополнительного списка С }beginnew(pc); { создание заголовка для списка С }acurrent:= aheadt .next;bcurrent:= bheadl.next;ccurrent:= pc;while (acurrent <> nil) and (bcurrent <> nil) do begin{ сравнение текущих элементов списков А и В }if acurrentT.element = bcurrentT.element then begin{ добавление элемента в пересечение }new(ccurrentT.next);ccurrent:= ccurrentT.next;ccurrentT.element:= acurrentT.element;acurrent:= acurrentT.next;4.4.
РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ СВЯЗАННЫХ СПИСКОВ111(11)bcurrent:= bcurrentT'. nextendelse { элементы неравны }if acurrentt.element < bcurrentT.element thenacurrent:= acurrentf.next;elsebcurrent:= bcurrentT.next(12)(13)(14)(15)endccurrentT.next:= nilend; { INTERSECTION }Связанные списки в листинге 4.3 в качестве заголовков имеют пустые ячейки,которые служат как указатели входа списков. Читатель при желании может написать эту программу в более общей абстрактной форме с использованием примитивовсписков. Но программа листинга 4.3 может быть более эффективной, чем абстрактная программа. Например, в листинге 4.3 используются указатели на отдельныеячейки вместо "позиционных" переменных, указывающих на предыдущую ячейку.Так можно сделать вследствие того, что элементы добавляются в список С, а спискиА и В только просматриваются без вставки или удаления в них элементов.Процедуру INTERSECTION листинга 4.3 можно легко приспособить для реализации операторов UNION и DIFFERENCE.
Для выполнения оператора UNION надо всеэлементы из списков А и В записать в список С. Поэтому, когда элементы не равны(строки 12-14 в листинге 4.3), наименьший из них заносится в список С, так же,как и в случае их равенства. Элементы заносятся в список С до тех пор, пока на исчерпаются оба списка, т.е. пока логическое выражение в строке 5 не примет значение false. В процедуре DIFFERENCE в случае равенства элементов они не заносятся всписок С. Если текущий элемент списка А меньше текущего элемента списка В, тоон (текущий элемент списка А) заносится в список С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
