Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних Черга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Компютерних технологій автоматики та метрології
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Лабораторна робота
Предмет:
Структури даних та алгоритми
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Лабораторна робота № 4
Структура даних Черга
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Завдання: Змоделювати чергу, в якій задається початок черги і довжина черги (замість кінця черги). Після обробки всієї заданої вхідної послідовності знайти найбільший непарний елемент черги.
3 Алгоритм роз’вязку задачі:
Чергу організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку задаєм довжину і початок черги, потім по черзі вносимо елементи. Дані вносяться/вилучаються з черги залежно від знаку. В кінці знаходиться найбільший непарний елемент шляхом перебирання всіх елементів і порівняння з попереднім.
4 Динаміка вмісту черги:
Внесення в чергу вхідних даних( п - початок )
Довжина
п
0
Порожня черга
Довжина
п
23
1
Дані:23 Команда: push(23)
Довжина
п
23
59
2
Дані:23 Команда: push(59)
Довжина
п
23
59
22
3
Дані:23 Команда: push(22)
Довжина
п
59
22
2
Дані:23 Команда: pop(-3)
Довжина
п
59
22
69
3
Дані:23 Команда: push(69)
Довжина
п
59
22
69
34
4
Дані:23 Команда: push(34)
Довжина
п
22
69
34
3
Дані:23 Команда: pop(-5)
Довжина
п
22
69
34
27
4
Дані:23 Команда: push(27)
Довжина
п
22
69
34
27
88
5
Дані:23 Команда: push(88)
5 Результати виконання програми:
Висновки:
На цій лабораторній роботі я ознайомився з cтруктурою даних черга. Дослідив принципи і методи роботи.
Додатки:
//--------------------------------queue.cpp----------------------------------
#include <stdio.h>
#include <iostream>
using namespace std;
template<class item>
class queue{
private:
int cou; //початок черги
item *items; //Масив елементів
int count; // довжина черги
public:
//Конструктор з заданою ємністю
queue(int n,int p ){
count = 0;
items = new item[n];
cou=p;
}
//Деструктор
~queue(){delete[] items;}
//Занесення даних в чергу
void push(item it){
items[cou+count] = it;
count++;
}
bool empty(){ //перевірка чи черга порожня
if (cou+count<cou)
return true;
else
return false;
}
//Вилучення зі черги
void pop(){
if(empty()!=1){
cou++;
count-1;
}
else cout << "empty\n";
}
//Вивести вміст черги
void print(){
cout << "queue:";
for(int i = cou; i < cou+count; i++)
cout << items[i] << " ";
}
item top(int a){ //повертає значення заданого елемента
return items[a];
}
};
//--------------------------------main.cpp-----------------------------------
#include "queue.cpp"
//Варіант 5
void main()
{
int r,p;
cout <<"Rozmir->"<<endl; //вводимо довжину черги
cin >> r;
cout << endl <<"Pochatok->"<< endl; //вводимо початок черги
cin >> p;
int i,a; queue<int> queue1(r,p);
for(i = p; i < r+p; i++){ // запис елементів у чергу
cout <<endl<< "a="; cin >> a;
if (a>0) {
queue1.push(a);
queue1.print();
}
else {
queue1.pop();
queue1.print();
i=i-2;
}
}
cout << "Kinec chergu!!!" << endl;
int s=0; //знаходження найбільшого непарного елемента
for (int i=p; i<=r+p;i++)
if(queue1.top(i)%2==1){
if (s<queue1.top(i)){
s=queue1.top(i);
}
}
cout << endl <<endl <<"Naubilshuy neparnuy el ->"<<s << endl;
}
27.11.2012 18:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора