Мiнiстерство освiти і науки, молоді та спорту України Національний університет «Львівська політехніка» Кафедра ЕОМ Звіт з лабораторної роботи № 4 з дисципліни: «Програмування. Частина III. Структури даних та алгоритми» на тему: «Структура даних ЧЕРГА» Варіант № : (8+114) % 30 + 1 = 3 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (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). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа. Алгоритм розв’язання задачі: Аналізую чергу, яка задана завданням Створюю клас queue і наповнюю його інтерфейс. Описую методи push, pop, top, empty, show,full, wipe_out та конструктор. Під`єднуюю заголовочний файл q.h до stdafx.h, де зберігаються всі заготовочні файли. Заповнюю файл main.cpp, яка демонструє роботу моєї черги як абстрактної структури. Динаміка вмісту черги під час обробки введеної послідовності Позначимо: P – початок черги; К – кінець черги. Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності змінити порядок слідування елементів в деку на протилежний. 1) K P         порожня черга    2) P K   5      push(5)     3) P K   5 4     push(4)    4) P K   5 4 3    push(3)    5) P K   5 4 3 1   push(1)    6) P K   5 4 3 1 2   push(2)    7) P K   5 4 3 1 2  pop()    8) P K   5 4 3 1 2 2 push(2)    9) P K   5 4 3 1 2 2 3 push(3)     Результати виконання програми: Висновок: На лабораторній роботі я досліджував абстрактну структуру даних: чергу. Набув практичних навичок побудови черги, досліджував динаміку його вмісту та розв’язав задачу Додатки: #include<iostream> #include<conio.h> using namespace std; #define n 10 class Deque{ int a[n],l,r; public: Deque(){ for(int i=0;i<n;i++){ a[i]=0; } l=1; r=0; } virtual~Deque(){} bool Empty(){if(r<l) return true; return false;} bool Full(){if(r==n-1) return true; return false;} void Push(int x){ if(r+1>=n){cout<<"Deque is overload";} else {r=r+1; a[r]=x;} } void Pop_left(){ if(l+1>n){cout<<"Deque is overflow\n"; } else l=l+1; } void Pop_right(){ if(r-1<0){cout<<"Deque is overflow";} else r=r-1;} int Front_left(){return a[l];} int Front_right(){return a[r];} void Func(){ int buf[n], len; len=r-l+1; int k=0; for(int i=0;i<len;i++){ buf[i]=Front_right(); Pop_right(); } Deque(); for(int i=0;i<len;i++){ Push(buf[i]); } } void Print(){ for(int i=l;i<r+1;i++){ cout<<a[i]<<"\t"; } cout<<"\nleft="<<l; cout<<"\nright="<<r<<endl; } }; int main(void){ int v=(8+'r')%30+1; cout<<"Variant - "<<v<<endl; /*Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності змінити порядок слідування елементів в деку на протилежний.*/ Deque obj1; int arr[10]={1,2,-3,4,5,-6,7,8,-9,10}; cout<<"Vhidniy masiv:\n"; for(int i=0;i<n;i++){ cout<<arr[i]<<"\t"; } cout<<endl; for(int i=0;i<sizeof(arr)/sizeof(int);i++){ if(arr[i]>=0){ obj1.Push(arr[i]); obj1.Print(); } if(arr[i]<0){ if(arr[i]%2==1){obj1.Pop_left(); obj1.Print();} else obj1.Pop_right(); obj1.Print(); } } obj1.Func(); cout<<"\nPisla obrobki:\n"; obj1.Print(); getch(); return 0; }