Программирование - 07 - Множества

5

7 Множества

Множество — это структурированный тип данных, представляющий набор взаимосвязанных по какому-либо признаку (или группе признаков) элементов, которые можно рассматривать как единое целое.

Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественных (и других скалярных типов, число элементов которых превышает 256). Этот тип называется базовым типом множества. Количество элементов множества не должно превышать 256. Поэтому нельзя использовать в качестве базового типа типы, количество элементов которых превышает 256 (например, Integer), для таких типов в качестве базового типа можно использовать диапазоны или перечисления из их значений.

Область значений переменных типа множество — набор всевозможных подмножеств, составленных из элементов базового типа. Если базовый тип принимает N значений, то тип множество для него будет иметь вариантов различных значений (порядок элементов в подмножествах не учитывается).

Формат описания:

1-ый способ:

Type

имя_типа_множество = set of базовый_тип ;

Var

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

2-ой способ:

Var

имя_множества : set of базовый_тип ;

Пример 7.1 ( описания множеств ):

Type

Chislo = set of 1..31 ;

LatBold = set of ‘A’ .. ’Z’ ;

Col = set of ( Red, Green, Blue ) ;

Day = ( Mon, Tues, Wed, Thur, Fri, Sat, Sun ) ;

WorkDay = set of Mon .. Fri ;

Var

Ch1, Ch2 : Chislo ;

LatB1 : LatBold ;

C1, C2, C3 : Col ;

WD1, WD2, WD3, WD4 : WorkDay ;

KirB : set of ‘А’..’Я’ ;

Выражения с множествами

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

Операнды множественного типа:

• переменные типа множество;

• множественные конструкции (множественные константы).

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

Например,

[ 1, 2, 5, 17 ]

[ 1..50 ]

[ 1..5, 10..100 ]

[ x+y..2*x+3*y ]

[ ‘P’, ‘a’, ‘s’, ‘c’, ‘a’, ‘l’ ]

[ ‘A’..’Z’ ]

[ ] — пустое множество

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

1. * (пересечение: );

2. + (объединение: );

– (относительное дополнение — разность множеств: \ );

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

= (проверка равенства множеств);

<> (проверка неравенства множеств);

<= или >= (проверка включения одного множества в другое);

in (проверка принадлежности элемента множеству).

Примеры 7.2 ( операции над множествами ):

A	B	Операция	Результат
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A*B	[ 2, 3 ]

A	B	Операция	Результат
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A+B	[ 1, 2, 3, 4 ]

A	B	Операция	Результат
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A-B	[ 1 ]

A	B	Операция	Результат
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A=B	False
[ 1, 2, 3 ]	[ 1, 2, 3 ]	A=B	True
[ ’a’..’z’ ]	[ ’a’..’z’ ]	A=B	True
[ ’a’..’z’ ]	[ ’b’..’z’ ]	A=B	False

A	B	Операция	Результат
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A<>B	True
[ 1, 2, 3 ]	[ 1, 2, 3 ]	A<>B	False
[ ’a’..’z’ ]	[ ’a’..’z’ ]	A<>B	False
[ ’a’..’z’ ]	[ ’b’..’z’ ]	A<>B	True

A	B	Операция	Результат
[ 1, 2, 3, 4 ]	[ 2, 3, 4 ]	A>=B	True
[ 1, 2, 3 ]	[ 2, 3, 4 ]	A>=B	False

A	B	Операция	Результат
[ 2, 3, 4 ]	[ 1, 2, 3, 4 ]	A<=B	True
[ 2, 3, 4 ]	[ 1, 2, 3 ]	A<=B	False

N	A	Операция	Результат
3	[ 2, 3, 4 ]	N in A	True
1	[ 2, 3, 4 ]	N in A	False
’d’	[ ’b’..’z’ ]	N in A	True
’a’	[ ’b’..’z’ ]	N in A	False

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

Процедуры работы с множествами

Procedure ...

Include ( var MySet : set of T ; IncSubSet : T ) ;
—	добавляет к множеству MySet подмножество IncSubSet, где MySet — переменная типа множество любого допустимого базового типа T; IncSubSet — выражение типа T
Exclude ( var MySet : set of T ; IncSubSet : T ) ;
—	удаляет из множества MySet подмножество IncSubSet

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

Использование множеств

Использование множеств в программах дает следующие преимущества:

• значительно упрощаются сложные операторы if;

• увеличивается наглядность программы и понимание алгоритма решения задачи;

• в ряде случаев экономится память, время компиляции и выполнения (объем памяти, занимаемый одним элементом множества, составляет 1 бит; множественные операции выполняются быстрее).

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

Пример. Требуется создать множество из элементов типа Char (выход из фазы создания осуществить при вводе значения ‘z’); найти в нем элемент с минимальным номером в таблице кодов; распечатать все элементы созданного множества в алфавитном порядке. Управление работой программы осуществить из меню.

Program DemoSet ;

Var

S : set of Char ;

N, Rejim : Char ;

Procedure Konstr ;

Begin

Writeln ( ‘Вводите элементы множества из букв a..z; символ z – окончание ввода’ ) ;

S := [ ];

While True do

Begin

ReadLn ( N ) ;

S := S + [ N ] ;

If N = ‘z’

then Exit

end

End ;

Procedure MinS ;

Begin

N := ‘ ‘;

While not ( N in S ) do

N := Succ( N ) ;

Writeln ( ‘Элемент с минимальным номером = ’ , N )

End ;

Procedure Rasp ;

Begin

For N := ‘a’ to ‘z’ do

If N in S

Then wtiteln ( N )

End ;

Begin

While True do

Begin

Writeln ( ‘1 – Создание’ ) ;

Writeln ( ‘2 – Поиск Эл-та с мин-м номером’ ) ;

Writeln ( ‘3 – Вывод Эл-ов мн-ва’ ) ;

Writeln ( ‘4 – Выход из программы’ ) ;

Readln ( Rejim ) ;

Case Rejim of

‘1’ : Konstr ;

‘2’ : MinS ;

‘3’ : Rasp ;

‘4’ : Halt

end

End

End.