Программная инженерия Нижний Новгород 017 Лабораторный

1.4. Условия и ограничения 
Сделаем следующие основные допущения: 
1. Условимся рассматривать в дальнейшем конечные (см. выше) множества, 
состоящие из элементов произвольного типа. 
2. Элементы множества проиндексированы (каждому элементу соответствует 
уникальный индекс). 
3. Множество индексов элементов составляет непрерывный диапазон целых 
значений. 
4. Будем считать размер множества конечным числом, не превышающим 2
31
. 
2. Метод решения 
2.1. Структуры данных 
Как известно, структура данных есть модель данных в виде математической 
структуры S = (M
1
, …, M
k
, p
1
,…,p
n
), где M
1
, …, M
k
– базисные множества, p
1
,…,p
n
– 
отношения между элементами базисных множеств. 
Поскольку построение математической структуры основано на понятии множества, само 
множество не может быть определено, как структура данных. 
В дальнейших рассуждениях мы будем опираться на следующее описание множества, 
вытекающее из сделанных выше допущений. 
Каждому множеству A = {a
1
, a
2
, …, a
n
} 

U = {u
1
, …, u
k
} поставим в соответствие 
характеристический вектор 

= (

1
, 

2
, …, 

k
}, где
a) k – мощность U; 
b) 

i 
= 





.
если
,
0
;
если
,
1
A
u
A
u
i
i
c) 
1
k
i
i
n




. 
Все операции над множествами могут быть заменены в таком случае на операции над 
характеристическими векторами. Таким образом, в дальнейшем в работе мы будем решать 
задачу хранения и обработки именно характеристических векторов. 
Важный вопрос хранения самих элементов множеств вида A, а также Универса U, в 
данной работе не рассматривается. Отметим только, что введение характеристического 
вектора для представления множества позволяет организовать хранение лишь Универса 
(например, в виде вектора элементов) и избежать многократного дублирования данных, 
содержащихся в конкретных множествах вида A. 
Поскольку каждый элемент характеристического вектора принимает значения из 
множества {0, 1}, наиболее эффективной (с точки зрения расхода памяти) является его 

---

 
21 
реализация через битовое поле – непрерывный участок памяти (количество бит в котором 
достаточно для представления Универса), где каждый бит соответствует одному элементу 
вектора 

. 
Реализацию битового поля целесообразно вынести в отдельный класс, скрывающий 
детали, не существенные для представления и работы с множествами (некоторые из 
возникающих нюансов будут рассмотрены далее).