Операция со множествами

Лекция №1

Структурированные типы данных. Множества. Объявление множеств. Построение множеств. Операции над множествами. Приоритеты множественных операций. Примеры. Записи. Объявление записей. Вложенные записи.

В языке программирования множество представляет собой ограниченную своеобразную представленную в памяти (по сравнению с другими типами данных) совокупность элементов одного и того же базового типа, который выступает в качестве универсального множества (универсума). В качестве базового типа может выступать: 1) Целочисленный тип: Byte; 2) Символьный тип: char; 3) Перечислимый пользователем тип данных.

В множестве могут присутствовать элементы, порядковые значения которые не выходят за диапазон 0..255. Разрешено объявлять множества, состоящие не более чем из 256 элементов. Нумерация элементов во множестве идет от 0 до 255. В отличие от других типов данных один элемент множества занимает в памяти 1 бит. Исходя из этого для хранения полного множества из 256 элементов, достаточно 32 байта. Такая двоичная форма хранения информации позволяет эффективно реализовывать представление множества и операций над ними. Для обозначения используются квадратные скобки: [ ].

Объявление множеств:

Исполняется ключевым словом set (набор).

Синтаксическое объявление:

Var «Имя переменной»:set of «базовый тип»;

Примеры:

Type

Charset= set of char;

Var

m_ch1,m_ch2:charset;

m_arr: array [1..5] of charset;

m_b: set of byte;

Описывая множество, бывает удобно сразу указать какие элементы, оно может содержать. Это можно осуществить двумя способами: 1.Перечислить все возможные значения (множественно-перечислимый тип); 2. Указать пары граничащих значений (используется чаще).

Примеры:

Type

Digits=setoff 0..9;

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

Var

M1:set of 0..6; (Объем памяти =1 байт)

M2:digits; (Объем памяти =2 байта)

M3:charset;

M4:set of 0..4;

M5:set of(black, white,grey);

M6:set of 7..16; (объем памяти =3 байта, в первый байт входит 7,в третий 16)

Number1,number2:0..9;

Определение памяти требуется для множеств:

M:set of N1…N2; N2>N1.

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

В общем случае использованное множеств не предполагает значение их машинного представления.Эти знания могут быть необходимы при обращении к множеству напрямую, например, через указатель. Размер, занимаемый множеством можно определить с помощью функции size of():

I:= Size of(m6);

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

На этом этапе решается задача с заполнением множеств. способы заполнения множеств:

1) m1:=[0,1,4];

2) m1:=[1,4,0];

3) m5:=[gray, white];

4) m3:=[‘K’..’P’]; аналогично m3:=[‘K’,’L’, ‘M’, ‘N’, ‘O’,’P’ ];

5) m2:=[9,4..7]

2. Задание стартового значения в разделе Const:

Const

M7:set of char=[‘a’..’e’];

3. Заполнение множеств, использую множественные операции (объединение, пересечение, вычитание, исключение смотри ниже).

Обнуление множества:m6:=[];

При задание множества можно использовать переменные в соответствии с базисным типом:

Number1:=1; Number2:=2;

M2:=[number1, number2, 6 ];

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

1. M1:=[1,4,6];

2. M1:=[1,3,6,8,7,10];