Тип "множество" (Set). Операции с множествами

4

Тип «множество» (Set). Операции с множествами

Множество -- это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект во множестве называется элементом множества. Турбо Паскаль поддерживает все основные операции с множествами. В Паскале множества определяются как наборы значений из некоего скалярного (перечислимого) типа. Скалярные типы - Byte и Char вводятся языком, они - перечислимые и могут служить основой для построения множеств. Если же их станет мало, то всегда можно ввести свой скалярный тип, например:

TYPE

VideoAdapterType = (MDA, Hercules, AGA, CGA, MCGA, EGA, VGA, Other, NotDetected);

и использовать переменную

VAR VideoAdapter: VideoAdapterType;

которая может иметь только перечисленные в задании типа значения. А далее можно ввести переменную -- множество из тех же значений.

В описании множества как типа используется конструкция Set of и следующее за ней указание базового типа, т.е. того скалярного типа, из элементов которого составлено множество. Способов задания множеств несколько:

Таблица 1. TYPE

SetOfChar	= Set of Char; {множество из символов}
SetOfByte	= Set of Byte; {множество из чисел}
SetOfVideo	= Set of VideoAdapterType; { множество из названий видеоадаптеров}
SetOfDigit	= Set of 0..9; {множество из чисел от 0 до 9}
SetOfDChar	= Set of `0'..'9'; { множество из символов `0','1',..,'9'}
SetOfVA	= Set of CGA.. VGA; { подмножество названий видеоадаптеров}

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

Если перечислимый тип вводится только для подстановки его имени в Set of, то можно перечислить значения сразу в конструкции Set of. He забудьте круглые скобки!

TYPE SetOfVideo = Set of (MDA, Hercules, AGA, CGA, MCGA, EGA, VGA, Other, NotDetected);

SetOfGlasn = Set of ('А', `И','0','У, `Э');

Можно опустить фазу описания типа в разделе TYPE и сразу задавать его в разделе описания переменных:

VAR V1: Set of...

В Турбо Паскале разрешено определять множества, состоящие не более чем из 256 элементов. Столько же элементов содержат типы Byte и Char, и это же число является ограничением количества элементов в любом другом перечислимом базовом типе множества, задаваемом программистом. Каждый элемент множества имеет сопоставимый номер. Для типа Byte номер равен значению числа, в типе Char номером символа является его ASCII-код. Всегда нумерация идет от 0 до 255. По этой причине не являются базовыми для множеств типы ShortInt, Word, Integer, LongInt.

Множества имеют весьма компактное машинное представление: один элемент расходует 1 бит. Поэтому для хранения 256 элементов достаточно 32 байт (для меньшего диапазона значений множеств цифра будет еще меньше).

Переменная, описанная как множество, подчиняется специальному синтаксису. Элементы множества должны заключаться в квадратные скобки:

Таблица 2. Применение квадратных скобок

SByte	:=	[1,2,3,4,10,20,30,40];
SChar	:=	[`а', `б', `в'];
SChar	:=	[ `r'];
SVideo	:=	[CGA, AGA, MCGA];
SDiap	:=	[1..4];
SComp	:=	[1..4,5,7,10..20];
SCharS	:=	[`а'..'п', `р'..'я'];
Empty	:=	[]

Пустое множество записывается как [ ]. Порядок следования элементов внутри скобок не имеет значения так же, как не имеет значения число повторений. Например, многократное включение элемента «а» во множество

SetVar: = [`а', `б', `а', `а']; эквивалентно его однократному упоминанию. В качестве элементов множества в квадратные скобки могут включаться константы и переменные соответствующих базовых типов. Более того, можно вместо элементов подставлять выражения, если тип их результата совпадает с базовым типом множества:

VAR

X: Byte;

S: Set of Byte;

X: = '3'

S: = [1, 2, X];

S: = S + [X+1]; {и т. п.}

Таблица 3. Операции, применимые к множествам

	Название	Форма	Комментарий
=	Проверка на равенство	S1=S2	Результатом будет логическое значение, равное True, если S1 и S2 состоят из одинаковых элементов независимо от порядка следования, и False в противном случае
<>	Проверка на неравенство	S1<>S2	Результатом будет логическое значение, равное True, если S1 и S2 отличаются хотя бы одним элементом, False в противном случае
<=	Проверка на подмножество	S1<=S2	Результатом будет логическое значение, равное True, если все элементы S1 содержатся и в S2 независимо от их порядка следования, и равное False в противном случае
>=	Проверка на надмножество	S1>=S2	Результатом будет логическое значение, равное True, если все элементы S2 содержатся в S1,и False в противном случае
In	Проверка вхождения элемента в множество	Е in [...] Е in S1	Результатом будет логическое значение True, если значение Е принадлежит базовому типу множества, и входит в множество [..] (S1). Если множество не содержит в себе значения Е, то результатом будет False
+	Объединение множеств	S1+S2	Результатом объединения будет множество, полученное слиянием элементов этих множеств и исключением дублированных элементов
-	Разность множеств	S1-S2	Результатом операции взятия разности S1-S2 будет множество, составленное из элементов, входящих в S1, но не входящих в S2
*	Пересечение множеств	S1*S2	Результатом пересечения будет множество, состоящее только из тех элементов S1 и S2, которые содержатся одновременно и в S1, в S2

Как видно, операции над множествами разделяются на операции сопоставления множеств и операции, создающие производные множества. И те, и другие будут работать лишь в том случае, когда их операнды сопоставимы. Это означает, что в операциях могут участвовать только те множества, которые построены на одном базовом типе (так, несопоставимы множества значений типа Char и типа Byte).

Операции сопоставления всегда двухместные. Результатом операции сопоставления будет логическое значение True или False. В этом смысле они близки операциям сравнения. Рассмотрим некоторые примеры сопоставлений.

Таблица 4. Операции сопоставления

Значение S1	Значение S2	Выражение	Результат
[1,2,3,4]	[1,2,3,4]	S1=S2	True
[`а','b','с']	[`с', `а']	S1=S2	False
[`а'..'z']	[`z'..'а']	S1=S2	True
[1,2,3]	[3,1,2,4]	S1<>S2	True
[`а'..'z']	[`b'..'z']	S1<>S2	True
[`c'..'t']	[`t'..'c']	S1<>S2	False
[1,2,3,4]	[2,3,4]	S1>=S2	True
[`а'..'z']	[`b'..'t']	S1>=S2	True
[`z', 'x', 'c']	[`c', 'x']	S1>=S2	True
[1,2,3]	[1,2,3,4]	S1<=S2	True
[`d'..'h']	[`z'..'а']	S1<=S2	True
[`a', 'v']	[`a', `n', 'v']	S1<=S2	True

Операция проверки вхождения во множество in бывает очень полезна при проверке попадания в диапазоны перечислимых типов:

Таблица 5. Операция проверки вхождения во множество in

Значение S1	Выражение	Результат
2	if S1 in [1, 2, 3] then..	True
`v'	if S1 in [`a'..'n'] then..	False
X1	if S1 in [X0, X1, X2, X3] then..	True

Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций.

Например, выражение

if (а=1) or (а=2) or (а=3) or (а=4) or (а=5) or (а=6) then...

можно заменить более коротким выражением

if a in [1..6] then...

Часто операцию in пытаются записать с отрицанием: Х NOT in М. Такая запись является ошибочной, так как две операции следуют подряд; правильная инструкция имеет вид NOT (X in М). Вторая группа операций над множествами реализует математические действия над ними: объединение, дополнение и пересечение множеств. Результатом операций всегда будет множество. Приведем некоторые примеры операций. Операции объединения и пересечения не зависят от мест операндов, но результат операции дополнения чувствителен к порядку следования, и S1- S2 не будет в общем случае равно S2 - S1. Поэтому результат выражений типа S1-S2-S3 будет зависеть от порядка вычислений (слева направо или наоборот), устанавливаемых компилятором. Обычно принято вычислять слева направо, но лучше не закладывать так явно в программу особенности компиляторов, в том числе не искать «многоместных» разностей. Их лучше вычислять через промежуточные переменные.

Таблица 6. Промежуточные переменные

Значение S1	Значение S2	Выражение	Результат
[1,2,3]	[1,4,5]	S1+S2	[1,2,3,4, 5]
[`A'..'D']	[`E'..'Z']	S1+S2	[`A'..'Z']
[]	[]	S1+S2	[]
[1,2,3]	[1,4,2,5]	S1*S2	[1, 2]
[`A'..'Z']	[`B'.. 'R']	S1*S2	[`B'.. 'R']
[]	[]	S1*S2	[]
[1,2,3,4]	[3,4,1]	S1-S2	[2]
[`A'..'Z']	[`D'.. 'Z']	S1-S2	[`A'..'C']
[X1, X2, X3,X4]	[X4, X1]	S1-S2	[X2, X3]

Достоинства множеств очевидны: гибкость представления наборов значений (правда, ограниченных типов и размеров), удобство их анализа. Механизм работы с множествами Турбо Паскаля соответствует базовым математическим действиям с конечными множествами. Значения типа «множество» очень компактно кодируются, и множество из 256 элементов займет всего лишь 32 байта. Множества хорошо работают там, где нужно проводить анализ однотипных выборок значений или накапливать произвольно поступающие значения. Недостатки множеств -- это обратная сторона их достоинств. За компактность представления приходится платить невозможностью вывода множеств на экран, хотя отладчик это проделывает. Причем, эта проблема трудноразрешима, ибо отсутствует механизм изъятия элемента из множества. Довод, что и в математике такое действие не определено, малоутешителен. Можно только убедиться в его наличии во множестве. Ввод множеств возможен только по элементам

Пример_1. Иллюстрацией описания множеств и операций над ними может служить программа Dem_Mno, в которой описаны множества чисел D,D1, D2, D3. Затем они заполнены следующим образом: множество D1 -- четными числами 2, 4, 6, 8; множество D2 -- числами 0, 1, 2, 3, 5; множество D3 -- нечетными числами 1, 3, 5, 7, 9. После этого над множествами выполнены операции объединения, разности и пересечения.

Program Dem_Mno; {Демонстрация операций над множествами}

Type

Digits=Set of 0..9;

Var

D1,D2,D3,A,B,C,D: Digits;

Begin

D1:=[2,4,6,8]; {Заполнение множеств}

D2:=[0,3,5];

D3:=[1,3,5,7,9];

A:=D1+D2; {Объединение множеств D1 и D2}

B:=A+D3; {Объединение множеств A и D3}

C:=B-D2; {Разность множеств B и D2}

D:=C*D1; {Пересечение множеств C и D1}

End.

Как видно из текста программы, сначала описан тип Digit =Set of 0..9, затем описаны переменные D1, D2, D3, A,B,C,D этого типа. В первой части программы осуществляется заполнение множеств, а затем над множествами выполняются операции объединения, пересечения, разности. Так как в Pascal отсутствуют средства ввода-вывода элементов множества, то работу программы придется проверять, выполняя ее в пошаговом режиме и отслеживая изменения значений переменных D1, D2, D3, A, B, C, D в окне просмотра.

Результат просмотра:

A= [0, 2..6, 8]

B= [0..9]

C= [1, 2, 4, 6..9]

D= [2, 4, 6, 8]

Пример 2. Опишите множество М (1..50). Сделайте его пустым. Вводя целые числа с клавиатуры, заполните множество десятью элементами.

В разделе описания переменных опишем множество целых чисел от 1 до 50, переменную Х целого типа будем использовать для считывания числа во множество, целую переменную I используем для подсчета количества введенных чисел.

В начале программы применим операцию инициализации множества M:=[], так как оно не имеет элементов и является пустым.

Заполнение множества элементами произведем с использованием оператора for, параметр которого I будет указывать порядковый номер вводимого элемента. Операцию заполнения множества запишем в виде оператора присваивания М:=М+[Х]. Контроль заполнения множества запишем с использованием операции проверки принадлежности in. Если условие выполняется, выведем сообщение о том, что число Х помещено во множество.

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

Program Inpu_Mno;

Uses CRT;

Var

M: Set of 1..50;

X, I: integer;

Begin

ClrScr;

M:=[];

for I:=1 to 10 do

begin

write ('Введите ', I,'-й элемент множества ');

readln (X);

if X in [1..50] then

begin

writeln ('Элемент ',X:2, ' помещен во множество 1..50 ');

M:=M+[X];

end;

end;

readln;

End.

Результат диалога:

Введите 1-й элемент множества 2

Элемент 2 помещен во множество 1..50

Введите 2-й элемент множества 1

Элемент 1 помещен во множество 1..50

Введите 3-й элемент множества 3

Элемент 3 помещен во множество 1..50

Введите 4-й элемент множества 5

Элемент 5 помещен во множество 1..50

Введите 5-й элемент множества 6

Элемент 6 помещен во множество 1..50

Введите 6-й элемент множества 7

Элемент 7 помещен во множество 1..50

Введите 7-й элемент множества 0

Введите 8-й элемент множества 9

Элемент 9 помещен во множество 1..50

Введите 9-й элемент множества 5

Элемент 5 помещен во множество 1..50

Введите 10-й элемент множества 3

Элемент 3 помещен во множество

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

Результат просмотра

M= [1..3, 5..7,9]

Пример 3. Описать множество гласных и согласных букв русского алфавита, определить количество гласных и согласных букв в предложении, введенном с клавиатуры.

Зададим тип Letter -- множество букв русского алфавита, затем опишем переменные этого типа: Glasn - множество гласных букв, Sogl - множество согласных букв. Вводимое с клавиатуры предложение опишем переменной Text типа String. Для указания символа в строке Text применим переменную I типа byte. Для подсчета количества гласных и согласных букв опишем переменные G и S.

В целом текст программы будет выглядеть следующим образом:

Program Glasn_Sogl;

Uses CRT;

Type

Letters=set of 'А'..'я';

Var

Glasn, Sogl:letters;

Text:string;

I:byte;

G,S:byte;

Begin

ClrScr;

Glasn:=['А','а','Е','е','И','и','О','о','У','у','Э','э','Ю','ю','Я','я'];

Sogl:=['Б'..'Д','б'..'д','Ж','ж','З','з','К'..'Н',

'к'..'н','П'..'Т','п'..'т','Ф'..'Щ','ф'..'щ','Ъ','ъ','Ь','ь'];

writeln ('Введите предложение');

readln (Text);

G:=0;

S:=0;

for I:=1 to Length (Text) do

begin

if Text[I] in Glasn then G:=G+1;

if Text[I] in Sogl then S:=S+1;

end;

writeln ('В предложении',G:3,' гласных и',S:3,' согласных букв');

readln;

End.

Результат работы:

Введите предложение:

Проверка программы

В предложении 5 гласных и 11 согласных букв

Пример 4. Пусть дана последовательность символов с точкой в конце. Определить число различных букв, входящих в данную последовательность.

Программа для реализации данной задачи имеет следующий вид:

Program Sim_Mno;

Uses CRT;

Var

M: set of char;

I: char;

Mos:integer;

Begin

ClrScr;

writeln ('Введите последовательность символов');

M:=[];

while True do begin

read (I);

if I='.' then break;

M:=M+[I];

end;

Mos:=0;

for I:='A' to 'z' do

if (I in M) then Mos:=Mos+1;

writeln ('Число различных букв=', Mos:3);

readln;

End.

Результат работы:

Введите последовательность символов

p

r

o

g

r

a

m

.

Число различных букв= 6