МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних ЧЕРГА до лабораторної роботи № 2 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " № варіанта = [ (10 ) + ( ASCII–код 114 )] % 30 + 1 Варіант - 5 Львів-2011 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). ЗАВДАННЯ №5 Змоделювати чергу, в якій задається початок черги і довжина черги (замість кінця черги). Після обробки всієї заданої вхідної послідовності знайти найбільший непарний елемент черги. 3. Алгоритм виконання: - задання довжини черги; - зчитування числа; - перевірка чи це число додатнє, чи від’ємне: додатнє заноситься в чергу, а від’ємне вилучає з черги один елемент; - знаходження найбільшого непарного елемента черги; - виведення результатів; 4. Динаміка зміни вмісту черги: 84, 32, 43, 16, 58, - 62, - 65, 52, 39, 54           П           84           П 84 32          П           84 32 43         П 84 32 43 16        П           84 32 43 16 58       П 32 43 16 58        П            43 16 58        П  43 16 58 52        П           43 16 58 52 39      П  43 16 58 52 39 54     П 5. Результати виконання програми:
Висновок: На даній лабораторній роботі я вивчив фундаментально абстрактноу структури даних - черги. Набув практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. ДОДАТОК #include "queue.h" #include <iostream> #include <cstring> #include <cstdlib> #include <ctime> using namespace std; int main() { int arr[30]; srand(time(0)); queue a; for (int i = 0; i < 30; i++) { arr[i] = rand() % 200 - 100; } std::cout << "Input sequence: "; for (int i = 0; i < 30; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; for (int i = 0; i < 30; i++) { a.push(arr[i]); } std::cout << "Max non parity: " << a.max_nonparity() << std::endl; return 0; } #include <cassert> #include <cstring> #include <iostream> #include "queue.h" queue::queue( ) { count = 0; first = 0; } int queue::front( ) const { assert(!empty( )); return data[first]; } void queue::pop( ) { assert(!empty( )); first = next_index(first); --count; print(); } void queue::push(const int& entry) { assert(size( ) < CAPACITY); data[first+count] = entry; ++count; print(); } int queue::max_nonparity() { int max = first; for (int i = first; i < first+count; i++) { if (data[i] > max) { max = data[i]; } } return max; } void queue::print() { std::cout << "queue: "; for (int i = first; i < first+count; i++) { std::cout << data[i] << " "; } std::cout << std::endl; } #include <cstdlib> // Provides size_t class queue { public: static const int CAPACITY = 30; // КОНСТРУКТОР queue( ); // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void pop( ); void push(const int& entry); // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty( ) const { return (count == 0); } int front( ) const; int size( ) const { return count; } int max_nonparity(); void print(); private: int data[CAPACITY]; int first; int count; // ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ int next_index(int i) const { return (i+1) % CAPACITY; } };