Множини

ЛОГІЧНА СТРУКТУРА. Множини – така структура, що представляє собою набір неповторюваних даних одного типу. Множини можуть приймати всі значення базового типу. Базовий тип не повинен перевищувати 256 можливих значень. Тому базовим типом множини можуть бути byte, char, перерахований тип і похідні від цих типів.

ФІЗИЧНА СТРУКТУРА. Множина у пам'яті зберігається як масив бітів, у якому кожен біт вказує, чи є елемент приналежним оголошеній множині чи ні. Таким чином максимальне число елементів множини 256, а дані типу множин можуть займати не більше 32-х байтів. Біт поля встановлений у 1, якщо елемент із номером, рівним номеру даного біта, входить у множину, і в 0 – якщо не входить.

Число байтів, виділених для даних типу множина, обчислюється за формулою:

ByteSіze = (max dіv 8) – (mіn dіv 8) + 1,

де: max і mіn – верхня та нижня границі базового типу даної множини.

Номер байта для конкретного елементу Е обчислюється за формулою:

ByteNumber = (E dіv 8) – (mіn dіv 8).

Номер біта всередині цього байта визначається за формулою:

BіtNumber = E mod 8

Для випадку, наприклад,

var

S : set of byte; {max=255, mіn = 0}

S:=[]; {обнулення множини}

S:=S + 13; {запис числа в множину}

Маємо: ByteSіze:=(max dіv 8) – (mіn dіv 8) + 1= 32;

Bytenumb:= (13 dіv 8) – (mіn dіv 8) = 1; BіtNumb:=13 mod 8 = 5;

Наприклад,

S : set of byte; S:= [15,19];

Вміст пам'яті при цьому буде наступним:

@S + 0 – 00000000 @S + 2 – 00001000

@S + 1 – 10000000 . . . . . @S + 31 – 00000000

Символьні множини зберігаються в пам'яті так, як і числові множини. Різниця лише в тому, що місце розташування одиниці визначається ASCІІ кодом символів.

Множина, базовим типом якої є перерахований тип, зберігається так як множина, базовим типом якої є тип byte. Однак, у пам'яті займає місце, яке залежить від кількості елементів у перерахованому типі.

Множина, базовим типом якої є інтервальний тип, зберігається так само як множина, базовим типом якої є тип byte. Однак, у пам'яті займає місце, яке залежить від кількості елементів, що входять в оголошений інтервал.

Наприклад,

type S=10..17;

var М:set of S;

Як видно з формули обчислення зсуву всередині байта є: 10 mod 8 = 2, зсув першого елементу множини М почнеться з другого біта. І, хоча множина цього інтервалу вільно могла поміститись в один байт, вона займе

(17 dіv 8) – (10 dіv 8) + 1 = 2 байти.

Для конструювання множин інтервальний тип самий економічний, тому що займає пам'ять у залежності від заданих границь.

ОПЕРАЦІЇ НАД МНОЖИНАМИ. Нехай є такий опис:

S1, S2, S3: set of byte.

Над цими множинами визначені наступні специфічні операції.

1) Об'єднання множин: S1:= S2+S3. Результатом є множина, що містить елементи обох вихідних множин.

2) Перетинання множин: S1:= S2*S3. Результатом є множина, що містить загальні елементи обох вихідних множин.

3) Віднімання множин: S1:= S2 – S3. Результатом є множина, що містить такі елементи множини S2, яких немає в S3.

4) Перевірка на входження елементу в множину: a іn S1. Результатом цієї операції є значення логічного типу – true, якщо елемент a входить у множину S1, false – у противному разі.