Вопрос 28.doc

Вопрос 28

2. Множественный тип данных.

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

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

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

Таким образом, элементами множеств в Паскале не могут быть ни вещественные числа (Real не относится к порядковому типу), ни стринги (это не простой тип, и тем более не порядковый).

Объявление и конструирование множеств Множества в программе могут быть объявлены в разделе описания типов или непосредственно в разделе описания переменных с помощью служебного слова set.

Первый способ объявления переменной типа множества (с использованием раздела типов Туре):

Туре <имя типа> = set оf<базовый  тип>;

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

Второй способ объявления переменной типа множества (в разделе переменных Var):

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

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

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

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

Замечание 2. Если во множестве нет ни одного элемента, то оно называется пустым и обозначается [].

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

Операции, создающие производные множества. Объявим и сконструируем множества:

type    MN1 = set of char;      MN2 = set of byte;

var

N1,N2,N3,N4 : MN2;      C1,C2,C3,C4 : MN1;

begin                                                   

N1:= [1,2,3,4,5];     N2:= [2..6J;            

Cl:= ['0'..'7'];      C2:= ['2', '>', 'K'..'S'];

Объединение двух множеств А и В (записываемое как А+В) есть новое множество, состоящее из элементов, принадлежащих или множеству А, или множеству В, или тому и другому одновременно

Пересечение двух множеств А и В (записываемое как А*В) есть новое множество, состоящее из элементов, принадлежащих как множеству А, так и множеству В.

Разность двух множеств А и В ( записываемая как А-В ) есть новое множество, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

Сравнение множеств. Проверка принадлежности множеству.

Сравнение множеств предполагает проверку следующих ситуаций: равны множества или нет; является ли одно множество подмножеством другого или нет.

1.  Множество А равно множеству В (записывается как А=В) тогда и только тогда, когда каждый элемент множества А является элементом множества В и наоборот.

2. Множество А не равно множеству В (записывается как А<>В), если не каждый элемент множества А является элементом множества В или на¬оборот.

3. Множество А есть подмножество множества В (записывается как А<=В) тогда и только тогда, когда каждый элемент множества А является элементом множества В. В этом случае говорят, что множество А входит во множество В.

4.  Множество В есть подмножество множества А (записывается как А>=В) тогда и только тогда, когда каждый элемент множества В является элементом множества А. В этом случае говорят, что множество А содержит множество В.

Операции сравнения множеств - двуместные. Результат операции будет логического типа : TRUE, если условие выполняется, и FALSE в противном случае.

Проверка принадлежности элемента множеству выполняется с помощью операции in. Пусть элемент S и множество А имеют одинаковый базовый тип. Тогда операция S in А проверяет, принадлежит ли элемент S множеству А; если да, то результат операции TRUE, иначе - FALSE.

В Паскале принят следующий приоритет операций, выполняемых над множествами : *, +, -, =, <>,>=, <=, in. Для изменения порядка выполнения операций используются круглые скобки.