6. Структуровані типи даних. Множини
Множина – це структурований тип даних, елементами якого є всі підмножини, побудовані на основі елементів базового типу.
Наприклад,
множина, базовими для якої є елементи
,
складається з підмножин
,
де
– порожня множина.
Всі
підмножини множини різні й невпорядковані,
тому підмножини
і
– еквівалентні. Кількість елементів
базового типу, на основі якого конструюється
множинний тип, називається потужністю
і не може перевищувати
.
У програмі опис множини має вигляд
<ім’я типу> = set of <базовий тип>;
де <ім’я типу> – ідентифікатор, set, of – зарезервовані слова (множина, із), <базовий тип> – будь-який порядковий тип крім Word, Integer, LongInt.
Множина будується конструктором. Конструктор – це список сталих, виразів, типів-діапазон базового типу, взятих у квадратні дужки. Наприклад,
Type Ts = set of char;
Var s: Ts;
s1: set of 0..9;
s:= [‘a’..’z’]; {множина всіх підмножин із малих латинських літер}
s1:= [1..3, 7, 9]; {множина всіх підмножин із цифр 1,2,3,7,9}
Над множинами визначені такі операції:
– перевірка
еквівалентності; результат
,
якщо множини еквівалентні, інакше
;
– перевірка
нееквівалентності; результат
,
якщо множини нееквівалентні, інакше
;
–
перевірка
входження; результат
,
якщо множина
включає множину
,
інакше
;
– перевірка
входження; результат
,
якщо множина
включає множину
,
інакше
;
– перевірка
належності; результат
,
якщо елемент
міститься у множині
,
інакше
;
– перетин
множин; результат – множина спільних
елементів
і
;
– об’єднання
множин; результат – множина елементів
доповнена тими елементами
,
яких немає в
;
– різниця
множин; результат – множина елементів
,
яких немає в
.
Окрім
зазначених операцій можна використовувати
процедуру
– добавити елемент
у множину S
та процедуру
– вилучити елемент
із множини S.
Приклад. Задано натуральне число . Розробити програму, яка друкує у зростаючому порядку всі цифри, які входять в це число, які не входять в це число і які входять в це число більше одного разу.
Для побудови згаданих множин виділяємо цифри у заданому числі. Для цього послідовно ділимо це число за модулем 10 (операція mod) і ділимо націло на 10 (операція div). Остачі від ділення за модулем 10 є цифрами цього числа. Добавляємо ці цифри у множину s1. Якщо така цифра вже є в множині s1, то добавляємо її у множину s3 – цифр, що повторюються. Множину s2 – цифр, яких немає в числі, одержимо як різницю множини-сталої c – всіх цифр і множини s1.
Для реалізації описаного алгоритму командою File|New Application створимо новий проект.
Рис. 6.1 Форма Пошук цифр
Присвоїмо формі заголовок Пошук цифр (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB6_1.pas, а проект – PLAB6_1.dpr.
Розробимо форму для введення початкових даних і виведення результату Рис.6.1.
Для введення початкових даних і виведення результату розмістимо на формі чотири компоненти Edit.
Крім цього, розмістимо на формі дві керуючі кнопки (компонент Button) з написами Обчислити, Вихід.
Обробник кнопки Обчислити міститься у програмному модулі ULAB6_1 і має вигляд:
Unit ULAB6_1;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
{Обробник кнопки Обчислити}
procedure TForm1.Button1Click(Sender: TObject);
Const c=[0..9];
Var n, i, k: integer;
s1, s2, s3: set of 0..9;
begin
{Введення початкових даних}
n:=StrToInt(Edit1.Text);
s1:=[]; {Множина цифр, які є в числі}
s2:=[]; {Множина цифр, яких немає в числі}
s3:=[]; {Множина цифр, які є в числі і повторюються}
i:=n;
while i<>0 do
begin
k:=i mod 10;
if k in s1 then s3:=s3+[k] else s1:=s1+[k];
i:=i div 10;
end;
s2:=c-s1;
{Виведення результату}
Edit2.Text:=''; Edit3.Text:=''; Edit4.Text:='';
{ Цифри, які є в числі }
for i:=0 to 9 do
if i in s1 then Edit2.Text:=Edit2.Text+IntToStr(i)+' ';
{ Цифр, яких немає в числі }
for i:=0 to 9 do
if i in s2 then Edit3.Text:=Edit3.Text+IntToStr(i)+' ';
{Цифри, що повторюються}
for i:=0 to 9 do
if i in s3 then Edit4.Text:=Edit4.Text+IntToStr(i)+' ';
end;