Тема 7. Множини

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

Наприклад, множина, базовими для якої є елементи , складається з підмножин

,

де – порожня множина.

Всі елементи множини різні й невпорядковані, тому множини і – еквівалентні. Кількість елементів базового типу, на основі якого конструюється множинний тип, називається потужністю і не може перевищувати .

У програмі опис множини має вигляд

<ім’я типу> = set of <базовий тип>;

де <ім’я типу> – ідентифікатор, set, of – зарезервовані слова (множина, із), <базовий тип> – будь-який порядковий тип значення якого не перевищують 256.

У програмі множину можна описати за допомогою ідентифікатора типу або безпосередньо у розділі Var. Наприклад,

Type Tmn = set of char;

Var s1: Tmn;

s2: set of 0..9;

де множина символів s1 описана за допомогою ідентифікатора типу Tmn, а множина цифр s2 безпосередньо у розділі Var.

Існує також множина константа. Множина константа може бути типізованою або нетипізованою. Наприклад,

Const Mt:set of char=[‘a’.. ‘z’];

Mn=[0.. 9];

де Mt типізована множина константа із малих латинських літер, а Mn нетипізована множина константа із цифр.

Множина будується за допомогою конструктора. Конструктор – це список сталих, виразів, типів-діапазон базового типу, взятих у квадратні дужки. Наприклад,

Var S1:set of char;

S2: set of 0..9;

Begin

.................

S1:=[‘a’..’z’]; {множина всіх підмножин із малих латинських літер}

S2:= [1..3, 7, 9]; {множина всіх підмножин із цифр 1,2,3,7,9}.

End.

Над множинами визначені такі операції:

· – перевірка еквівалентності,

результат=

· – перевірка нееквівалентності,

результат=

· – перевірка входження,

результат=

· – перевірка входження,

результат=

· – перевірка належності,

результат=

· – об’єднання множин Рис.6.1. а),

результат=

· – переріз множин Рис.6.1. б),

результат=

· – різниця множин Рис.6.1. в),

результат=

А + В А * В А - В

а) б) в)

Рис. 6.1. а) ­– об’єднання множин, б) – переріз множин,

в) – різниця множин.

Окрім, зазначених операцій можна використовувати процедуру – добавити елемент у множину S та процедуру – вилучити елемент із множини S.

Звернення до множини можливе тільки в цілому, до конкретного базового елемента множини звернутися неможливо.

При введенні базових елементів множини використовується допоміжна змінна базового тип . Значення базового елемента вводиться і присвоюється допоміжній змінній , а потім змінна за допомогою процедури або операції об’єднання добавляється до множини. Наприклад,

Var S: set of byte;

i, k: bye;

begin

S:=[]; {очистка множини}

.............

for i:=0 to 3 do

begin

x:=StrToInt(Memo1.Lines[i]);

S:=S+[x];

або

Include(S,x);

end;

.............

end.

Якщо Memo1 мстить числа 2, 5, 4, 9, то буде створена множина із базових елементів {2, 5, 4, 9}.

Для виведення базових елементів множини потрібно перебрати всі значення базового типу і перевірити чи це значення належить множині. Якщо значення належить множині, то його слід вивести. Наприклад, виведемо базові елементи множини S із попереднього прикладу. Оскільки базовий тип byte приймає значення від 0 до 255, то і також буде змінюватися від 0 до 255

for i:=0 to 255 do

if i in S then

Memo1.Lines.Add(IntToStr(i));

В результаті будуть виведені за зростанням всі базові елементи множини S – 2, 4, 5, 9.