Завдання на практичну роботу

Варіант 1. Створити клас Lstack – стек, що базується на структурі односпрямованого списку.

Варіант 2. Створити клас Lstack2 – стек, що базується на структурі двоспрямованого списку.

Тип елементу структури обрати самостійно. Передбачити функції класу для виконання наступних операцій (табл.3.1).

Таблиця 3.1 – Основні операції над стеком

Операція	Опис
рush()	занести у стек задане значення
pop()	добути і вилучити значення із вершини стека
print()	вивести усі значення стека на екран
num()	повернути кількість значень, що знаходяться у стеку
isempty()	повернути значення true (тип bool), якщо стек порожний

Варіант 3. Створити клас Lqueue – черга, що базується на структурі односпрямованого списку.

Варіант 4. Створити клас Lqueue2 – черга, що базується на структурі двоспрямованого списку.

Тип елементу структури обрати самостійно. Передбачити функції для виконання наступних операцій (табл.3.2).

Таблиця 3.2 – Основні операції над чергою

Операція	Опис
аdd()	занести у кінець черги задане значення
del()	добути і вилучити значення із початку черги
print()	вивести усі значення, що знаходяться у черзі, на екран
num()	повернути кількість значень, що знаходяться у черзі
isempty()	повернути значення true (тип bool), якщо черга порожня

Контрольні запитання

1. Що таке стек?

2. Що таке черга?

3. Представлення в пам’яті стеків та черг.

4. Яким чином задаються черга та стек на мові С++?

5. Які основні операції виконуються над такими структурами даних як стек та черга?

6. Переваги та недоліки різного представлення в пам’яті структур даних стек та черга.

7. Використання структур даних стек та черга для розв’язання задач.

Практична робота №4 Множини

Мета роботи

Сформувати практичні навики організації такої структури як множини та їх використання при розв’язанні задач.

Основні теоретичні відомості

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

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

Приклад. Програмна реалізація множини у вигляді лінійного двоспрямованого списку.

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}.