Структура даних Черга. Лабораторна робота з Інші. Робота № 517852

Структура даних Черга

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2012

Тип роботи:

Лабораторна робота

Предмет:

Інші

Група:

КІ

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 4 Структура даних Черга 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги.Набуття практичних навичок побудовичерги, дослідженнядинаміки її вмісту та використання черг для розв'язання прикладних задач. 2 Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові елементи.). 3 Алгоритм роз’вязку задачі: Дек організовуємо у вигляді класу. Це дає можливість працювати з усіма типами даних. Спочатку по черзі вносимо елементи. Дані вносяться в дек з права якщо елемент додатній та парний і вносяться з ліва якщо елемент не парний, а якщо елемент від’ємний парний то він робить операцію pop з права, не парний то з ліва. 4.Динаміка вмісту деку: Внесення в основний дек вхідних даних(п– правий край, л – лівий край) 1)push_left(5) 5 2)push_left(9) 9 5 3)push_right(14) 9 5 14 4)push_right(54); 9 5 14 54 5)push_left(63) 63 9 5 14 54 6)push_right (4) 63 9 5 14 54 4 7)pop_left(-3) 9 5 14 54 4 8)push_left(5) 5 9 5 14 54 4 9)pop_right (-6) 5 9 5 14 54 10)push_left(5) 5 5 9 5 14 54 11)push_right(2) 5 5 9 5 14 54 2 5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась зcтруктурою даних черга. А саме із різновидом черги – дек. Дослідила принципи і методи роботи з чергою та деком. Додатки: *****************quere.cpp************* #include <stdio.h> #include <iostream> #include <conio.h> using namespace std; template<class item> class deq{ private: //Left right int left,right; //Розмір int count; //Масив елементів item *items; //Capacity - ємність int Capacity; public: //Конструктор з заданою ємністю deq(int n){ Capacity = n; items = new item[Capacity]; count = 0; left = Capacity / 2; right = left - 1; } //Деструктор ~deq(){delete[] items;} //Занесення даних в дек void push_right(item it){ if (count < Capacity){ if(right == Capacity - 1 ){ for (int i = left - 1; i < right; i++) items[i]=items[i + 1]; items[right] = it; left--; } else items[++right] = it; count++; } } //Якшо дані досягають кінця масиву, то вони //перевисуються на одну позицію від кінця void push_left(item it){ if (count < Capacity){ if(left == 0){ for (int i = right + 1; i > 0; i--) items[i] = items[i - 1]; items[left] = it; right++; } else items[--left] = it; count++; } } //Розмір деку int size(){return count;} //Перевірка чи дек порожній bool empty(){return (count == 0);} //Вершина деку item front_left(){if (!empty())return items[left];} item front_right(){if(!empty())return items[right];} //Вилучення з деку void pop_left(){ if(!empty()){ left++; count--; } } void pop_right(){ if(!empty()) right--; count--; } //Вивести вміст деку void print(){ cout << "deq:"; if(!empty()){ for(int i = left; i <= right; i++) cout << items[i] << " "; if (count == Capacity) cout << "size:full" << endl; else cout << "size:" << count << endl; } else cout << " empty" << endl; } void perevirka() { int k=0; for(int i = left; i <= right; i++) if (items[i]==items[i+1]) k++; if (k!=0) cout<<"je chysla jaki povtirjujutsja"; else cout<<"vsi chysla rizni"; } }; *******************main.cpp****************** #include "quere.cpp" void main() { int i,a; deq<int> deq1(20); //Приклад масиву printf("arr={1,2,-3,-4,4,3,8,1,7,5,8}\n"); //Занесення даних в дек з клавіатури deq1.print(); for(i = 0; i <= 10; i++){ cout << "a="; cin >> a; if(a < 0) //Якщо число відємне і парне вилучаємо справа //інакше - зліва if(-a % 2 == 0) deq1.pop_right(); else deq1.pop_left(); else //Якщо число додатнє і парне додаємо //елемент справа інакше зліва. if(a%2 == 0) deq1.push_right(a); else deq1.push_left(a); deq1.print(); //Виведення вмісту деку } int s = deq1.size(); //розмір деку deq1.perevirka(); getch(); }

Лабораторна робота Інші

rew1rew

18.11.2012 16:52

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись