Понятие множества
МНОЖЕСТВА
Лекция №11.
Множественный тип данных в языке Паскаль соответствует математическому представлению о множествах: это ограниченная совокупность различных элементов. Множество создается на основе элементов базового типа, он может быть перечисляемым, интервальным или byte. В множестве не может быть более 256 элементов.
Множество описывается с помощью служебных слов set of :
type имя_типа = set of базовый_тип;Примеры:
type Caps = set of 'A'.. 'Z'; Colors = set of (RED, GREEN, BLUE); Numbers = set of byte;Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных, например:
var oct: set of 0.. 7;Константы множественного типа записываются в виде заключенной в квадратные скобки последовательности элементов или интервалов базового типа, разделенных запятыми, например:
['A', 'D'] [1, 3, 6] [2, 3, 10.. 13].Константа вида [ ] означает пустое подмножество.
Тип "множество" задает набор всех возможных подмножеств его элементов, включая пустое. Если базовый тип, на котором строится множество, имеет k элементов, то число подмножеств, входящих в это множество, равно 2k.
|
|
Переменная множественного типа содержит одно конкретное подмножество значений множества. Пусть имеется переменная b интервального типа:
var b: 1.. 3;Эта переменная может принимать три различных значения: 1, 2 или 3. Переменная m множественного типа
var m: set of 1.. 3;может принимать восемь различных значений:
[ ] [1] [2] [3] [1, 2] [1, 3] [2, 3] [1, 2, 3]Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char, boolean и производные от них типы.
Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.
Число байтов, выделяемых для данных типа множество, вычисляется по формуле:
ByteSize = (max div 8) - (min div 8) + 1,
где max и min — верхняя и нижняя границы базового типа данного множества.
Номер байта для конкретного элемента Е вычисляется по формуле:
ByteNumber = (E div 8) - (min div 8),
номер бита внутри этого байта по формуле:
BitNumber = E mod 8
Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1, 2, 3] и [3, 2, 1] — это эквивалентные множества.
Каждый элемент в множестве учитывается только один раз. Поэтому множество [1, 2, 3, 4, 2, 3, 4, 5] эквивалентно [1..5].
Нельзя вводить значения во множественную переменную процедурой ввода и выводить процедурой вывода.
Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания:
<множественная переменная>:= <множественное выражение>;