МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» ІНСТИТУТ КОМП’ЮТЕРНОЇ ТЕХНІКИ АВТОМАТИКИ ТА МЕТРОЛОГІЇ Кафедра ЕОМ ЗВІТ ЛАБОРАТОРНОЇ РОБОТИ №4 З ПРЕДМЕТУ: «Програмування. Частина III. Структури даних та алгоритми» ТЕМА: «Структура даних ЧЕРГА» ВИБІР ВАРІАНТУ: № варіанта = (17+101)%30+1=29 Львів – 2011 Мета роботи. Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. Постановка задачі. Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (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). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. 29. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності знайти три найбільших елемента черги. Алгоритм розв’язання задачі. Цей алгоритм був реалізований у програмі, в якій спочатку підключаються потрібні для виконання програми бібліотеки. Потім написала код програми для організації введення елементів масиву, додатні з яких будуть додавати дані в чергу, а від’ємні – віднімати. Також написала код програми для знаходження трьох найбільших елементів черги. Динаміка вмісту черги  K P  0)       - порожня черга      P K   P K   P K  1) 1       2)        3)  3         P K   P K   P K  4)  3 4     5)   4     6)   4  6       P K      7)   4 6 7     Результати виконання програми. / Висновки. Виконав[ім’я автора приховано] для розв'язання прикладних задач. Додатки. #include<stdio.h> #include<conio.h> #include<math.h> #define n 5 class Queue { private: int qu[n]; public: int k,l; Queue(){k=-1; for(int i=0;i<n;i++) qu[i]=0; l=0;} ~Queue(){}; Queue(Queue &Queue){}; void push(int a) {int q=0; if (k<n-1) { k++; qu[k]=a; }else{ printf("\nQueue overflow\n"); for(int i=0;i<n;i++){ qu[i]=qu[i+l]; } k=k-l+1; l=0; qu[k]=a; } } void pop() { if (l<=k){ qu[l]=0; l++; } else printf("\nQueue underflow\n"); } int front() { return qu[l]; } bool empty() { return (k<l); } bool full() { return ((k>l)); } void print() { for(int i=0;i<n;i++) printf("%d ",qu[i]); printf("\n"); for(int i=0;i<l;i++) { printf(" "); } printf("p "); if(k!=l){ for(int i=l+1;i<k;i++) { printf(" "); } printf("k\n"); }else printf("\n"); } } ; void main() { Queue q1; int k; int z; int p=0; printf("Vvtdit rozmir masuvu \n"); scanf("%d", &k); int g[20]={0}; printf("Vvtdit elementu masuvu \n"); for (int i=0;i<k;i++){ scanf("%d",&g[i]);} for (int i=0;i<k;i++){ if (g[i]>0) q1.push(g[i]); else if (g[i]<0) q1.pop(); q1.print(); p=p+1; } int a[10]={0},j=0, max=0; while (!(q1.empty())) { z=q1.front(); a[j]=z; j++; q1.pop(); } for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf("%d",a[max]); a[max]=0; for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf(" %d",a[max]); a[max]=0; for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf(" %d",a[max]); getch(); }