2. Завдання 2: Динамічні структури даних 2.1. Теоретична частина В програмуванні та комп'ютерних науках структу?ри да?них — це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру. Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх обробки. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій. Відома формула «Програма = Алгоритми + Структури даних» дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тої чи іншої структури даних для їх збереження, а навпаки. Підтримка базових структури даних, які використовуються в програмуванні, включена в комплекти стандартних бібліотек найбільш розповсюджених мов програмування, таких як Standart Template Library для C++, Java API, Microsoft.NET, тощо. Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена) Основні операції з чергою англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow). англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow). Реалізація на мовах програмування Черга може бути реалізована за допомогою масива Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, lenght[Q] -- довжина черги. Черга аналогічна черзі людей у супермаркеті: перший клієнт у ній обслуговується першим, а решта клієнтів займають чергу з кінця і очікують, коли їх обслужать. Вузли черги видаляються тільки з голови черги, а розміщуються в чергу тільки в її хвості. Тому, черга – це структура даних типу «першим ввійшов – першим вийшов» («fіrst-іn, fіrst-out» – FІFO). Операції «помістити в чергу» і «видалити з неї» відомі як enQueue і deQueue відповідно. У черг є багато застосувань в обчислювальних системах. У більшості комп’ютерів є тільки один процесор, тому в один момент часу може бути обслужений тільки один користувач. Запити інших користувачів поміщаються в чергу. Кожен запит поступово просувається в черзі вперед у міру того, як відбувається обслуговування користувачів. Запит на початку черги є черговим кандидатом на обслуговування. Черги також застосовують для підтримання процесу буферизації потоків даних, які виводяться на друк. У багатокористувацькому середовищі може бути тільки один принтер. У багатьох користувачів у процесі виконання програм може виникнути потреба одночасного виведення на друк даних. Такі вихідні дані записуються в буферний файл на диску, де вони очікують у черзі, поки принтер не стане для них доступним. Інформаційні пакети також очікують своєї черги в комп’ютерних мережах. Пакет може надійти на вузол мережі в будь-який момент часу, а потім він має бути відправлений до наступного вузла мережі у напрямі свого кінцевого пункту призначення. Вузол маршрутизації (вузол, який зберігає інформацію про маршрут) направляє в кожен момент часу один пакет; тому пакети перебувають у черзі доти, доки програма маршрутизації не обробить їх. Файл-сервер у комп’ютерній мережі обробляє запити багатьох клієнтів мережі. Сервери мають обмежену пропускну здатність обслуговування запитів клієнтів. Коли така пропускна здатність перевищена, запит клієнта очікує своєї черги (див. ПП14.4 на CD). Неустановлення вказівника зв’язку в останньому вузлі черги в нуль є помилковим. Програма (див. ПП14.4 на CD) створює шаблон класу черг на основі схованого спадкування шаблону класу списків. Нехай черга має функції – члени enQueue, deQueue, іsQueueEmpty і prіntQueue. Зазначимо, що ці фукції-члени є функціями-членами шаблону класу списків іnserAtBack, removeFromFront, іsEmpty і prіnt відповідно. Зазвичай шаблон класу списків містить і інші функції-члени (іnsertAtFront і removeFromBack), які не бажано було б робити доступними для класу черг через відкритий інтерфейс. Отже, коли вказується, що шаблон класу черг має успадковувати шаблон класу списків, то задається сховане спадкування. Це приводить до того, що всі функції-члени шаблону класу списків стають схованими в шаблоні класу черг. Коли реалізуються функції-члени черги, вони мають викликати відповідні функції-члени класу списків: enQueue повинна викликати іnsertAtBack, deQueue_removeFromFront, іsQueueEmpty_ іsEmpty, а функція-член prіntQueue – викликати prіnt. Шаблон класу черг використовують у функції maіn для реалізації черги з даними цілого типу іntQueue типу Queue<іnt>. Цілі числа від 0 до 3 містяться в черзі до іntQueue, а потім видаляються з неї за принципом «першим ввійшов – останнім вийшов». Потім шаблон класу черга використовується для реалізації черги з дійсними значеннями floatQueue типу Queue<float>. Дійсні значення 1.1, 2.2, 3.3 і 4.4 поміщаються в чергу floatQueue, а потім видаляються з неї за тим же принципом «першим ввійшов – останнім вийшов».2.2. Частина 1: Побудова АТД 2.2.1. Постановка задачі Змоделювати абстрактний тип даних (АТД) на базі статичного масиву, який використати в другій частині цього завдання. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів в АТД. Для реалізації цього задати послідовність з К > 10 цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в АТД, а кожне непарне число має вилучати з АТД один елемент. Виводити на екран динаміку вмісту АТД під час обробки заданої послідовності. 2.2.2. Динаміка вмісту Виберу якусь вхідну послідовність для виконання програми 1,2,3,-4,5,-6,-7,-8,9,10 Намалюю динаміку вмісту стеку після введення таких даних:
2.2.3. Результати виконання програми Програма виводить динаміку стеку в текстовому вигляді і по завершенню дублює вміст стеку, як було задано в умові.
б) Розглянемо випадок, коли буде викликатися функція pop() з пустого стеку, або push(x) з заповненим(розмір масиву під стек заданий 10) 1,-2,-3,4,5,6,7,8,9,10,11,12,13,14
Перед другим кроком черга була порожня і була виконана функція pop() – програма повідомила, що це некоректний ввід. На останніх кроках (13 та 14) масив черги був переповненим і була виконана функція push(14) – програма повідомила, що це некоректний ввід. 2.3. Частина 2. Застосування АТД 2.3.1. Постановка задачі Розв’язати задачу використовуючи АТД "ЧЕРГА" 10. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2. Промоделювати стан черги. Розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець. 2.3.2. Алгоритм розв’язання задачі Для розв’язання цієї задачі використовую чергу, створену у частині 1. Додаю до неї функції void push_front(int a); void pop_last(); та int last1(); для роботи з покупцями які невитримали і пішли (pop_last) та з пільговими покупцями, що додаються в початок черги (push_front). В файлі main.cpp запрограмував введення з клавіатури вхідних даних. Потім додав до черги перших m покупців. Тоді в циклі перевіряю чи не настав час деякої події (додання покупця, вилучення покупця, додання пільгового покупця, вилучення останнього покупця). Час цих подій задаю за допомогою псевдовипадкових чисел. При настання часу деякої події виконую її. Кожної ітерації цикла додаю 1 до поточного часу. Вихід з циклу реалізовано по перевищенню поточного часу за час експерименту. При здійсненні первної події виводжу про це повідомлення а також вмістимість всієї черги. 2.3.3. Результати виконання програми
Висновки Виконуючи цю частину курсової роботи я навчився дослідження внутрішнє представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних, а саме детально познайомився з структурою даних черга і навчився використовувати її на прикладі конкретної задачі. Список літератури Матвейчук Т. А. Основи представлення данних в пам'яті комп'ютера: Конспект лекцій (частина І ) з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми". – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 37 с. Конспект лекцій. Додатки До завдання 1 #include <iostream> #define N 1000 using namespace std; class Queue { public: void push(int a); void pop(); int front(); bool empty(); bool full(); Queue(); //конструктор по замовчуванню void show(); int count_show(); protected: int arr[N]; int first, last, count; }; #include "queue.h" void Queue::push(int a) { if (full() == 1) cout << "Неможливо додати елемент, масив переповнений" << endl; else { last++; arr[last] = a; count++; } } void Queue::pop() { if (empty() == 1) { cout << "Неможливо вийняти елемент, черга порожня" << endl;
} else { first++; count--; }
} int Queue::front() { return arr[first]; } bool Queue::empty() { return (first == last+1); } bool Queue::full() { return (last == N-1); } Queue::Queue() { first = 0; last = -1; count = 0; } void Queue::show() { cout << "Вмiст черги:" << endl; for (int i = first; i < last+1; i++) cout << arr[i] << " "; cout << endl; } int Queue::count_show() { return count; } До завдання 2 #include <iostream> #define N 1000 using namespace std; class Queue { public: void push(int a); void push_front(int a); void pop(); void pop_last(); int front(); int last1(); bool empty(); bool full(); Queue(); //конструктор по замовчуванню void show(); int count_show(); protected: int arr[N]; int first, last, count; }; #include "queue.h" void Queue::push(int a) { if (full() == 1) cout << "Неможливо додати елемент, масив переповнений" << endl; else { last++; arr[last] = a; count++; } } void Queue::push_front(int a) { if (full() == 1) cout << "Неможливо додати елемент, масив переповнений" << endl; else { first--; arr[first] = a; count++; } } void Queue::pop() { if (empty() == 1) { cout << "Неможливо вийняти елемент, черга порожня" << endl;
} int Queue::front() { return arr[first]; } int Queue::last1() { return arr[last]; } bool Queue::empty() { return (first == last+1); } bool Queue::full() { return (last == N-1); } Queue::Queue() { first = 0; last = -1; count = 0; } void Queue::show() { cout << "Вмiст черги:" << endl; for (int i = first; i < last+1; i++) cout << arr[i] << " "; cout << endl; } int Queue::count_show() { return count; } #include "queue.h" #include <string.h> #include <time.h> int main() { setlocale (0, ""); srand(time(0));
int now_time = 0; int T; int number = 1; int temp; Queue q1;
int m, t1, t2, t3, t4; cout << "Введiть вхiднi данi - m, t1, t2, t3, t4" << endl; cin >> m >> t1 >> t2 >> t3 >> t4; cout << "Введiть час Т - час, впродовж якого проводитиметься дослiдження" << endl; cin >> T; int now_t1 = rand()%(t1) + 1; int now_t2 = rand()%(t2) + 1; int now_t3 = rand()%(t3) + 1; int now_t4 = rand()%(t4) + 1;
