Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ. ЧЕРГА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
З лабораторної роботи №1.2
На тему:
«ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ. ЧЕРГА »
з дисципліни:
«Обчислювальний практикум»
Львів – 2013
Мета роботи:
Вивчити побудову та застосування до розв’язання прикладних задач динамічних структур даних.
Теоретична частина
Абстрактний тип даних
Абстрактний тип даних (АТД) - це тип даних, який надає для роботи з елементами цього типу певний набір функцій, а також можливість створювати елементи цього типу за допомогою спеціальних функцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення - в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних звичайно представляються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних стараються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Черга
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.
Завдання
Побудова АТД
Змоделювати абстрактний тип даних (АТД) , який використати в Завданні 4. Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Алгоритм розв’язання задачі:
// queue1.h
#define queue 5
class Tqueue
{
private:
int data[queue]; // масив елементів черги
int first,last,count; // змінні початок, кінець, і лічильник
public:
bool EMPTY, FULL; // Булеві змінні для визначення чи черга пуста, чи повна
// EMPTY повертає значення true якщо черга пуста, в іншому випадку false
// FULL повертає значення true якщо черга повна, в іншому випадку false
Tqueue();
void push(int); // додає новий елемент до черги
void pop(); // вилучає елемент із черги
int front(); // повертає значення елемента з початку черги, але не вилучає //його
};
// queue1.cpp
#include "queue1.h"
#include <iostream>
using namespace std;
Tqueue::Tqueue()
{
first=0,last=-1,count=0;
EMPTY=true, FULL=false;
}
void Tqueue::push(int item)
{
if(FULL==false)
{
data[++last]=item;
++count;
EMPTY=false;
if(count==queue)
FULL=true;
};
}
void Tqueue::pop()
{
if(EMPTY==false)
{
for(int i=0;i<(count-1);i++)
data[i]=data[i+1];
count--;last--;
if(count==0)EMPTY=true;
}
}
int Tqueue::front()
{
return (data[first]);
}
// main.cpp
#include <conio.h>
#include <iostream>
#include "queue1.h"
using namespace std;
void print(Tqueue q)
{
Tqueue tmp;
tmp=q;
cout<<"Dunamika:";
if(q.EMPTY==true)
cout<<"Queue is EMPTY\n";
else
{
cout<<"{ ";
while(tmp.EMPTY==false)
{
cout<<tmp.front()<<" ";
tmp.pop();
}cout<<"}\n";
}
}
int main()
{
Tqueue a;
int i,b,c,mm,k=0,m=1;
cout<<"Killist elementiv cherhy: ";
cin>>b;
for(i=0;i<b;i++)
{
cout<<"Vvedit ["<<i+1<<"] element: ";
cin>>c;
if(c%2==0)
{
if(a.FULL==true)
{
cout<<"queue overflow\n";
}
else a.push(c);
}
if(c%2==1)
{
if(a.EMPTY==true)
{
cout<<"queue underflow\n";
}
else a.pop();}
print(a);
}
getch();
return 0;
}
Результат виконання програми:
/
Рис. 1. Ескіз вікна з результатом виконання програми.
Висновок: Виконавши дану лабораторну роботу, я зрозумів що собою являє абстрактний тип даних, а також як працює і реалізовується АТД "Черга" .
14.04.2015 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора