Основні теоретичні відомості. Множина – одне з основних понять сучасної математики
Множина – одне з основних понять сучасної математики. Строго воно не визначається, але може бути дано інтуітивне визначення множини як сукупності певних і різних об'єктів довільної природи, яка розглядається як одне ціле. Об'єкти, які складають множину, називаються її елементами. Наприклад, можна говорити про множину усіх книг в певній бібліотеці, множину літер українського алфавіту або про множину всіх коренів певного рівняння тощо.
На мові С++ множина може бути представлена у вигляді двоспрямованого списку.
Приклад. Програмна реалізація множини у вигляді лінійного двоспрямованого списку.
class Node
{ public:
char d; // дані
Node *next; // покажчик на наступний вузол
Node *prev; // покажчик на попередній вузол
Node (char dat = 0) {d = dat; next = 0; prev = 0;} // конструктор
};
class Set
{ Node *pbeg, *pend; // покажчики на початок та кінець множини
public:
Set() { pbeg = 0; pend = 0; }// конструктор
~Set();// деструктор
void include(char d); // додавання елемента в кінець множини
Node *find(char d); //пошук заданого елемента
bool exclude(char key); // видалення елементів множини
int power(); // потужність множини
void print();// друк множини
};
Розглянемо реалізацію методів класу. Метод include – додавання елемента до множини. Метод find – пошук заданого елементу. Множина не може містити двох однакових елементів. Це треба враховувати при доповненні множини новими елементами.
Node * Set::find(char d)
{ Node *pv = pbeg;
while(pv) { if(pv->d == d) { break;} pv = pv->next; }
return pv;}
void Set::include(char d)
{ if(Node *key=find(d)) return; // пошук вузла key, якщо є, то 0
Node *pv = new Node(d);
if(!pbeg) { pbeg = pend = pv; }
else { pv->prev = pend; pend->next = pv; pend = pv; }
}
Метод exclude – видалення елементів множини виконується аналогічно видаленню елементів списку:
bool Set::exclude(char key)
{ if(Node *pkey = find(key))
{ if(pbeg == pkey) // видалення з початку множини
{pbeg = pbeg->next; pbeg->prev = 0;}
else if(pkey == pend) // видалення з кінця множини
{pend = pend->prev; pend->next = 0;}
else // видалення з середини множини
{(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev; }
delete pkey;
return true;}
return false;
}
Кількість елементів множини називають її потужністю. Всі множини мають визначену кількість елементів. Порожня множина має нуль елементів. Поняття потужності множин стає важливим в контексті встановлення відношень між множинами. Взаємооднозначне відношення між двома множинами можливо встановити лише коли кількість їхніх елементів співпадає. Метод power – визначення потужності множини:
Методи power та друку print множини поелементо переглядають множину переходячи по відповідним посиланням:
int Set::power()
{ int p=0;
Node *pv = pbeg;
while(pv) { p++; pv = pv->next;}
return p;
}
void Set::print()
{ Node *pv = pbeg;
cout << endl << " Set: ";
while(pv) {cout << pv->d << " "; pv = pv->next;}
cout << endl;}
Деструктор множини звільняє пам'ять з-під усіх елементів множини:
Set::~Set()
{ if(pbeg) {Node *pv = pbeg;
while(pv) {pv = pv->next; delete pbeg; pbeg = pv; }
}
}
Нижче наведений приклад програми, що використовує клас Set. Програма формує множину рядку 'BETA', друкує його на екран та вираховує потужність множини; додає елементи 'A', 'T', 'X' до множини, друкує її та вираховує потужність множини; видаляє елемент 'T', друкує множину та вираховує потужність множини.
void main()
{ Set S;
S.include('B');
S.include('E');
S.include('T');
S.include('A');
S.print();
cout<<" Power of set="<<S.power();
S.include('A');
S.include('T');
S.include('X');
S.print();
cout<<" Power of set="<<S.power();
if(!S.exclude('T')) {cout << "element not found"<< endl;}
S.print();
cout<<" Power of set="<<S.power();
getch();}
Над множинами можна виконувати наступні операції:
– різниця множин А та B є множина елементів, які належать множині А, але не належать множині В;
– об'єднанням множин А та B називається множина, яка складається з усіх тих елементів, які належать хоча б одній з множин A, B;
– перетином множин А та B називається множина, яка складається з усіх тих елементів, які належать кожній із множин А, B;
– симетрична різниця множин A та B є така множина елементів, які містяться в одній з цих двох множин, але не в обох. Наприклад, симетрична різниця множин {1,2,3} та {3,4} є {1,2,4}.