Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 4 на тему: "Структура даних ЧЕРГА " з дисципліни: " Програмування. Частина III. Структуриданих та алгоритми " Вибір індивідуального завдання: №варіанта=(11+97)%30+1=19 Львів – 2012 МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудовичерги, дослідження динаміки його вмісту та використання черг для розв'язання прикладних задач. ПОСТАНОВКА ЗАДАЧІ Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow). 19. Змоделювати дек, в якому до опису деку додано функцію change, яка міняє значення елементів, що знаходяться в лівому та в правому кінцях деку. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба обміняти значення лівого і правого кінців деку. Після обробки всієї заданої вхідної послідовності знайти суму парних чисел деку.   ДИНАМІКА ВМІСТУ ЧЕРГИ Послідовність K цілих (додатніх, від'ємних, нульових, парних і непарних) чисел Моя послідовність: 1 2 3 4 5 -1 0 3 4 5 2 1 Схематичне зображення черги після обробки кожного числа з вхідної послідовності Введемо такі позначення: П – покажчик початку черги, К – покажчик кінця черги К П            -queue(); П К 1            -push_left(1); П К 1 2           - push_right(2); П К 3 1 2          - push_left(3); П К 3 1 2 4         - push_right(4); П К 5 3 1 2 4        - push_left(5); П К 3 1 2 4        - pop(); П К 4 1 2 3        - change(); П К 3 4 1 2 3       - push_left(3); П К 3 4 1 2 3 4      - push_right(4); П К 5 3 4 1 2 3 4     - push_left(5); П К 5 3 4 1 2 3 4 2    - push_right(2); П К 1 5 3 4 1 2 3 4 2   - push_left(1); Визначити суму парних елементів деку. Сума парних елементів деку рівна 12. АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ Створюємо клас queue1.h Під час реалізації програми вводимо послідовність чисел. Якщо число непарне, то вводимо в ліву сторону черги, якщо парне – в праву. При вводі від’ємного числа ми вилучаємо 1-й елемент черги. При вводі 0, ми міняємо лівий і правий елемент місцями. Виводимо результуючу чергу. Виводимо суму парних чисел. Завершуємо роботу програми. РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАММИ Скріншот 1: Меню програми.
Скріншот 2: Ввід натуральних чисел.
Скріншот 3: Вивід результуючої черги.
Скріншот 4: Сума парних чисел.
ВИСНОВКИ На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних – чергу. Набувпрактичних навичок побудови черги та провів дослідження динаміки її вмісту. ДОДАТКИ queue1.h #ifndef MAIN_SAVITCH_QUEUE1_H #define MAIN_SAVITCH_QUEUE1_H #include <cstdlib> // Provides size_t #include <cassert> // Надає макрос assert. #include <conio.h> #include <iostream> namespace main_savitch_8B { template <class Item> class queue { public: // ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ typedef std::size_t size_type; typedef Item value_type; static const size_type CAPACITY = 30; // КОНСТРУКТОР queue( ){ count = 0; first = 0; last = CAPACITY/2; }; // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void pop_left( ) { assert(!empty( )); first = next_index(first); --count; }; void pop_right() { assert(!empty( )); last = prev_index(last); --count; } void push_right(const Item& entry) { assert(size( ) < CAPACITY); last = next_index(last); data[last] = entry; ++count; }; void push_left(const Item& entry) { assert(size( ) < CAPACITY); first = prev_index(first); data[first] = entry; ++count; } void dynam() { if(!empty()) for (int i=first; i<=last; i++) cout << "| " << data[i] << " |"; }; void commute_left(const Item& entry) { if(data[first]<10) { cout << "Елемент " << data[first] << " замiнено на - " << entry; assert(size( ) < CAPACITY); data[first] = entry; ++count; } else cout << "Елемент не є < 10"; }; void commute_right(const Item& entry) { if(data[last]<10) { cout << "Елемент " << data[last] << " замiнено на - " << entry; assert(size( ) < CAPACITY); data[last] = entry; ++count; } else cout << "Елемент не є < 10"; }; void change() { Item x=data[last]; data[last]=data[first]; data[first]=x; }; // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty( ) const { return (count == 0); } Item front_left( ) const { assert(!empty( )); return data[first]; }; Item front_right( ) const { assert(!empty( )); return data[last]; }; size_type size( ) const { return count; } private: Item data[CAPACITY]; size_type first; size_type last; size_type count; // ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ size_type next_index(size_type i) const { return (i+1) % CAPACITY; } size_type prev_index(size_type i) const { return (i-1) % CAPACITY; } }; } #endif main.cpp #include <iostream> #include "queue1.h" #include <conio.h> using namespace std; using namespace main_savitch_8B; int main() { queue<int> s; char v; int x=1; system("color 0f"); setlocale(LC_CTYPE,"Ukrainian"); do{ cout << "Команди роботи:" << endl; cout << " " << "1. Push(x)." << endl; cout << " " << "2. Pop_right()." << endl; cout << " " << "3. Pop_left()." << endl; cout << " " << "4. Автоматичний показ роботи деку." << endl; cout << " " << "5. Iндивiдуальне завдання(сума парних елементiв)." << endl; cout << " " << "6. Вихiд." << endl << endl; if (x==0) cout << "Крайнi елементи помiнянi мiсцями." << endl; s.dynam(); cout << endl << endl; v=getch(); system("cls"); if (v=='6') return 0; else if (v=='1'){ cout << "Введiть x - "; cin >> x; if(x<0){ if (x%2==0) s.pop_right(); else s.pop_left(); } else if (x>0) { if (x%2==0) s.push_right(x); else s.push_left(x); } else s.change(); system("cls"); } else if (v=='2'){ s.pop_right(); system("cls"); } else if (v=='3'){ s.pop_left(); system("cls"); } else if (v=='4'){ queue<int> a; cout << "push(1) - " << endl; a.push_left(1); a.dynam(); cout << endl << endl << "push(2) - " << endl; a.push_right(2); a.dynam(); cout << endl << endl << "push(3) - " << endl; a.push_left(3); a.dynam(); cout << endl << endl << "push(4) - " << endl; a.push_right(4); a.dynam(); cout << endl << endl << "push(5) - " << endl; a.push_left(5); a.dynam(); cout << endl << endl << "push(6) - " << endl; a.push_right(6); a.dynam(); cout << endl << endl << "push(7) - " << endl; a.push_left(7); a.dynam(); cout << endl << endl << "s.pront_left() - " << a.front_left(); cout << endl << "s.pront_right() - " << a.front_right() << endl; cout << endl << endl << "push(-8) - " << endl; a.pop_right(); a.dynam(); cout << endl << endl << "push(-9) - " << endl; a.pop_left(); a.dynam(); cout << endl << endl << "push(10) - " << endl; a.push_right(10); a.dynam(); cout << endl << endl << "pop_right() - " << endl; a.pop_right(); a.dynam(); cout << endl << endl << "pop_left() - " << endl; a.pop_left(); a.dynam(); cout << endl << endl << "push(11) - " << endl; a.push_left(11); a.dynam(); cout << endl << endl << "push(12) - " << endl; a.push_right(12); a.dynam(); cout << endl << endl << "Дек до змiн:" << endl; a.dynam(); cout << endl << "Дек пiсля обертання:" << endl; a.change(); a.dynam(); queue<int> b; int sum=0; while (!a.empty()){ x=a.front_left(); a.pop_left(); b.push_right(x); if(x%2==0) sum=sum+x; } while (!b.empty()){ x=b.front_right(); b.pop_right(); a.push_left(x); } cout << endl << endl << "Сума парних елементiв деку: " << sum << endl; a.dynam(); getch(); system("cls"); } else if (v=='5') { queue<int> a; int sum=0; while (!s.empty()){ x=s.front_left(); s.pop_left(); a.push_right(x); if(x%2==0) sum=sum+x; } while (!a.empty()){ x=a.front_right(); a.pop_right(); s.push_left(x); } cout << endl << "Сума парних елементiв деку:" << sum << endl; getch(); system("cls"); } } while (1); }