Міністерство освіти та науки України Національний університет «Львівська політехніка»
ЗВІТ З лабораторної роботи №3 З дисципліни: «Програмування ч.3 Структури і алгоритми» " Структура даних СТЕК" Варіант № 21 Варіант=(8+75)%21+1=21 Мета роботи Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. Завдання 2.1. Постановка задачі. Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку"(stack underflow) і "переповнення стеку" (stack overflow). Примітка: після реалізації стеку працювати з ним як з абстрактним типом даних, а не як з масивом. 21. Написати програму для послiдовного зберiгання трьох стекiв в масивi з N елементiв (стеки розміщуються в масиві рівномірно один за одним). На вході задаються пари цiлих чисел (i,j), де 1 ( і ( 3 , j ( 0. Число j>0 пари (i,j) додається в i-ий стек; число j<0 пари (i,j) не використовується, але один елемент вилучається зі стеку. Після обробки всієї заданої вхідної послідовності знайти в якому стеку сума всіх парних чисел буде найменьшою. 2.2. Алгоритм розв’язання задачі. Стек реалізований на масиві за допомогою класу під назвою Stack. Він містить поля – масив (власне стек), три змінних, які будуть вказувати на останній елемент масиву (перший елемент, який доданий до стеку) три змінні FULL типу bool для перевірки на заповнення стеку та три змінні типу bool EMPTY для перевірки пустоти стеку. Для перевірки в якому стеку найменша кількість парних чисел використовується допоміжна функція getElements(int), яка приймає номер стеку та повертає суму парних елементів. Після отримання трьох сум знаходимо мінімальне і виводимо на екран номер стеку. 3. Результати виконання програми.
4.Висновки: Ознайомився з фундаментальною абстрактною структурою даних стек. Набув практичних навичок побудови стеку, дослідив динаміку його вмісту та використав стек для розв'язання прикладних задач. 5. Додатки: #include "stdafx.h" #include <iostream> #include <string.h> #include <conio.h> using namespace std; class Stack { int data [60]; // стек int tos1, tos2, tos3; // індекс вершини public: Stack (); // конструктор void push (int, int); // додавання елементу void pop (int); // вилучення int top(int); // перегляд елементу в вершині void show(int); // вивід динаміки стеку int empty (int); // перевірка на елементи в стеку int getSize(int); // отримати розмір стеку bool FULL1, FULL2, FULL3; // логічна змінна переповнення bool EMPTY1, EMPTY2, EMPTY3; int getElements(int); }; Stack::Stack(){ tos1 = 0; tos2 = 20; tos3 = 40; FULL1 = false; FULL2 = false; FULL3 = false; EMPTY1 = true; EMPTY2 = true; EMPTY3 = true; } void Stack::push(int i, int s){ if (EMPTY1 && i == 1) EMPTY1 = false; if (EMPTY2 && i == 2) EMPTY2 = false; if (EMPTY3 && i == 3) EMPTY3 = false; if (FULL1 && i == 1) throw "Steck overflow exception"; if (FULL2 && i == 2) throw "Steck overflow exception"; if (FULL3 && i == 3) throw "Steck overflow exception"; cout << "push: " << s << endl; if (i == 1){ data[tos1] = s; tos1++; if (tos1 == 19) FULL1 = true; } if (i == 2){ data[tos2] = s; tos2++; if (tos2 == 39) FULL2 = true; } if (i == 3){ data[tos3] = s; tos3++; if (tos3 == 59) FULL3 = true; } } int Stack::top(int i){ if (i == 1) return data[tos1-1]; if (i == 2) return data[tos2-1]; if (i == 3) return data[tos3-1]; } void Stack::pop(int i){ if (i == 1){ if (tos1 == 0) throw "Steck underflow exception"; cout << "pop - " << data[tos1-1] << endl; if (tos1 == 19) FULL1 = false; tos1--; if (tos1 == 0) EMPTY1 = true; } if (i == 2){ if (tos2 == 20) throw "Steck underflow exception"; cout << "pop - " << data[tos2-1] << endl; if (tos2 == 39) FULL2 = false; tos2--; if (tos2 == 0) EMPTY2 = true; } if (i == 3){ if (tos3 == 40) throw "Steck underflow exception"; cout << "pop - " << data[tos3-1] << endl; if (tos3 == 59) FULL3 = false; tos3--; if (tos3 == 0) EMPTY3 = true; } } void Stack::show(int i){ if (i == 1){ int i=0; while (i<tos1){ cout << data[i] << " "; i++; } cout << endl; } if (i == 2){ int i=20; while (i<tos2){ cout << data[i] << " "; i++; } cout << endl; } if (i == 3){ int i=40; while (i<tos3){ cout << data[i] << " "; i++; } cout << endl; } } int Stack::getSize(int i){ if (i == 1) return tos1; if (i == 2) return tos2; if (i == 3) return tos3; } int Stack::getElements(int i){ int sum1=0, sum2=0, sum3=0; if (i == 1){ for (int i=0; i<tos1; i++){ if (data[i]%2 == 0) sum1++; } return sum1; } if (i == 2){ for (int i=20; i<tos2; i++){ if (data[i]%2 == 0) sum2++; } return sum2; } if (i == 3){ for (int i=40; i<tos3; i++){ if (data[i]%2 == 0) sum3++; } return sum3; } } int _tmain(int argc, _TCHAR* argv[]) { int i, j; Stack s; while (true){ cout << "enter i, j (j==0 - exit): "; cin >> i >> j; if (j != 0){ try{ if (j>0) s.push(i,j); else s.pop(i); } catch (char* ex){ cout << ex << endl; } } if (j == 0) break; } s.show(1); s.show(2); s.show(3); int s1 = s.getElements(1); int s2 = s.getElements(2); int s3 = s.getElements(3); int min = s1, num = 1; if (s2<s1){ min = s2; num = 2; } if (s3<min){ min = s3; num = 3; } cout << "min sum is in stack number " << num << endl; _getch(); return 0; }