Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних Черга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Лабораторна робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Лабораторна робота № 4
Структура даних Черга
Львів – 2010
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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності продублювати всі елементи дека (тобто замість кожного одного елемента має стати підряд два однакових).
3 Алгоритм роз’вязку задачі:
Дек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку по черзі вносимо елементи. Дані вносяться/вилучаються з черги з лівого/правого краю залежно від знаку і від парності числа. Дані вилучаються і заносяться в додаткову чергу два рази, а потім назад.
4 Динаміка вмісту деку:
Внесення в основний дек вхідних даних(п – правий край, л – лівий край)
п
л
Порожній дек
лп
1
Дані: 1 Команда: push_left(1)
л
п
1
2
Дані: 2 Команда: push_right(2)
пл
2
Дані: -3 Команда: pop_left()
п
л
Дані: -3 Команда: pop_right()
пк
4
Дані: 4 Команда: push_right(4)
л
п
3
4
Дані: 3 Команда: push_left(3)
л
п
3
4
8
Дані: 8 Команда: push_right(8)
л
п
1
3
4
8
Дані: 1 Команда: push_left(1)
л
п
7
1
3
4
8
Дані: 7 Команда: push_left(7)
л
п
5
7
1
3
4
8
Дані: 5 Команда: push_left(5)
л
п
5
7
1
3
4
8
8
Дані: 8 Команда: push_right(8)
Занесення даних з одного кінця деку в інший з подвоєнням
(п – правий край, л – лівий край)
л
п
5
7
1
3
4
8
8
л
п
7
1
3
4
8
8
5
5
л
п
1
3
4
8
8
5
5
7
7
л
п
3
4
8
8
5
5
7
7
1
1
л
п
4
8
8
5
5
7
7
1
1
3
3
л
п
8
8
5
5
7
7
1
1
3
3
4
4
л
п
8
5
5
7
7
1
1
3
3
4
4
8
8
л
п
5
5
7
7
1
1
3
3
4
4
8
8
8
8
5 Результати виконання програми:
Висновки:
На цій лабораторній роботі я ознайомився з cтруктурою даних черга. А саме різновид черги – дек. Дослідив принципи і методи роботи зі чергою і деком.
Додатки:
//--------------------------------quere.cpp----------------------------------
#include <stdio.h>
#include <iostream>
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;
}
};
//--------------------------------main.cpp-----------------------------------
#include "quere.cpp"
//Варіант 10
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(); //розмір деку
//Перенесення даних з одного кінця деку
//в інший з подвоєнням
for(i = 0; i < s; i++){
deq1.push_right(deq1.front_left());
deq1.push_right(deq1.front_left());
deq1.pop_left();
deq1.print();
}
getchar(); getchar();
}
25.11.2012 18:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора