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[і] будет элементом универсального множества, соответствующим числу і.

 

45