yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.3. Реализация множеств посредством двоичных векторов

Алгоритмы и структуры данных

4.3. Реализация множеств посредством двоичных векторов

Наилучшая конкретная реализация абстрактного типа данных SET (Множество) выбирается исходя из набора выполняемых операторов и размера множества. Если все рассматриваемые множества будут подмножествами небольшого универсального множества целых чисел 1, ..., N для некоторого фиксированного N, тогда можно применить реализацию АТД SET посредством двоичного (булева) вектора. В этой  реализации множество представляется двоичным вектором, в котором i-й бит равен 1 (или true), если і является элементом множества. Главное преимущество этой реализации состоит в том, что здесь операторы MEMBER, INSERT и DELETE можно выполнить за фиксированное время  (независимо от размера множества) путем прямой адресации к соответствующему биту. Но операторы UNION, INTERSECTION и DIFFERENCE выполняются за время, пропорциональное размеру универсального множества.

Если универсальное множество так мало, что двоичный вектор занимает не более одного машинного слова, то операторы UNION, INTERSECTION и DIFFERENCE можно выполнить с помощью простых логических операций (конъюнкции и дизъюнкции), выполняемых над двоичными векторами. В языке Pascal для представления небольших множеств можно использовать встроенный тип данных set. Максимальный размер таких множеств зависит от конкретного применяемого компилятора и поэтому не формализуем. Однако при написании программ мы не хотим быть связаны ограничением максимального размера множеств по крайней мере до тех пор, пока наши множества можно трактовать как подмножества некоего универсального множества {1, ..., N]. Поэтому в данном разделе будем придерживаться представления множества в виде булевого массива А, где A[i] = true тогда и только тогда, когда і является элементом множества. С помощью объявлений языка Pascal АТД SET можно определить следующим образом:

const

N =  {  подходящее числовое значение   } ;

type

SET = packed array [1..W]   of boolean;

Реализация оператора UNION приведена в листинге 4.2. Для реализации операторов INTERSECTION и DIFFERENCE надо в листинге 4.2 заменить логический оператор or на операторы and и and not соответственно. В качестве простого упражнения читатель может самостоятельно написать код для реализации других операторов, перечисленных в разделе 4.1 (за исключением операторов MERGE и FIND, которые не имеют практического смысла при данном представлении множеств).

 

 

procedure UNION   (A,   B:   SET;   var  C:   SET   ) ;

var

І :   integer ;

begin

for  i:=  1  to N do

C[i]:= A[i]   or В[i]

end

Представление множеств в виде двоичных векторов можно применить не только тогда, когда универсальное множество состоит из последовательных целых чисел, но и в более общей ситуации, когда универсальное множество конечно. Для этого достаточно установить взаимно однозначное соответствие между элементами этого множества и целыми числами 1, ..., N. Например, так, как это сделано в примере 4.1, где все определения данных мы пронумеровали числами от 1 до 9. В общем случае для реализации такого отображения используется АТД MAPPING (Отображение), описанный в главе 2. На практике обратное отображение из множества целых чисел в множество элементов универсального множества проще выполнить с помощью массива А, где A[і] будет элементом универсального множества, соответствующим числу і.

4.4. Реализация множеств посредством связанных списков

Очевиден способ представления множеств посредством связанных списков, когда элементы списка являются элементами множества. В отличие от представления множеств посредством двоичных векторов, в данном представлении занимаемое множеством пространство пропорционально размеру представляемого множества, а не размеру универсального множества. Кроме того, представление посредством связанных списков является более общим, поскольку здесь множества не обязаны быть подмножествами некоторого конечного универсального множества.

При реализации оператора INTERSECTION (Пересечение) в рамках представления множеств посредством связанных списков есть несколько альтернатив. Если универсальное множество линейно упорядочено, то в этом случае множество можно представить в виде сортированного списка, т.е. предполагая, что все элементы множества сравнимы посредством отношения "<", можно ожидать, что эти элементы в списке будут находиться в порядке е1, е2, ..., еп, когда е1 < е2 < e3 < … < еп. Преимущество отсортированного списка заключается в том, что для нахождения конкретного элемента в списке нет необходимости просматривать весь список.

Элемент будет принадлежать пересечению списков l1 и L2 тогда и только тогда, когда он содержится в обоих списках. В случае несортированных списков мы должны сравнить каждый элемент списка l1 с каждым элементом списка L2, т.е. сделать порядка О(n2) операций при работе со списками длины п. Для сортированных списков операторы пересечения и некоторые другие выполняются сравнительно просто: если надо сравнить элемент е списка L1 с элементами списка L2, то надо просматривать список l2 только до тех пор, пока не встретится элемент е или больший, чем е. В первом случае будет совпадение элементов, второй случай показывает, что элемента е нет в списке L2. Более интересна ситуация, когда мы знаем элемент d, который в списке l1 непосредственно предшествует элементу е. Тогда для поиска элемента, совпадающего с элементом е, в списке L2 можно сначала найти такой элемент f, что d≤f, и начать просмотр списка L2 с этого элемента. Используя этот прием, можно найти совпадающие элементы в списках l1 и L2 за один проход этих списков, продвигаясь вперед по спискам в прямом порядке, начиная с наименьшего элемента. Код процедуры, реализующей оператор INTERSECTION, показан в листинге 4.3. Здесь множества представлены связанными списками ячеек, чей тип определяется следующим образом:

type

се11type = record

element:   elementtype;

next:   ↑celltype

end

В листинге 4.3 предполагается, что elementtype — это тип целых чисел, которые можно упорядочить посредством обычного оператора сравнения <. Если elementtype представлен другим типом данных, то надо написать функцию, которая будет определять, какой из двух заданных элементов предшествует другому элементу.

 

 

25