Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних Черга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
Звіт
З лабораторної роботи №4
Структура даних Черга
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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами
даних, а не як з масивами.
24. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності перевірити, чи є у деку три однакових числа, які йдуть підряд одне за одним.
3. Динаміка вмісту деку.
3.1. Послідовність 10 цілих (додатніх, від'ємних, нульових, парних і непарних) чисел
3 -3 -1 3 6 5 3 4 7 6
3.2. Схематичне зображення черги після обробки кожного числа з вхідної послідовності
1)
(порожній дек)
2)
3
Push(3)
3)
Pop() ”Queue is empty”
4)
Pop(), “Queue underflow”, “Queue is empty”
5)
3
push(3)
6)
3
6
Push(6)
7)
5
3
6
Push(5)
8)
3
5
3
6
Push(3)
9)
3
5
3
6
4
Push(4)
10)
7
3
5
3
6
4
Push(7)
11)
7
3
5
3
6
4
push(6); errors: “Queue overflow” 12)
4. Алгоритм розв’язання задачі
Спочатку я створив клас деку deque та описав для нього власне поле імен, щоб уникнути
конфліктів. Для виводу динаміки черги написав окрему функцію під
назвою show_dynamics(). Виконання моєї програми іде за таким алгоритмом:
1. Ініціалізуємо усі потрібні змінні, створюємо «чергу»
2. Вводимо К та послідовність чисел з клавіатури
3. Перевіряємо чи число є менше 0. Якщо ні то додаємо це число у дек.
Якщо є менше 0, то вилучаємо елемент з деку та перевіряємо новий перший елемент на
парність. Якщо парний, то вилучаємо усі такі є парні елементи з деку.
4. Після закінчення циклу обробки даних, перевіряємо чи дек містить три однакових числа і виводимо повідомлення на екран , завершуємо роботу програми
Величина деку рівна 6 елементам. Вхідна послідовність рівна 10 елементам. Під час
виконання програми можна подивитись помилки та вирішення мого
варіанту завдання.
5. Результати виконання програми
/
/
/
/
/
/
/
/
/
Висновки
Виконуючи цю лабораторну роботу я дослідив абстрактний тип даних «черга». Дослідив цей
тип даних, навчився працювати з «чергою» та застосовувати до різних прикладних задач.
Написав програму, що відповідала моєму завданні та описав результати роботи в цьому звіті.
Також при написанні програми додатково ознайомився з переводом потоків вводу-виводу та
застосував це у своїй програмі.
Додатки
main.cpp
#include <iostream>
#include "queue.h"
using namespace std;
#define Type int
void ShowDeq(Queue<Type>);
bool Checking(Queue<Type>);
void ShowArr(const Type *arr, int n);
int main (void)
{
const int size = 10;
Type date[size] = {0};
int i = 0;
Queue<Type> deq;
i = 0;
cout << "Enter sequence with " << size << " elements:\n " ;
while (i < size) {
cin >> date[i];
++i;
}
system("cls");
for (i=0; i < size; i++) {
system("cls");
ShowArr(date, size);
if ( (date[i] & 1) == 0 ) {
if ( date[i] < 0 ) {
if (deq.empty()) {
system("cls");
cout << "Error! Deq underflow!\a\n";
ShowDeq(deq);
system("Pause");
}
else {
cout << "Element " << deq.front_right() << " popped from deq!\n\n";
deq.pop_right();
ShowDeq(deq);
system("Pause");
}
}
else
if(date[i] >= 0){
if (deq.full()) {
cout << "Error! Deq overflow. \a\n";
ShowDeq(deq);
system("Pause");
}
else {
deq.push_right( date[i]);
cout << "Element " << deq.front_right() << " pushed to deq!\n\n";
ShowDeq(deq);
system("Pause");
}
}
}
else
if(date[i]<0){
if(deq.empty()){
cout << "Error! Deq underflow!\a\n";
ShowDeq(deq);
system("Pause");
}
else {
cout << "Element " << deq.front_left() << " popped from deq!\n\n";
deq.pop_left();
ShowDeq(deq);
system("Pause");
}
}
else
if(date[i]>0){
if (deq.full()) {
cout << "Error! Deq overflow!\a\n";
ShowDeq(deq);
system("Pause");
}
else {
deq.push_left( date[i]);
cout << "Element " << deq.front_left() << " pushed to deq!\n\n";
ShowDeq(deq);
system("Pause");
}
}
}
system ("cls");
ShowArr(date, size);
ShowDeq(deq);
if (Checking(deq))
cout << "In the deq are three identical numbers that consecutive one by one!\n";
else
cout << "In the deq are'nt three identical numbers that consecutive one by one!\n";
system("Pause");
return 0;
}
void ShowDeq(Queue<Type> qq)
{
while (!qq.empty()) {
cout << qq.front_left() << " " ;
qq.pop_left();
}
cout << endl;
}
void ShowArr(const Type *arr, int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
}
bool Checking(Queue<Type> qq)
{
Type x;
int count = 1;
while (!qq.empty()) {
x = qq.front_left();
qq.pop_left();
if (x == qq.front_left()) {
count++;
}
if (count == 3)
return true;
if (x != qq.front_left())
count = 0;
}
return false;
}
queue.h
#ifndef _QUEUE_H_
#define _QUEUE_H_
template <class T>
class Queue
{
public:
const static int CAPACITY = 6;
private :
T deq[CAPACITY];
int first;
int last;
public:
Queue();
~Queue() {};
bool empty() const;
bool full() const;
bool push_left(const T & k);
bool push_right(const T & k);
bool pop_left();
bool pop_right();
T front_left() const;
T front_right() const;
};
template <class T>
Queue<T>::Queue()
{
first = CAPACITY / 2;
last = first - 1;
}
template <class T>
bool Queue<T>::empty() const
{
return first == last + 1;
}
template <class T>
bool Queue<T>::full() const
{
if (last == Queue<T>::CAPACITY - 1)
return true;
else
return false;
}
template <class T>
bool Queue<T>::push_left(const T & k)
{
if (this ->full() || first == 0)
return false;
deq[--first]=k;
return true;
}
template <class T>
bool Queue<T>::push_right(const T & k)
{
if (this ->full())
return false;
deq[++last]=k;
return true;
}
template <class T>
bool Queue<T>::pop_left()
{
if(empty())
return false;
++first;
return true;
}
template <class T>
bool Queue<T>::pop_right()
{
if(empty())
return false;
--last;
return true;
}
template <class T>
T Queue<T>::front_left() const
{
return deq[first];
}
template <class T>
T Queue<T>::front_right() const
{
return deq[last];
}
#endif
18.03.2015 01:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора