Множества.

16.1. Множества.

Тип данных множество позволяет программисту объявлять и использовать переменные, которые являются множествами, элементы которых хранятся в небольших, ограниченных наборах данных. Полный набор операций над множествами не поддерживается.

Тип данных множество определяется следующим образом:

TYPE

SetType = SET OF ComponentType;

где ComponentType является порядковым типом. Множества Паскаля ограничены по количеству хранимых элементов, максимальный размер такого набора данных не является частью спецификации Паскаля и зависит от реализации Паскаль-машины. Обычно это несколько сотен. Таким образом недопустимо следующее объявление.

TYPE

IntSet = SET OF INTEGER;

но допустимо

CONST

Max = 20;

TYPE

IntSet = SET OF 0 .. Max;

Если Max выбрано достаточно небольшим, чтобы быть в установленных пределах. Объявление не обеспечивают начальных значений переменной множества, таким образом значение Sieve после

VAR

Sieve = SET OF 0 .. Max;

неопределено.

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

Возможные значения множества являются членами множества мощности (powerset), множества всех подмножеств набора значений использованного для определения типа. Например множество мощности для типа

TYPE

SmallIntSet = SET OF 1 .. 3;

будет

{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

т.е. любые из этих множеств могут являться значениями типа SmallIntSet.

Константа множества с тремя элементами может быть записана как [1, 2, 3] или [ 1.. 3]

Любое из следующих присваиваний инициализирует Sieve значением {2, 3, ..., 19, 20}:

Sieve := [2 .. 20];

Sieve := [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];

Sieve := [2 .. 9, 10, 11 .. 15, 16, 17, 18 .. 20];

Операциями над значениями типа множеств являются

+ (объединение множеств),

– (разность множеств),

* (пересечение множеств)

= (эквивалентность),

<> (неэквивалентность),

<= (нестрогое подмножество),

>= (нестрогое надмножество),

IN (членство в множестве).

Операция	Операнды -> Результат
+ – *	SET X SET -> SET
= <> <= >=	SET X SET -> BOOLEAN
IN	ComponentType X SET -> BOOLEAN
[ ]	ComponentType X ComponentType -> SET

Операции объединения, разности и пересечения множеств определены только для пар множеств, но не для компонентов множеств. Таким образом, если Sieve имеет целые значения, недопустимо писать:

Sieve + 2

Вместо этого элемент может быть оформлен как значение типа 1-множество:

Sieve + [2]

Примеры выражений и их значения

Выражение	Значение
[3, 5] <= [3 .. 5]	TRUE
[3 .. 5] <= [3 .. 6]	TRUE
[3 .. 5] >= [3 .. 5]	TRUE
[3 .. 5] >= [3 .. 6]	FALSE

Бинарный инфиксный оператор IN проверяет членство в множестве:

Выражение	Значение
4 IN [3 .. 5]	TRUE
4 IN []	FALSE
4 IN [3, 5]	FALSE

Квадратные скобки используются не только для обозначения констант множеств, но и для формирования множеств из выражений, чьи значения являются элементами множеств. Например, если X имеет тип INTEGER и значение 3:

Выражение	Значение
[2, X]	{2, 3}
[3 .. X[]	{3}
[X .. X+2, SUCC(X+7)]	{3, 4, 5, 11}
[X .. 1]	{}

Свойства операторов для множеств

Оператор	Ассоциативность	Приоритет
[ ]	Нет	Высший
*	Левая
+ –	Левая
сравнения	Нет	Низший

Ниже приведено вычисление примеров множеств в нотации констант множеств Паскаля:

[1] + [7 .. 9] * [7, 9] = [1] + [7, 9] = [1, 7, 9]

[4 .. 6] – [4, 6] + [1] = [5] + [1] = [5, 1]

⇐ Предыдущая 123 4 Следующая ⇒