Множества в Pascal

Во многих языках программирования имеется такой тип данных как множества. Множество - это неупорядоченная структура данных, в которой каждое значение может быть представлено только одни раз.

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

Размер множества в Паскале ограничен предельно допустимым количеством элементов. Во множествах допускаются только такие элементы, порядковые значения которых в их базовых типах не выходят за границы 0..255. Для целочисленных множеств это означает, что в них могут присутствовать только числа от 0 до 255. Отрицательные элементы во множествах не допускаются.

Поэтому базовым типом не может выступать, например, integer. Если необходимо множество целочисленных объектов, то базовый тип должен объявлен как диапазон типа byte. Для символьных множеств базовым типом является char (в нем 256 значений с порядковыми номерами от 0 до 255).

Объявление множеств

В математике для обозначения множества используют фигурные скобки, например {4, 7, 12}, в Паскале — квадратные, например [1, 3, 5]. Порядок элементов во множестве не имеет значения. Так множества [3, 6, 9] и [9, 3, 6] одинаковы.

По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:

var
  имя: set of тип;

Например, объявление переменной ch как множества с базовым типом char, имеет вид:

var
  ch: set of char;

Можно сначала объявить тип множества, а потом использовать его для объявления переменных:

type
  t_ch = set of char;
var
  ch1, ch2: t_ch;

Часто в качестве базового типа используются перечисления и диапазоны:

type
  week_days = (Mon, Tue, Wed, Thu, Fri);
var
  work_days: set of week_days;
  lett: set of 'A'..'Z';

type
    nums = 5..25;
var 
    a: set of nums;

Объявление переменной-множества не присваивает ей набора значений.

Построение множества

Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой — конструктор множества или некоторое выражение над множествами.

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

type
  week_days = (Mon, Tue, Wed, Thu, Fri);
var
  work_days: set of week_days;
  lett: set of 'A'..'Z';
begin
  work_days := [Mon, Wed, Thu];
  lett := ['C', 'E'..'M', 'Z']
end.

Следует помнить, что при задании множества порядок его элементов безразличен, но при задании диапазона такой порядок важен.

Множество, в котором нет элементов, называется пустым (или нуль-множеством). В языке программирования Паскаль обозначается квадратными скобками, между которыми нет элементов:

work_days := [ ];

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

const 
    lett: set of ['а'..'я'] = ['а', 'е', 'и', 'о', 'у', 'ы', 'э', 'ю', 'я'];

Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 и ch2 имеют тип char, то допустима следующая последовательность операторов:

ch1 := 'A';
ch2 := 'K';
chs := [ch1, ch2, 'M'];

В результате получится множество ['A', 'K', 'M'].

Вывод элементов множества

В Pascal элементы множества нельзя вводить и выводить. Для организации их ввода-вывода следует использовать вспомогательные переменные. В то же время можно использовать множества как элементы типизированных файлов.

type
    nums = 0..10;

var 
    a: set of nums;
    i: byte;

begin

    a := [3, 0, 2];

    for i := 0 to 10 do
        if i in a then
            writeln(i);
end.

Результат выполнения:

0
2
3

Операции над множествами

• присвоение
• объединение
• пересечение
• дополнение
• тождественность
• нетождественность
• содержится во множестве
• содержит множество
• принадлежность элемента множеству

Объединение, пересечение и разность множеств

Над множествами выполнимы объединение (+), пересечение (*) и разность (-).

Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.

var
  chs1, chs2, chs3: set of char;
begin
  chs1 := ['a', 'b', 'd'];
  chs2 := ['m', 'd', 'e'];
  chs3 := chs1 + chs2 + ['k', 'n'];
end.

Результат: chs3 = ['a', 'b', 'd', 'm', 'e', 'k', 'n'].

Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.

chs3 := chs1 * chs2;

Результат: chs3 = ['d'].

Разность (дополнение) множеств A и B (A - B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.

chs1 := ['a', 'e', 't'];
chs2 := chs1 – ['e']    { ['a', 't'] }
chs3 := ['m', 'n', 't'] – chs2  { ['m', 'n'] }

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

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

include(имя_множества, элемент)
exclude(имя_множества, элемент)

Первая из них позволяет выполнить добавление одного элемента в указанное множество, а вторая удалить. Например:

include (chs1, 'g');  { аналогично chs1 + ['g'] }
exclude (chs2, 'a');  { аналогично chs2 - ['a'] }

Операции сравнения множеств

Над множествами можно выполнять четыре операции сравнения: =, <>, >=, <=.

Два множества A и B равны (A = B), если каждый элемент множества A является элементом множества B и наоборот.

Два множества A и B не равны (A <> B), если они отличаются хотя бы одним элементом.

Другими словами, операции = и <> используются для проверки эквивалентности: два значения переменной типа set считаются равными, если они состоят из одних и тех же элементов.

[1, 3] = [3, 1] возвращает true,
[1..3] = [1, 2, 3] возвращает true,
[1] <> [2] возвращает true,
[1, 2, 3] = [1, 4, 3] возвращает false,
[red, blue] = [red, yellow] возвращает false.

Множество A является подмножеством множества B (A <= B, или B >= A), если каждый элемент из A присутствует в B.

Операции >= и <= используются для проверки принадлежности одного множества другому: так, если множество a содержится во множестве b, то a <= b дает true.

[1, 2] <= [1, 2, 3] дает true

Пустое множество [ ] содержится во всех множествах, т.е. всегда [ ] <= [b] дает true.

in - операция проверки принадлежности элемента множеству

Имеется возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in. Пусть A – множество элементов некоторого базового типа, а x – переменная этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A.

red in [red, yellow] возвращает true;
red in [blue, green] возвращает false.

Замечание 1. Чтобы проверить, является ли значение n цифрой, удобно использовать операцию in следующим образом:

if n in [0..9] then …

Замечание 2. Результат операции in может быть неопределенным в некоторых случаях. Пусть:

a: set of 1..50;
x: integer.

Если присвоить x число, большее максимального значения 50 (например, x := 55), то в этом случае результат операции x in a не всегда false.

Все операции сравнения множеств, а также операция in возвращают логическое значение true или false.

Приоритеты операций над множествами

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

1. *
2. +, -
3. =, <>, <=, >=, in