Структура данных типа «множество»

Множество на физическом уровне — это массив битов, в котором каждый бит указывает, является ли элемент принадлежащим множеству или нет. Максимальное число элементов множества — 256, так что множество никогда не может занимать более 32 байтов.

Число байтов, занимаемых отдельным множеством, вычисляется как ByteSize = (Max div 8) – (Min div 8) + 1, где Min и Max — нижняя и верхняя граница базового типа этого множества.

Номер байта для конкретного элемента E вычисляется по формуле Byte Number = (E div 8) – (Min div 8), а номер бита внутри этого байта — по формуле BitNumber = E mod 8.

На логическом уровне множество можно описать так:

Type T_set = set of T; { T — базовый тип множества}

Значениями типа множество являются все подмножества базового типа. Мощность множественного типа T_set (кардинальное число) равна Car(T_set) = 2^Car(T). Число элементов базового типа ограничено и не должно превышать 256. Базовый тип является перечисляемым типом или поддиапазоном перечисляемого типа. Кроме того, объем памяти, занимаемый значением базового типа — один байт.

Допустимыми операциями для множества являются:

1. Пересечение (*).

2. Объединение (+).

3. Вычитание (–).

4. Операции отношения:

4.1. Равенство множеств (=).

4.2. Неравенство множеств (<>).

4.3. Левый операнд — подмножество правого (<=).

4.4. Правый операнд — подмножество левого (>=).

4.5. Принадлежность элемента множеству (in).

Структурированные типы данных в C