Занятие 1. Множественный тип данных. Множество. Элемент множества. Способы задания множества. Объединение множеств. Разность множеств. Пересечение множеств.

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

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

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

Такие ограничения связаны с формой представления множества в языке и могут быть сведены к тому, что функция Ord для используемого базового типа должна быть в пределах от 0 до 255.

Множество имеет зарезервированное слово set of и вводится следующим описанием

Type

< имя типа > = set of < имя базового типа >;

Var

< идентификатор,... >:< имя типа >;

Рассмотрите примеры описания множеств:

Type

SetByte = set of byte; {множество 1, определённое над типом byte}

SetChisla = set of 10 ... 20; {множество 2, определённое в диапазоне от 10 до 20

Symbol = set of char; {множество, определённое на множестве символов}

Month = (January, February, March, April, May, June, July, August, September, October, November, December);

Season : set of Month; {тип множества, определённый на базе перечислимого типа Month}

Var

Letter, Digits, Sign : Symbol {множествa, определённые над символьным типом}

Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season;

Index : SetChisla=[12, 15, 17];

Operation : set of (Plus, Minus, Mult, Divid);

Param : set of 0..9=[0, 2, 4, 6, 8];

Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет – 0.

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

Sign:=['+', '–'];

Spring:=[March, April, May];

b:=[ 'k', 'l', 'd' ]

либо определение через диапазон. Тогда в множество включены все элементы диапазона

Digits:=['0'..'9'];

WarmSeason := [May .. September];

Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа.

Обе формы конструирования могут сочетаться:

Vacation:=[January, February, June .. August];

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

{постоянное множество допустимых символов

Const

YesOrNo = ['Y', 'y', 'N', 'n'];

{множества – типизированные константы}

Const

Digits : set of char=['0'..'9'];

DigitsAndLetter : set of char=['0'..'9', 'a'..'z', 'A'..'Z'];

{применение операции "+" для объявления множества-константы}

Const

Yes = ['Y', 'y'];

No = ['N', 'n'];

YesOrNo = Yes+No;

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

Определение. Объединением 2-х множеств называется третье множество, которое содержит элементы, которые принадлежат хотя бы одному из множеств операндов, при этом каждый элемент входит в множество только один раз.

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

Type

Symbol = set of char;

Var

SmallLatinLetter, CapitalLatinLetter, LatinLetter : Symbol;

Begin

. . . . . .

SmallLatinLetter :=['a'..'z'];

CapitalLatinLetter := ['A'..'Z'];

LatinLetter := SmallLatinLetter+CapitalLatinLetter;

. . . . . .

End.

В операции объединения множеств могут участвовать и отдельные элементы множества.

Например, допустима следующая запись, где два элемента и множество объединяются в новое множество:

WarmSeason := May+Summer+September;

или другая запись

B: = B+['c'],

которую можно применить для организации множества в цикле, если заменить множество ['c'] переменной Sim того же типа, что и множество B, и считывать с клавиатуры данные в переменную Sim, а затем объединяя с множеством В.

B: = B+Sim,

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

Определение. Разностью 2-х множеств является третье множество, которое содержит элементы 1-го множества, не входящие во 2-е множество.

a: = a–[ 'd' ]

Если в вычитаемом множестве есть элементы, отсутствующие в уменьшаемом, они не влияют на результат.

Summer := WarmSeason–Spring–Autumn;

Summer := WarmSeason–May–September;

Модуль System содержит процедуры для включения элемента в множество

Include(Var S : set of T; Element : T);

и исключения из множества

Exclude(Var S : set of T; Element : T);

где S – множество элементов типа Т, а Element – включаемый элемент.

Эти функции отличаются от операций объединения и вычитания множеств только скоростью исполнения.