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

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

TYPE

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

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

VAR

VideoAdapter : VideoAdapterType;

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

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

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;

{ подмножество названий видеоадаптеров }

- 143 -

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

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

TYPE

SetOfVideo = Set of (MDA, Hercules, AGA, CGA, MCGA,

EGA, VGA, Other, NоtDetected);

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

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

VAR

V1 : Set of ...

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

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

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

SByte := [1, 2, 3, 4, 10, 20, 30, 40];

SChar := ['а', 'б','в'];

SChar := ['г'];

SVideo = [ CGA, AGA, MCGA];

SDiap := [1..4]; {то же, что [1, 2, 3, 4]}

SComp := [1..4, 5, 7, 10..20];

SCharS := ['а..п', 'р..я']; Empty := [];

Пустое множество записывается как [].

- 144 -

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

SetVar := ['а', 'б', 'а', 'а'];

эквивалентно однократному его упоминанию.

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

VAR

X : Byte; S : Set of Byte;

...

X := 3;

S := [ 1, 2, X ];

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

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

Таблица 7.2

Название

Форма

Комментарий

=

Проверка на равенство

S1=S2

Результатом будет логическое равенство значение, равное True, если S1 и S2 состоят из одинаковых элементов независимо от порядка следования, и False в противном случае

<>

Проверка на неравенство

S1<>S2

Результатом будет логическое неравенство значение, равное True, если S1 и S2 отличаются хотя бы одним элементом, False в противном случае

<=

Проверка на подмножество

S1<=S2

Результатом будет логическое подмножество значение, равное True, если все элементы S1 содержатся и в S2 независимо от их порядка следования, и равное False в противном случае

>=

Проверка на надмножество

S1>=S2

Результатом будет логическое надмножество значение, равное True, если все элементы S2 содержатся в S1 , и False в противном случае

- 145 -

in

Проверка вхождения элемента в множество

E in [...] E in S1

Результатом будет логическое значение True, если значение E принадлежит базовому типу множества и входит в множество [ ... ] (S1). Если множество не содержит в себе значения E, то результатом будет False

+

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

S1+S2

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

-

Разность множеств

S1-S2

Результатом операции взятия разности S1-S2 будет множество, составленное из элементов, входящих в S1, но не входящих в S2

*

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

S1*S2

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

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

Операции сопоставления всегда двухместные. Результатом операции сопоставления будет логическое значение True или False. В этом смысле они близки операциям сравнения. Рассмотрим некоторые примеры сопоставлений (в них X — обозначение переменной базового типа множества, a S — обозначение некоего непустого сопоставимого множества) (рис. 7.2).

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

if Ch in ['а', 'х', 'А', 'Х'] then ...

if J in [ 100..200 ] then ...

В подобных конструкциях можно указывать множество-константу

- 146 -

ИСТИННО

ЛОЖНО

[ 1, 2, 3] = [ 1, 3, 2]

[ 5, X ] = [ X, 5 ]

[] = []

[ 1, 2 ] <> [ 1 ]

[ 5, X ] <> [ 5, Х+1 ]

['a','b'] <= [ 'a'..'z' ]

[] >= S

[X, Х+1] >= [ Х+1 ]

5 in [0..5]

[] in [0..5]

[ 1, 2 ] = [1]

[ 5, X ] = 5, Х+1 ]

[] = [1]

[ 1, 2, 3] <> [1, 3, 2]

[ 5, X ] <> X, 5 ]

['0'..'9']<=[a]…[z]

[]>=S

[1..3]>=[0..4]

X in [X-1, X-2]

X in []

Рис. 7.2

справа от оператора in, не вводя промежуточных описаний переменных-множеств .

Вторая группа операций над множествами реализует математические действия над ними: объединение (сумма), разность (дополнение) и пересечение множеств. Результатом операций всегда будет множество. В табл. 7.2 указаны два множества в записи, но их может быть и больше. Некоторые примеры операций приведены на рис. 7.3. Операции объединения и пересечения не зависят от мест операндов, но

[1, 2, 3, 4, 4 ] + [ 3, 4, 4, 5, 6] даст [1, 2, 3, 4, 5, 6] ([1..6])

[ '1', '2' ] + [ '8', '9' ] даст [ '1', '2', '8', '9' ]

[ X ] + [] даст [X]

[ X ] + [ Х+1 ] + [ Х+2 ] даст [ X .. Х+2 ]

[ 1, 2, 3, 4, 4] - [3, 4, 4, 5, 6] даст [ 1, 2 ]

[ '1', '2' ] - ['8', '9'] даст [ '1', '2' ]

[ X ]-[] даст [ X ]

[] - [ X ] даст []

[ 1, 2, 3, 4, 4 ] * [3, 4, 4, 5, 6] даст [ 3, 4 ]

[ '1', '2'] * [ '8', '9' ] даст []

[ X ] * [] даст []

[ A ] * [ A, B ] * [ A, B, С ] даст [ А ]

Рис. 7.3

- 147 -

результат операции дополнения чувствителен к порядку следования, и S1-S2 не будет в общем случае равно S2-S1. Поэтому результат выражений типа S1-S2-S3 будет зависеть от порядка вычислений (слева направо или наоборот), устанавливаемых компилятором. Обычно принято вычислять слева направо, но лучше не закладывать так явно в программу особенности компиляторов, в том числе не искать «многоместных» разностей. Их лучше вычислять через промежуточные переменные.

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

Недостатки множеств — это обратная сторона их достоинств. За компактность представления приходится платить невозможностью вывода множеств на экран, хотя отладчик это проделывает. Причем, эта проблема трудноразрешима, ибо отсутствует механизм изъятия элемента из множества. Довод, что и в математике такое действие не определено, малоутешителен. Можно только убедиться в его наличии в множестве. Ввод множеств возможен только по элементам, как на рис. 7.4.

| VAR

| S : Set of Char; { переменная-множество }

| C : Char; { элемент множества }

| BEGIN

| S := []; С := #0; { обнуление значений }

| while C<> '.' do begin

| { цикл до ввода '.' : }

| ReadLn( C ); { чтение символа в C и }

| S := S + [ С ] { добавление его к S }

| end; {while}

| S := S - [ '.' ] { можно выбросить точку }

| ...

| END.

Рис. 7.4

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

- 148 -