Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних ЧЕРГА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 4
на тему:
"Структура даних ЧЕРГА "
з дисципліни:
" Програмування. Частина III. Структуриданих та алгоритми "
Вибір індивідуального завдання:
№варіанта=(11+97)%30+1=19
Львів – 2012
МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудовичерги, дослідження динаміки його вмісту та використання черг для розв'язання прикладних задач.
ПОСТАНОВКА ЗАДАЧІ
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow).
19. Змоделювати дек, в якому до опису деку додано функцію change, яка міняє значення елементів, що знаходяться в лівому та в правому кінцях деку. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба обміняти значення лівого і правого кінців деку. Після обробки всієї заданої вхідної послідовності знайти суму парних чисел деку.
ДИНАМІКА ВМІСТУ ЧЕРГИ
Послідовність K цілих (додатніх, від'ємних, нульових, парних і непарних) чисел
Моя послідовність: 1 2 3 4 5 -1 0 3 4 5 2 1
Схематичне зображення черги після обробки кожного числа з вхідної послідовності
Введемо такі позначення: П – покажчик початку черги, К – покажчик кінця черги
К П
-queue();
П К
1
-push_left(1);
П К
1
2
- push_right(2);
П К
3
1
2
- push_left(3);
П К
3
1
2
4
- push_right(4);
П К
5
3
1
2
4
- push_left(5);
П К
3
1
2
4
- pop();
П К
4
1
2
3
- change();
П К
3
4
1
2
3
- push_left(3);
П К
3
4
1
2
3
4
- push_right(4);
П К
5
3
4
1
2
3
4
- push_left(5);
П К
5
3
4
1
2
3
4
2
- push_right(2);
П К
1
5
3
4
1
2
3
4
2
- push_left(1);
Визначити суму парних елементів деку.
Сума парних елементів деку рівна 12.
АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ
Створюємо клас queue1.h
Під час реалізації програми вводимо послідовність чисел. Якщо число непарне, то вводимо в ліву сторону черги, якщо парне – в праву.
При вводі від’ємного числа ми вилучаємо 1-й елемент черги.
При вводі 0, ми міняємо лівий і правий елемент місцями.
Виводимо результуючу чергу.
Виводимо суму парних чисел.
Завершуємо роботу програми.
РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАММИ
Скріншот 1: Меню програми.
Скріншот 2: Ввід натуральних чисел.
Скріншот 3: Вивід результуючої черги.
Скріншот 4: Сума парних чисел.
ВИСНОВКИ
На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних – чергу. Набувпрактичних навичок побудови черги та провів дослідження динаміки її вмісту.
ДОДАТКИ
queue1.h
#ifndef MAIN_SAVITCH_QUEUE1_H
#define MAIN_SAVITCH_QUEUE1_H
#include <cstdlib> // Provides size_t
#include <cassert> // Надає макрос assert.
#include <conio.h>
#include <iostream>
namespace main_savitch_8B
{
template <class Item>
class queue
{
public:
// ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ
typedef std::size_t size_type;
typedef Item value_type;
static const size_type CAPACITY = 30;
// КОНСТРУКТОР
queue( ){
count = 0;
first = 0;
last = CAPACITY/2;
};
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ
void pop_left( ) {
assert(!empty( ));
first = next_index(first);
--count;
};
void pop_right() {
assert(!empty( ));
last = prev_index(last);
--count;
}
void push_right(const Item& entry) {
assert(size( ) < CAPACITY);
last = next_index(last);
data[last] = entry;
++count;
};
void push_left(const Item& entry) {
assert(size( ) < CAPACITY);
first = prev_index(first);
data[first] = entry;
++count;
}
void dynam() {
if(!empty()) for (int i=first; i<=last; i++) cout << "| " << data[i] << " |";
};
void commute_left(const Item& entry) {
if(data[first]<10) {
cout << "Елемент " << data[first] << " замiнено на - " << entry;
assert(size( ) < CAPACITY);
data[first] = entry;
++count;
}
else cout << "Елемент не є < 10";
};
void commute_right(const Item& entry) {
if(data[last]<10) {
cout << "Елемент " << data[last] << " замiнено на - " << entry;
assert(size( ) < CAPACITY);
data[last] = entry;
++count;
}
else cout << "Елемент не є < 10";
};
void change() {
Item x=data[last];
data[last]=data[first];
data[first]=x;
};
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ
bool empty( ) const { return (count == 0); }
Item front_left( ) const {
assert(!empty( ));
return data[first];
};
Item front_right( ) const {
assert(!empty( ));
return data[last];
};
size_type size( ) const { return count; }
private:
Item data[CAPACITY];
size_type first;
size_type last;
size_type count;
// ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ
size_type next_index(size_type i) const { return (i+1) % CAPACITY; }
size_type prev_index(size_type i) const { return (i-1) % CAPACITY; }
};
}
#endif
main.cpp
#include <iostream>
#include "queue1.h"
#include <conio.h>
using namespace std;
using namespace main_savitch_8B;
int main() {
queue<int> s;
char v; int x=1;
system("color 0f");
setlocale(LC_CTYPE,"Ukrainian");
do{
cout << "Команди роботи:" << endl;
cout << " " << "1. Push(x)." << endl;
cout << " " << "2. Pop_right()." << endl;
cout << " " << "3. Pop_left()." << endl;
cout << " " << "4. Автоматичний показ роботи деку." << endl;
cout << " " << "5. Iндивiдуальне завдання(сума парних елементiв)." << endl;
cout << " " << "6. Вихiд." << endl << endl;
if (x==0) cout << "Крайнi елементи помiнянi мiсцями." << endl;
s.dynam();
cout << endl << endl;
v=getch();
system("cls");
if (v=='6') return 0;
else if (v=='1'){
cout << "Введiть x - ";
cin >> x;
if(x<0){
if (x%2==0) s.pop_right();
else s.pop_left();
}
else if (x>0) {
if (x%2==0) s.push_right(x);
else s.push_left(x);
}
else s.change();
system("cls");
}
else if (v=='2'){
s.pop_right();
system("cls");
}
else if (v=='3'){
s.pop_left();
system("cls");
}
else if (v=='4'){
queue<int> a;
cout << "push(1) - " << endl;
a.push_left(1);
a.dynam();
cout << endl << endl << "push(2) - " << endl;
a.push_right(2);
a.dynam();
cout << endl << endl << "push(3) - " << endl;
a.push_left(3);
a.dynam();
cout << endl << endl << "push(4) - " << endl;
a.push_right(4);
a.dynam();
cout << endl << endl << "push(5) - " << endl;
a.push_left(5);
a.dynam();
cout << endl << endl << "push(6) - " << endl;
a.push_right(6);
a.dynam();
cout << endl << endl << "push(7) - " << endl;
a.push_left(7);
a.dynam();
cout << endl << endl << "s.pront_left() - " << a.front_left();
cout << endl << "s.pront_right() - " << a.front_right() << endl;
cout << endl << endl << "push(-8) - " << endl;
a.pop_right();
a.dynam();
cout << endl << endl << "push(-9) - " << endl;
a.pop_left();
a.dynam();
cout << endl << endl << "push(10) - " << endl;
a.push_right(10);
a.dynam();
cout << endl << endl << "pop_right() - " << endl;
a.pop_right();
a.dynam();
cout << endl << endl << "pop_left() - " << endl;
a.pop_left();
a.dynam();
cout << endl << endl << "push(11) - " << endl;
a.push_left(11);
a.dynam();
cout << endl << endl << "push(12) - " << endl;
a.push_right(12);
a.dynam();
cout << endl << endl << "Дек до змiн:" << endl;
a.dynam();
cout << endl << "Дек пiсля обертання:" << endl;
a.change();
a.dynam();
queue<int> b;
int sum=0;
while (!a.empty()){
x=a.front_left();
a.pop_left();
b.push_right(x);
if(x%2==0) sum=sum+x;
}
while (!b.empty()){
x=b.front_right();
b.pop_right();
a.push_left(x);
}
cout << endl << endl << "Сума парних елементiв деку: " << sum << endl;
a.dynam();
getch();
system("cls");
}
else if (v=='5') {
queue<int> a;
int sum=0;
while (!s.empty()){
x=s.front_left();
s.pop_left();
a.push_right(x);
if(x%2==0) sum=sum+x;
}
while (!a.empty()){
x=a.front_right();
a.pop_right();
s.push_left(x);
}
cout << endl << "Сума парних елементiв деку:" << sum << endl;
getch();
system("cls");
}
} while (1);
}
18.03.2015 01:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора