Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних Черга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота № 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();
}
18.11.2012 16:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора