МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 4 Структура даних Черга 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. 2 Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати дек, в якому до опису деку додано дві функції commute_left та commute_right, які заміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції додавання в лівому або в правому кінці деку опиниться число більше за 50, то треба зменшити його значення на 10. Після обробки всієї заданої вхідної послідовності перевірити, чи буде дек “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.). ). 3 Алгоритм роз’вязку задачі: Дек організовуємо у вигляді класу. Це дає можливість працювати з усіма типами даних. Спочатку по черзі вносимо елементи. Дані вносяться в дек з права якщо елемент додатній та парний і вносяться з ліва якщо елемент не парний, а якщо елемент від’ємний парний то він робить оперекію pop з права, не парний то з ліва . 4. Динаміка вмісту деку: Внесення в основний дек вхідних даних(п – правий край, л – лівий край) 1)push_left(5) 5           2)push_left (9) 9 5          3)push_right(14) 9 5 14         4)push_right (54); 9 5 14 44        5)push_left (63) 53 9 5 14 44       6) push_right (4) 53 9 5 14 44 4      7)pop_left (-3) 9 5 14 44 4       8)push_left (5) 5 9 5 14 44 4      9)pop_right (-6) 5 9 5 14 44       10)push_left (5) 5 5 9 5 14 44       Перевірка на дзеркальність: 5≠44 5≠14 9≠5 Отже дек не дзеркальний. If (top-left()==top.right()) Pop_left(); pop_right(); 5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась з cтруктурою даних черга. А саме із різновидом черги – дек. Дослідила принципи і методи роботи з чергою та деком. Додатки: #include <stdio.h> #include <iostream> #include <conio.h> using namespace std; class deq{ private: int left,right; int count; int *items; int Capacity; public: deq(int n){ Capacity = n; items = new int[Capacity]; count = 0; left = Capacity / 2; right = left - 1; } ~deq(){delete[] items;} void push_right(int it){ if (count < Capacity){ if(right == Capacity - 1 ){ for (int i = left - 1; i < right; i++) items[i]=items[i + 1]; items[right] = it; left--; } else items[++right] = it; count++; } } void push_left(int it){ if (count < Capacity){ if(left == 0){ for (int i = right + 1; i > 0; i--) items[i] = items[i - 1]; items[left] = it; right++; } else items[--left] = it; count++; } } int size(){return count;} bool empty(){return (count == 0);} int front_left(){if (!empty())return items[left];} int front_right(){if(!empty())return items[right];} void pop_left(){ if(!empty()){ left++; count--; } } void pop_right(){ if(!empty()) right--; count--; } void print(){ cout << "deq:"; if(!empty()){ for(int i = left; i <= right; i++) cout << items[i] << " "; if (count == Capacity) cout << "size:full" << endl; else cout << "size:" << count << endl; } else cout << " empty" << endl; } void dzerkalo(){ int k,p=0; if(Capacity%2==1) k=(Capacity-1)/2; else k=Capacity/2; for(int i=0;i<k;i++){ if(this->front_left()==this->front_right()) p++; this->pop_right(); this->pop_left(); } if(p==k) cout<<"TaK!"; } }; int main(){ puts("Vvedit' Dek:"); deq* n=new deq(10); int a; for(int i=0;i<10;i++){ cin>>a; if(a%2==0){ if(a>0){ if(a>50) a=a-10; n->push_right(a);} else n->pop_right(); } else{ if(a>0){ if(a>50) a=a-10; n->push_left(a); } else n->pop_left(); } n->print(); } n->dzerkalo(); getch(); return 0; }