Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних ЧЕРГА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Структури даних та алгоритми
Група:
КІ-25
Частина тексту файла (без зображень, графіків і формул):
Мiнiстерство освiти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
з лабораторної роботи № 4
з дисципліни: «Програмування. Частина III.
Структури даних та алгоритми»
на тему:
«Структура даних ЧЕРГА»
Варіант № : (6+97) % 30 + 1 = 14
2011
Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
Постановка задачі:
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа.
Алгоритм розв’язання задачі:
Аналізую чергу, яка задана завданням
Створюю клас queue і наповнюю його інтерфейс.
Описую методи push, pop, top, empty, show,full, wipe_out та конструктор.
Під`єднуюю заголовочний файл q.h до stdafx.h, де зберігаються всі заготовочні файли.
Заповнюю файл main.cpp, яка демонструє роботу моєї черги як абстрактної структури.
Динаміка вмісту черги під час обробки введеної послідовності
Позначимо: P – початок черги; К – кінець черги.
В послідовності 5 4 3 0 1 2 -5 2 3, якщо зустрічається елемент зі значенням 0 застосовується функція wipe_out() – видалення всіх елементів черги, якщо зустрічається додатне число – виконується ф-ція push(), та ф-ція pop(), якщо число від’ємне.
1) K P
порожня
черга
2) P K
5
push(5)
3) P K
5
4
push(4)
4) P K
5
4
3
push(3)
5) K P
wipe_out()
6) P K
1
push(1)
7) P K
1
2
push(2)
8) P K
2
pop()
9) P K
2
2
push(2)
10) P K
2
2
3
push(3)
Результати виконання програми:
Висновок:
На лабораторній роботі я досліджував абстрактну структуру даних: чергу. Набув практичних навичок побудови черги, досліджував динаміку його вмісту та розв’язав задачу.
Додатки:
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
const int M = 100;
#pragma once
#include <cassert>
#include "q.h"
#include <stdio.h>
#include <tchar.h>
#include <iostream>
// q.h
template <class Item>
class queue
{
private:
Item INFO[M];
int count;
public:
queue( );
void pop( );
void push(const Item& entry);
bool empty( ) const { return (count == 0); }
Item front( ) const;
int size( ) const { return count; }
void show();
void muve();
bool full(){return (INFO[M-1] == M-1);};
void wipe_out();
bool same();
};
template <class Item>
queue<Item>::queue( )
{
count = 0;
INFO[0] = 1;
INFO[M-1] = 0;
}
template <class Item>
Item queue<Item>::front( ) const
{
assert(!empty( ));
return INFO[1];
}
template <class Item>
void queue<Item>::pop( )
{
muve();
count--;
}
template <class Item>
void queue<Item>::push(const Item& entry)
{
assert(!(count > M - 1));
++count;
INFO[++INFO[M-1]] = entry;
}
template <class Item>
void queue<Item>::show()
{
std::cout << "QUENE: ";
for(int i = INFO[0]; i < INFO[M-1]+1; i++){
std::cout << INFO[i] << " " ;
}
std::cout << std::endl;
}
template <class Item>
void queue<Item>::muve()
{
for(int i = INFO[0]; i < INFO[M-1]; i++){
INFO[i] = INFO[i+1];
}
--INFO[M-1];
}
template <class Item>
void queue<Item>::wipe_out()
{
for (int i=0; i<count; i++)
{
muve();
}
count = 0;
}
template <class Item>
bool queue<Item>::same()
{
bool b = false;
for (int i=0; i<count-1; i++)
if (INFO[i]==INFO[i+1]) { b = true; }
return b;
}
//main.cpp
#include "stdafx.h"
using namespace std;
int main()
{
queue<int> q;
int v[M], m;
int k = 0;
cout << "ENTER VALUE OF QUEUE TO CONTINUE OR TEXT TO EXIT..." << std::endl;
while(cin >> v[k++]) { m = k; }
q.show();
for(k = 0; k < m; k++)
{
if (v[k]==0) { q.wipe_out(); q.show(); }
if (v[k]>0) { q.push(v[k]); q.show(); }
if (v[k]<0) { q.pop(); q.show(); }
}
cout << "\nSIZE: " << q.size() << endl;
cout << "EMPTY: " << boolalpha << q.empty() << endl;
cout << "FULL: " << boolalpha << q.full() << endl;
cout << "FRONT: " << q.front() << endl;
cout << "THE SAME ELEMENTS IN QUEUE: " << q.same() << endl;
cin.get();
return 0;
}
18.11.2012 22:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора