lektsii_OP / T11

	ПЛАН
МНОЖИННІ ТИПИ ................................................................................................................................	1
Поняття множини................................................................................................................................	1
Створення множини...........................................................................................................................	2
Операції над множинами..................................................................................................................	3
Реалізація множин..............................................................................................................................	7

МНОЖИННІ ТИПИ

Поняття множини

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

Множина – це структура даних, що складається з будь-якої (нефіксованої) кількості однотипних компонент, які належать до значень певного базового типу. Тобто, множина представляє собою деяку підмножину значень заданого базового типу, включаючи порожню множину.

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

Значення множинного типу так само, як і масиви, будуються з декількох значень одного (базового) типу. Однак, на відміну від масивів, значення множинного типу може містити будь-яку кількість різних елементів базового типу - від нуля елементів (порожня множина) до всіх можливих його значень.

Кардинальне число множинного типу визначається автоматично і містить 2n варіантів, де n - потужність базового типу. Так на базі типу, що має три значення (A, B, C), можна побудувати 23 = 8 різних підмножин:

{[A,B,C], [A,B], [A,C], [B,C], [A], [B], [C], [ ]}.

Вони і є можливими значеннями множинного типу (множинами), побудованого на основі відповідного базового типу.

Множинні типи належать до дещо незвичних і порівняно рідко використовуваних структур мов програмування. Зокрема, в Pascal вони присутні, тоді, як у класичній мові С їх немає. Однак, у С++ в бібліотеці STL є так званий контейнер1 set, що реалізує концепцію множини елементів. Для того, щоб почати використання даної колекції, слід підключити до програми заголовний файл <set>.

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

1 Контейнери — це об'єкти STL, що зберігають інші елементи і реалізують механізми доступу до них. Кожен контейнер описується шаблонним класом, у якому реалізуються механізми доступу і функції для обробки елементів, що містяться у контейнері.

1

Створення множини

Формат опису множин залежить від синтаксису мови програмування. У Pascal він має наступний вид:

ідентифікатор_множини : set of базовий_тип.

Як базові типи при заданні множин можуть використовуватися тільки порядкові типи, потужність яких не перевищує 256 значень, а верхня і нижня їх межі не виходять із діапазону 0 255 (byte, char, перелічувані типи, а також обмежені типи, утворені з них). Найчастіше базовий тип задається як перелічуваний або обмежений. Наприклад,

type

digit = set of 0..9; var

w : set of char;

kl : set of ('A', 'B', 'C'); d : digit;

Ініціалізація множини у Pascal здійснюється шляхом присвоєння їй значення, РБНФнотація задання якого має вид:.

множина = “[ ]“ | “[“ значення ,, значення- “]“ значення = вираз| вираз .. вираз.

Тобто, окрім констант, як елементи множини, можна також використовувати й змінні множинного типу, вирази, діапазони значень. Наприклад,

d := [2, 3, 5, 9];
d1	:= [1, 2..50];
d2	:= [1, 3, k];	{ 1, 3, 10 }
d3	:= [k .. 2*k];	{ 10 .. 20 }
tl := ['A', 'B'];
t2 := ['a' ..'d', 'k'];
t := [ ];		{ пуста множина }

У С++ множина описується як контейнерний шаблон:

set <тип_компонент> ідентифікатор_множини.

Наприклад,

set<int> mySet;

Дане оголошення означає, що створюється об'єкт-множина з ім'ям mySet, елементи якої мають тип даних int. Оголошена таким чином множина є ще порожньою.

Як і інші структури даних, множини в С++ можна визначати. Для цього існує два основних способа:

set <T> m2(m);	// використовується конструктор копіювання
set <T> m1(begin, end);	// використовується конструктор з параметрами

де T - тип елементів множини; m, m1, m2 – множини; begin і end – початкове і кінцеве значення діапазона елементів.

2

Перша форма – це використання для ініціалізації множини конструктора2 копіювання. В результаті створюється множина m2, яка містить ті ж елементи, що і множина m. Друга форма - створює множину, яка містить елементи в діапазоні, заданому параметрами begin і end. Наприклад,

int data[5] = { 5, 11, 4, 27, 3 };
set<int> mySet (data, data+5);	// mySet містить значення 3, 4, 5, 11, 27

Слід зазначити, що особливістю множини set, як структури даних, є впорядкованість її унікальних елементів. Тому, незважаючи на те, що масив data містить послідовність елементів 5, 11, 4, 27, 3, множина mySet представляється послідовністю чи-

сел 3, 4, 5, 11, 27.

Який елемент видалити

Операції над множинами

Типовими діями при обробці множин є:

-додавання елемента в множину (виключаючи можливість дублювання);

-видалення елемента з множини;

-перевірка присутності у множині деякого елемента.

Реалізуються ці дії у мовах програмування, зазвичай, за допомогою вбудованих стандартних засобів (підпрограм).

Так для реалізації дій по включенню нового елемента в множину та видаленню елемента із множини у мові Pascal використовують стандартні процедури:

Include(mySet,elem) - додає значення elem в множину mySet; Exclude(mySet,elem) - видаляє значення elem з множини mySet.

Наприклад,

Include (mySet , 128);	{ додавання числа 128 у множину mySet }
Exclude (mySet , 23);	{ видаленняя числа 23 із множини mySet }

У С++ виконання цих дій здійснюється наступними методами контейнера (класу) set:

insert() - додає елемент в множину; erase() - видаляє елемент із множини.

При додаванні нового елемента в множину він відразу стає на своє місце так, щоб не порушувати порядок сортування.

Наприклад,

set<int> mySet;	// оголошення пустої множини цілих чисел mySet
for (int i=1; i<= 10; i++)
mySet.insert(i);	// додавання у mySet поточного числа
mySet .insert(4);	// нічого не відбудеться - значення 4 вже є в множині

2 Конструктор – це специфічний метод класу, що служить для ініціалізації даних цього класу

3

for (int i=2; i<= 10; i+= 2)
mySet.erase(i);	// видалення із множини mySet парних чисел

У даному прикладі спочатку формується множина mySet, яка містить десять перших натуральних чисел (перший цикл for). Власне додавання поточного елемента в множину здійснюється методом insert(). Наступний цикл for видаляє із сформованої множини парні елементи. Для видалення поточного елемента із множини служить метод erase().

Слід звернути увагу, що для правильного використання методів, треба викликати їх як функції-члени контейнера (у даному випадку - множини):

ідентифікатор_множини . виклик_метода.

Наприклад, mySet.insert(i) - виклик метода insert об'єкта-множини mySet.

Перевірка присутності деякого елемента у множині може здійснюватися у С++ за допомогою метода find().Якщо шуканий елемент знайдений у вказаній множині, то повертається ітератор3 (об'єкт-покажчик) на нього, інакше - ітератор кінця контейнера, який визначається методом end(). Наприклад,

set<int> mySet;	// оголошення пустої множини цілих чисел mySet
for (int i=1; i<= 10; i++)
mySet.insert(i);	// додавання у mySet поточного числа

int del;

cout << "\n Який елемент видалити? "; cin >> del;

if (mySet.find(del) != mySet.end() )

, cout <<"Елемент " << *mySet.find(del) << " - видалений!" << endl; mySet.erase(del); // видалення із множини mySet елемента del

}

else cout<<"Елемент відсутній \n";

В set немає поняття «індекс елементу». Тому єдиний спосіб переглянути дані, що містяться в множині, полягає у використанні так званих ітераторів. Ітератор є аналогом покажчика на елемент. Він використовується для проглядання контейнера в прямому або зворотному напрямі. Ітератор в бібліотеці STL відіграє таку ж роль, що й індекс елемента звичайного масиву. За допомогою індексу масиву можна отримати деякий елемент масиву, а за допомогою ітератора — деякий елемент контейнера. Основні методи для роботи з ітераторами наведені у табл. 1.

	Таблиця 1. Перелік основних методів для роботи з ітераторами
Назва	Опис
begin	повертає прямий ітератор, який вказує на початок колекції
end	повертає прямий ітератор, який вказує на кінець колекції (реально він вказує на уяв-
	ний неіснуючий елемент, наступний за останнім)
rbegin	повертає зворотний ітератор, який вказує на останній елемент колекції
rend	повертає зворотний ітератор, який вказує на початок колекції (позицію, що передує
	першому елементу)

3 Ітератори - це об'єкти-покажчики, які дозволяють перебрати всі елементи контейнера

4

У Pascal для перевірки присутності у множині деякого елемента служить операція входження in. Результатом її застосування є логічне значення true, якщо заданий елемент належить вказаній множині, і значення false в противному випадку. Наприклад,

2 in [1..10, 12]	=>	true
'M' in ['A'.. 'K']	=>	false

Операцію in часто використовують для скорочення запису громіздких умов. Так, наприклад, якщо потрібно перевірити, чи є буква голосною, то замість громіздкої умови

if (c='А') or (c='Е') or (c='І') or (c='О') or (c='U') or (c='У') then...

можна записати більш коротко:

if c in *'А', 'Е', 'І', 'О', 'U', 'У'+ then ...

Для множин визначені також операції відношення, які перевіряють рівність чи нерівність множин, а також, чи є одна множина підмножиною іншої. Співвідношення відповідних множинних операцій і їх математичних еквівалентів у Pascal і С++ наведені у табл. 2.

Таблиця 2. Співвідношення множинних операцій і їх математичних еквівалентів

	Математичний запис				Запис на Pascal	Запис на С++
		А = B			А = B	А = =B
		A	B		A <> B	A != B
		A	B		A < B	A < B
		A	B		A <= B	A <= B
		A	B		A > B	A > B
		A	B		A >= B	A >= B
Наприклад, у Pascal:
[1..3] = [1, 2]		=>		false
[1..3] >= [1, 2]		=>		true
[1..3] <= [1, 2]		=>		false
[1..3] <> [1, 2]		=>		true

Характерною особливістю множинного типу є можливісь визначення на ньому найбільш поширених теоретико-множинних операцій: об'єднання множин, їх перетину і різниці.

У Pascal ці специфічні операції визначені наступним чином:

-Об'єднання множин ( + ). Результатом є множина, що містить елементи, які входять до обох множин-операндів. Наприклад,

A:= [1, 2, 4, 5];	А	В
B:= [2, 5..8];
M:= A+B;	{ [1, 2, 4..8] }

Ця операція використовується також для включення елемента в множину. Наприклад,

mySet := mySet + [128];

{ додавання числа 128 у множину mySet }

5

-Перетин множин ( * ). Результатом є множина, що містить спільні елементи двох множин-операндів. Наприклад,

A:= [1, 2, 4, 5];	А	В
B:= [2, 5..8];
M:= A*B;	{ [ 2, 5] }

-Різниця множин ( ). Результатом є множина, що складається з елементів першої множини, які не входять у другу множину. Наприклад,

A:=[1, 2, 3];	А	В
B:= [2, 5, 6];
M:=A-B;	{ [1, 3] }

Ця операція використовується також для видалення елемента із множини. Наприклад,

mySet := mySet - [23];

{ видаленняя числа 23 із множини mySet }

У С++ для виконання теоретико-множинних операцій над елементами множин використовують глобальні алгоритми, як складові STL-бібліотеки. Вони визначені в заголовному файлі <algorithm>. Перелік основних алгоритмів для роботи з множинами наведений у табл. 3.

Таблиця 3. Перелік основних алгоритмів для роботи з множинами

Формат метода			Опис
set_union(first1, last1, first2, last2, first3)		Утворює упорядковане об'єднання множин,
		заданих діапазонами first1 last1 і first2 last2
set_intersection(first1, last1, first2, last2, first3)		Утворює упорядкований перетин множин, заданих
		діапазонами first1	last1 і first2	last2
set_difference(first1, last1, first2, last2, first3)		Утворює упорядковану різницю множин, заданих
		діапазонами first1	last1 і first2	last2
includes(first1, last1, first2, last2)		Повертає true, якщо всі об'єкти з діапазону first2
		last2 є також в діапазоні first1		last1

Тут first1, last1, first2, last2 - ітератори початків і кінців оброблюваних множин, first3 - ітератор, який вказує на місце відповідного контейнера, починаючи з якого потрібно записати результат.

Наприклад,

set<int> s1, s2, s3;
for (int	i=1; i<= 10; i++)
s1 .insert(i);		// ініціалізація множини s1
for (int	i=2; i<= 20; i+= 2)
s2 .insert(i);		// ініціалізація множини s2

set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));

У даному прикладі спочатку створюються множини s1 і s2, а потім як їх перетин методом set_intersection формується множина s3. Для створення ітератора вставки (останнього параметра у методі set_intersection) використовується метод inserter(), який як параметри приймає два аргумента: сам створюваний контейнер (s3) і ітератор, який вказує позицію, з якої повинна початися вставка в цей контейнер.

6

Слід зазначити, що у С++ до об'єктів-множин, як різновидів STL-контейнерів, можуть також застосовуватися інші, характерні для усіх контейнерів функції-члени. Основні із них наведені у таблиці 4.

			Таблиця 4. Перелік основних методів STL-колекцій
	Назва		Опис
	empty	визначає, чи є колекція порожньою
	size	визначає розмір колекції
	clear	видаляє всі елементи колекції
	erase	видаляє елемент або декілька елементів з колекції
Наприклад,
set<int> s;
for (int i=1; i<= 10; i++)
s .insert(i);			// ініціалізація множини
s.clear();			// очищення множини
if (s .empty.) cout<<”set empty”;			// перевірка пустоти множини

Мови програмування не завжди підтримують стандартні засоби виведення елементів множин. Зокрема, у Pascal для цього використовуються штучні прийоми. Наприклад,

for c:= 'A' to 'Z' do

if c in mySet then write(c: 2);

В С++ для виведення елементів контейнера, зокрема, множини, використовується метод copy(). Загалом даний метод призначений для копіювання заданого діапазона елементів у вказане місце. Його аргументами є три ітератора: перші два обмежують діапазон елементів, які підлягають копіюванню; третій - вказує на місце, куди треба скопіювати елементи. Якщо в якості третього аргумента вказати ітератор потока виведення ostream_iterator, то елементи контейнера виведуться на екран дісплея. Наприклад,

set<int> mySet;

for (int i=1; i<= 10; i++) mySet.insert(i);

copy (mySet.begin(),mySet.end(), ostream_iterator<int>(cout, " "));

У даному прикладі створюється і виводиться множина mySet, яка містить десять перших натуральних чисел. Для виведення результату використовується метод copy(). Виклик ostream_iterator<int>(cout, " ") створює ітератор для виведення змінних типу int в потік cout, роздільником в даному випадку визначений пробіл.

Реалізація множин

В мовах програмування множини реалізуються по-різному.

7

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

M, N : set of 0..9;	0	1	2	3	4	5	6	7	8	9
M := [2, 4, 5, 6, 8, 9];	0	0	1	0	1	1	1	0	1	1
N : = [ 1, 3, 5, 7, 9];	0	1	0	1	0	1	0	1	0	1

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

M, N : set of 0..9;	0	1	2	3	4	5	6	7	8	9
M := [2, 4, 5, 8, 9];	0	0	1	0	1	1	0	0	1	1
N : = [ 1, 3, 5, 7, 9];	0	1	0	1	0	1	0	1	0	1
M + N = [1, 2, 3, 4, 5, 7, 8, 9 ]	0	1	1	1	1	1	0	1	1	1
M * N = [5, 9 ]	0	0	0	0	0	1	0	0	0	1

ВС++ є дві різні реалізації множин:

-set, заснований на реалізації червоно-чорного дерева;

-unordered_set, заснований на хеш-таблицях.

Приклад. Визначити усі рядкові літери вхідного рядка і їх кількість. Реалізація даного прикладу на Pascal:

program mnoz;
var s : string;	{	рядок }
m : set of 'a'..'z';	{	множина рядкових літер }
i : word;	{	допоміжне ціле число }
c : char;	{	допоміжний символ }
begin
m := [ ];	{	створення пустої множини }
write(‘Enter string:	’);
readln (s);	{	введення рядка }
for i := 1 to length (s) do
if s [i] in ['a'..'z'] then m := m + [ s [i] ];				{ формування множини рядкових літер }
i:=0;
write ('Set: ');
for c := 'a' to 'z' do
if c in m then
begin
write (c:2);		{	виведення рядкових літер, наявних у множині }
i:=i+1;		{	визначення кількості елементів множини }
end;
writeln;
write ('Number elements of the set: ', i);				{ виведення кількості рядкових літер }
readln
end.

Реалізація даного прикладу на С++:

8

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main()
{ string s;	// створення пустого рядка
set<char> m;	// створення пустої множини символів
cout<<"Enter string: ";
getline(cin,s);	//введення рядка
for(int i = 1; i <= s.length(); i++)
if (islower(s[i])) m.insert(s[i]);	// формування множини рядкових літер
cout << "Set: ";
copy(m.begin(), m.end(), ostream_iterator<char>(cout, " "));		// виведення множини літер
int n = m.size();	// визначення кількості елементів множини
cout<<"\n Number elements of the set: "<<n<<endl;

system("pause");

}

Відеокопія результату роботи даної програми:

9