3.3. Представление множеств

Как было отмечено выше, выбор структуры данных, т. е. способа организации данных в памяти машины, определяется теми операциями, которые будут проводиться над данными.

Рассмотрим основные операции над множествами:

1. Принадлежать (a, S): Если aS, то выдаётся сообщение "да".

2. Вставить (a, S): S  S{a}.

3. Удалить (a, S): S  S\{a}.

4. Найти (a). Сообщается имя того множества, которому в данный момент принадлежит а (если а принадлежит более чем одному множеству, то операция не определена).

5. Объединить (S₁, S₂, S₃): S₃=S₁S₂.

6. Пересечь (S₁, S₂, S₃): S₃=S₁S₂.

7. Сцепить (S₁, S₂, S₃): S₃=S₁S₂.

8. Расцепить (a, S). Предполагается, что множество S упорядочено отношением . Операция разбиваетS на два множества: S₁={bba и bS}; S₂={bb>a и bS}.

9. MIN (S). Операция выдаёт наименьший (относительно ) элемент множестваS.

10. MAX (S). Операция выдаёт наибольший (относительно ) элемент множестваS.

Множество в памяти ЭВМ может быть представлено тремя способами: списком, характеристическим вектором и одномерным массивом.

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

Аналогично операция АВ требует времени, пропорционального сумме размеров множеств, поскольку надо выделить элементы, входящие в оба множества, и вычеркнуть каждый экземпляр каждого такого элемента. Если же А и В не пересекаются, можно найти АВ за время, не зависящее от размера А и В. Для этого достаточно сделать лишь конкатенацию списков, представляющих А и В. Задача объединения двух непересекающихся множеств усложняется, если необходимо быстро определить, входит ли данный элемент в данное множество.

Рассмотрим представление множества в виде двоичного (битового) вектора. Пусть U - универсальное множество (рассматриваемые множества являются его подмножествами), состоящее из n элементов. Линейно упорядочим его. Подмножество SU представляется в виде вектора V_s из n битов, такого, что i-й разряд в V_s равен 1 тогда и только тогда, когда i-й элемент множества U принадлежит S. Будем называть V_s характеристическим вектором для S.

Представление в виде двоичного вектора удобно тем, что можно определить принадлежность i-го элемента множества U данному множеству за время, не зависящее от размера данного множества. Более того, основные операции над множествами, такие, как объединение и пересечение, можно осуществлять как операции над двоичными векторами.

Полезность характеристических векторов вытекает из их компактности, существования простого фиксированного соотношения между i и S_i (адресом ячейки и значением i-го разряда вектора) и возможности при таком представлении очень легко добавлять и исключать элементы.

Например, характеристический вектор (ХВ) начального сегмента последовательности простых чисел имеет вид

S_i 1 2 3 4 5 6 7 8 9 10

ХВ для простых чисел 0 1 1 0 1 0 1 0 0 0

Главное неудобство ХВ состоит в том, что они неэкономичны. Исключение составляют "плотные" (в смысле малого числа нулей) подпоследовательности последовательности S₁, S₂, S₃,... . Кроме того, их трудно использовать, если не существует простого соотношения между i и S_i. Если такое соотношение сложное, то использование ХВ может быть очень неэкономичным в смысле времени обработки. Если последовательности недостаточно плотные, то значительным может оказаться объем памяти.

Если операции над двоичными векторами нельзя считать пер-вичными (т. е. выполняемыми за единицу времени), то можно с таким же успехом вместо характеристического вектора определить массив А, для которого А[i]=1 тогда и только тогда, когда i-й элемент множества U принадлежит A. При таком представлении все ещё легко выяснить, принадлежит ли данный элемент данному множеству.

Недостаток этого представления в том, что объединение и пересечение занимает время, пропорциональное |U|, а не размерам рассматриваемых множеств. Подобно этому память, требуемая для хранения множества A, пропорциональна |U|, a не |A|.