Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Застосування АТД
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
про виконання лабораторної роботи № 2
з дисципліни: “Обчислювальний практикум”
на тему: “ Застосування АТД "Черга" до розв’язання прикладних задач”
Львів 2013
Мета: Ознайомитись з АТД «Черга»
Теоретичні відомості:
Черга - структура даних з дисципліною доступу до елементів "перший прийшов - перший вийшов" ( FIFO, First In - First Out). Додавання елемента (прийнято позначати словом enqueue - поставити в чергу) можливо лише в кінець черги, вибірка - тільки з початку черги (що прийнято називати словом dequeue - прибрати з черги), при цьому обраний елемент з черги видаляється.
Способи реалізації черги
Існує кілька способів реалізації черзі в мовах програмування.
Масив
Перший спосіб являє чергу у вигляді масиву і двох цілочисельних змінних start і end. / Зазвичай start вказує на голову черги, end - на елемент, який заповниться, коли в чергу увійде новий елемент. При додаванні елемента в чергу в q[end]записується новий елемент черги, а end зменшується на одиницю. Якщо значення end стає менше 1, то ми як би циклічно обходимо масив і значення змінної стає рівним n. Витяг елемента з черги проводиться аналогічно: після вилучення елемента q[start] з черги змінна start зменшується на 1. З такими алгоритмами один осередок з n завжди буде незайнятої (так як черга з n елементами неможливо відрізнити від порожньої), що компенсується простотою алгоритмів.
Переваги даного методу: можлива незначна економія пам'яті в порівнянні з другим способом; простіше в розробці.
Недоліки: максимальна кількість елементів в черзі обмежене розміром масиву. При його переповненні потрібно перевиделеніе пам'яті і копіювання всіх елементів в новий масив
Зв'язний список
Другий спосіб заснований на роботі з динамічною пам'яттю. Чергу представляється в якості лінійного списку, в якому додавання / видалення елементів йде строго з відповідних його кінців.
Переваги даного методу: розмір черги обмежений лише обсягом пам'яті.
Недоліки: складніше в розробці; потрібно більше пам'яті; при роботі з такою чергою пам'ять сильніше фрагментируется; робота з чергою трохи повільніше.
Реалізація на двох стеках
Чергу може бути побудована з двох стеков S1 і S2 як показано нижче:
Процедура enqueue (x): S1.push (x) Процедура dequeue (): якщо S2 порожній: якщо S1 порожній: повідомити про помилку: черга порожня поки S1 не порожній: S2.push (S1.pop ()) return S2.pop ()
Такий спосіб реалізації найбільш зручний в якості основи для побудови персистентной черзі.
Застосування черг
Черга в програмуванні використовується, як і в реальному житті, коли потрібно зробити якісь дії в порядку їх надходження, виконавши їх послідовно. Прикладом може служити організація подій у Windows. Коли користувач надає якусь дію на додаток, то в додатку не викликається відповідна процедура (адже в цей момент додаток може вчиняти інші дії), а йому надсилається повідомлення, що містить інформацію про скоєний дії, це повідомлення ставиться в чергу, і тільки коли будуть оброблені повідомлення, що прийшли раніше, додаток виконає необхідну дію.
Клавіатурний буфер BIOS організований у вигляді кільцевого масиву, зазвичай довжиною в 16 машинних слів, і двох покажчиків: на наступний елемент у ньому і на перший незайнятий елемент.
Завдання:
Автостоянка має одну полосу, на якій може бути розмiщено до 10 автомобiлiв. Машини в'їжджають з пiвденного кiнця стоянки i від'їжджають з пiвнiчного. Якщо автомобiль власника, що прийшов на стоянку забрати його, не розташований пiвнiчнiше за всі решту, то всi автомобiлi, що стоять пiвнiчнiше його, виїжджають iз зупинки, потiм виїжджає його машина і всі машини повертаються в початковому порядку. Якщо машина залишає гараж, то всi машини розташованi пiвденнiше, перемiщаються вперед на стiльки позицій, скiльки є вiльних мiсць в пiвнiчнiй частинi. Написати програму зчитування групи рядків, кожний з яких мiстить літеру "A" для прибуття i літеру "D" для вiдправлення, а також номер машини. Машини прибувають i вiдправляються в порядку, що задає цей список рядків. Програма має видавати повiдомлення при кожному прибутті або вiдправленні машини. При прибутті машини в ньому повинно говоритись, чи є на стоянці вiльне мiсце. Якщо вiльне мiсце вiдсутнє, машина чекає до тих пiр, поки воно не звiльниться, або до моменту зчитування рядка, що повідомляє про вiдправлення цього автомобiля. Якщо з'являється вiльне мiсце, повинно видаватись iнше повiдомлення. При вiдправленнi автомобiля повiдомлення повинно мiстити в собi кiлькiсть перемiщень машини в серединi стоянки (включаючи її вiдправлення, але не прибуття; це число рiвне 0, якщо машина була вiдправлена під час очiкування вільного місця).
Текст програми:
Main.cpp
#include <queue>
#include <deque>
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
setlocale(LC_ALL,"Russian");
queue<int>garage;
int numbers_of_all_cars; // число всіх машин
int number_of_the_car; // номер машини в черзі
int elements=0; // елементи(машини)
cout<<"Введiть кiлькiсть машин: ";
cin>>numbers_of_all_cars;
if(numbers_of_all_cars>10)
{cout<<"На парковцi тiльки 10 мiсць."<<endl;
abort();}
cout<<"\nВ гаражi "<<numbers_of_all_cars<<" машин:"<<endl;
for (int i=0; i<numbers_of_all_cars; i++)
garage.push(elements=elements+1); // добавляем элементи (машини) в чергу
queue <int> newgarage = garage;
while (!newgarage.empty())
{ cout<< newgarage.front()<<" ";
newgarage.pop();}
cout << "\nПерший елемент черги: " << garage.front()<<endl;
cout << "Останнiй елемент черги: " << garage.back()<<endl;
cout<<"\nНомер машини, котра покидає гараж: ";
cin>>number_of_the_car;
cout<<"\nВсi машини, перед вибраною № "<<number_of_the_car<<", виїхали з черги та заїхали з iншого кiнця:"<<endl;
while(garage.front()!=number_of_the_car)
{
garage.push(garage.front());
garage.pop();
}
garage.pop();
queue <int> newgarage2 = garage;
while (!newgarage2.empty())
{ cout<< newgarage2.front()<<" ";
newgarage2.pop();}
cout << "\nПерший елемент черги: " << garage.front()<<endl;
cout << "Останнiй елемент черги: " << garage.back()<<endl;
_getch();
}
Результат виконання програми:
/
Висновок: на цій лабораторній роботі я ознайомився із АТД «СПИСОК» і навчився застосовуати його у практичних задачах.
03.04.2018 21:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора