Множества в Паскале, их описание. Операции над множествами

Под множеством в языке Паскаль понимают ограниченный неупорядоченный набор различных элементов одинакового типа, логически связанных друг с другом. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255. Множество, не содержащее элементов, называется пустым. Множество имеет имя. Тип элементов, входящих в множество, называется базовым. В качестве базового типа можно использовать любой порядковый тип, кроме Word, Integer, Longint.

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

Var Имя множества:Set of базовый тип;

Или

Type Имя типа=Set of базовый тип;

Var Имя множества:Имя типа;

Например:

Type

TM=Set of 1..100;

TS=Set of 'a'..'z';

Var Mch:TM; {Множество целых чисел от 1 до 100}

MSym:TS; {Множество строчных латинских букв}

M: Set of 1..10; {Множество целых чисел от 1 до 10}

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

Например:

Var M1,M2,M3:set of 1..99;

Begin . . .

M1:=[]; { Множество пустое}

M2:=[1,3,5,7,9]; { Множество нечетных чисел в первом десятке}

M3:=[2,4,6,8]; { Множество четных чисел в первом десятке}

. . .

End.

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

Типизированная константа - множество задается в виде правильного конструктора множества, например:

Type

Type_month=(Jn,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);

TDays=Set of 1..31;

Tmonth=Set of 1..12;

Tsym=Set of 'A'..'Z';

Tmno=Set of Type_month;

Const

SymMno:Tsym=['A','E','I','O','U']; {подмножество гласных букв}

DaysMno:TDays=[1,8,15,22,29]; {подмножество выходных дней месяца}

Spring_Mes:Tmonth=[3,4,5]; {подмножество весенних месяцев года}

Spring_Month:Tmno=[Mar,Apr,May]; {то же, что и предыдущее}

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

1) * - пересечение множеств: результат содержит элементы, общие для обоих множеств. Например: пусть имеется описание:

Var S1,S2,S3,S4,S5:Set of 1..10;

Begin

S1:=[1,3,4,6];

S2:=[2,4,5,1];

S3:=S1*S2; - в S3 будет содержаться [1,4].

2) +- объединение множеств : результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:

S4:=S1+S2; - в S4 будет содержаться [1,3,4,6,2,5].

3) - -разность множеств: результат содержит элементы из первого множества, которые не принадлежат второму:

S5:=S1-S2; - в S5 будет содержаться [3,6].

4) =- проверка эквивалентности (или равенства): возвращает TRUE, если оба множества эквивалентны, т.е. содержат все одинаковые элементы.

5) <>- проверка неэквивалентности (или неравенства): возвращает TRUE, если оба множества неэквивалентны, т.е. содержат неодинаковые элементы.

6) <= - проверка вхождения: возвращает TRUE, если первое множество включено во второе (т.е. все элементы первого множества присутствуют также и во втором).

7) >= - проверка вхождения: возвращает TRUE, если второе множество включено в первое.

8) IN- проверка принадлежности элемента множеству. Эта операция возвращает результат TRUE, если элемент (или выражение), стоящий слева принадлежит множеству, указанному справа.

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

Include- включает новый элемент во множество: Include(M,elem);

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

Exclude -исключает элемент из множества: Exclude(M,elem).

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

Основным достоинством использования множеств является экономия памяти: внутренне устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит). Если элемент включен в множество, то соотвествующий разряд имеет значение 1, в противном случае - 0. Минимальной единицей памяти является 1 байт, содержащий 8 бит, поэтому для хранения множества мощностью 256 элементов выделяется память 32 смежных байта.

Рассмотрим работу с множествами на следующем примере.

Из множества целых чисел от 1 до 20 выделить:

1) множество чисел, делящихся на 2 и 3 одновременно;

2) множество чисел, делящихся на 2 или на 3.

Первая задача соответствует нахождению пересечения множеств чисел, одно из которых содержит числа, делящиеся на 2, а другое на 3. Вторая - объединению этих двух множеств.

Обозначим множество чисел, делящихся на 2 через М2; множество чисел, делящихся на 3 через М3; множество чисел, делящихся на 2 и 3 через М2and3; множество чисел, делящихся на 2 или 3 через М2or3.

Текст программы

Type TM=Set of 1..20; {Описание типа множества целых чисел от 1 до 20}

Var M2,M3,M2and3,M2or3:TM; {Описание множеств}

k:1..20; {Описание переменной}

Begin

M2:=[]; M3:=[]; {Пустые множества}

for k:=1 to 20 do

begin

if k mod 2 = 0 then Include(M2,k); {Включение элемента делящегося на 2 в

множество М2}

if k mod 3 = 0 then Include(M3,k); { Включение элемента делящегося на 3 в

множество М3}