Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних ЧЕРГА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних ЧЕРГА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 4
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2012
Методичні вказівки до лабораторної роботи "Структура даних ЧЕРГА" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А. Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2012 – 12 с.
Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Приклад :
В послідовності 8 2 6 3 1 4 9 кожна парна цифра визначає операцію push (додавання цієї цифри в чергу), а кожна непарна цифра визначає операцію pop (вилученя з черги одного елемента).
Введемо такі позначення: P – покажчик початку черги, К – покажчик кінця черги
Наведемо динаміку вмісту черги під час обробки заданої послідовності:
K P
0)
- порожня черга
P K
P K
P K
1)
8
2)
8
2
3)
8
2
6
P K
P K
P K
4)
2
6
5)
6
6)
6
4
P K
7)
4
Оскільки черга - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас queue, для використання якого потрібно включити заголовочний файл:
# include <queue>
Набір стандартних операцій роботи з чергою показаний у таблиці:
Операція
Дія
push(іtem)
Поміщає новий елемент у кінець черги
pop()
Вилучає елемент з черги, але не повертає його значення
front()
Повертає значення елемента з початку черги, але не вилучає його
empty()
Повертає true, якщо черга порожня, і false у противному випадку
sіze()
Повертає кількість елементів у черзі
Розглянемо статичну реалізацію черги на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу queue, аналогічний класу queue зі стандартної бібліотеки шаблонів STL.
// ФАЙЛ: queue1.h (частина простору імен main_savitch_8B)
#ifndef MAIN_SAVITCH_QUEUE1_H
#define MAIN_SAVITCH_QUEUE1_H
#include <cstdlib> // Provides size_t
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( );
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ
void pop( );
void push(const Item& entry);
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ
bool empty( ) const { return (count == 0); }
Item front( ) const;
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; }
};
}
#include "queue1.template" // Директива включення реалізації.
#endif
Файл реалізації класу queue показаний в наступному лістінгу:
#include <cassert> // Надає макрос assert.
namespace main_savitch
{
template <class Item>
const typename queue<Item>::size_type queue<Item>::CAPACITY;
template <class Item>
queue<Item>::queue( )
{
count = 0;
first = 0;
last = CAPACITY - 1;
}
template <class Item>
Item queue<Item>::front( ) const
{
assert(!empty( ));
return data[first];
}
template <class Item>
void queue<Item>::pop( )
{
assert(!empty( ));
first = next_index(first);
--count;
}
template <class Item>
void queue<Item>::push(const Item& entry)
{
assert(size( ) < CAPACITY);
last = next_index(last);
data[last] = entry;
++count;
}
}
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
4.1. Вибір варіанта індивідуального завдання
№ варіанта = [(день народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1
4.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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
1. Змоделювати циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по зростанню, чи ні.
2. Змоделювати чергу, в якій до опису черги додано дві змінні EMPTY та FULL замість функцій empty() та full() відповідно. Переписати основні функції роботи з чергою з врахуванням цих змінних. Показати динаміку вмісту черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі три однакових елемента, що йдуть підряд.
3. Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності змінити порядок слідування елементів в деку на протилежний.
4. Змоделювати чергу, в якій покажчик кінця черги вказує не на останній елемент черги, а на перший вільний елемент масиву. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по спаданню, відсортовані по зростанню або невідсортовані.
5. Змоделювати чергу, в якій задається початок черги і довжина черги (замість кінця черги). Після обробки всієї заданої вхідної послідовності знайти найбільший непарний елемент черги.
6. Змоделювати дек, в якому до опису деку додано дві функції commute_left та commute_right, які заміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції вилучення в лівому або в правому кінці деку опиниться число меньше за 10, то треба подвоїти його значення. Після обробки всієї заданої вхідної послідовності збільшити в два раза значення кожного елемента черги.
7. Змоделювати чергу за допомогою масиву INFO[N], де INFO[0], а не окрема змiнна, використовується для зберiгання початку черги, INFO[N-1], а не окрема змiнна, використовується для зберiгання кінця черги; решта елементів масиву можуть містити елементи самої черги. Після обробки всієї заданої вхідної послідовності перевірити, чи буде в черзі непарна кількість елементів, чи ні.
8. Змоделювати чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву. Після обробки всієї заданої вхідної послідовності визначити, чи сума всіх парних чисел черги буде більшою за суму непарних, чи ні.
9. Змоделювати чергу, в якій до опису черги додано змінну EMPTY замість функції empty(). Переписати основні функції роботи з чергою з врахуванням цієї змінної. Після обробки всієї заданої вхідної послідовності знайти довжину найбільш довгої послідовності однакових елементів черги, що йдуть підряд.
10. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності продублювати всі елементи дека (тобто замість кожного одного елемента має стати підряд два однакових).
11. Змоделювати чергу з пріоритетами. Новий елемент додається завжди в кінець черги, а при вилученні елемента в черзі шукається (цей пошук може бути тільки послідовним) елемент із максимальним пріоритетом і після цього він вилучається з черги. На вході задається послідовність слів. Пріоритет визначається як довжина слова. Якщо слово починається з великої літери, то воно додається в чергу, якщо з малої, то з черги вилучається один елемент. Після обробки всієї заданої вхідної послідовності визначити найбільшу кількість елементів з однаковим пріоритетом.
12. Змоделювати чергу, в якій замість двох функцій pop і front використовується тільки одна функція pop, яка робить ці дві дії одночасно, тобто і вилучає елемент зі стека, і повертає його значення. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі два однакових елемента, що йдуть підряд.
13. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності визначити, чи є в черзі хоча б одне число менше за 7.
14. Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа.
15. Змоделювати чергу, в якій до опису черги додано змінну FULL замість функції full(). Переписати основні функції роботи з чергою з врахуванням цієї змінної. Показати динаміку вмісту черги. Після обробки всієї заданої вхідної послідовності знайти кількість елементів черги, які більші за своїх сусідів.
16. Змоделювати дек, в якому до опису деку додано дві функції commute_left та commute_right, які заміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції додавання в лівому або в правому кінці деку опиниться число більше за 50, то треба, використовуючи функції commute_left або commute_right, замінити його значення на число 10. Після обробки всієї заданої вхідної послідовності перевірити, чи буде дек “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.).
17. Написати програму, у якій числа вхідної послідовності циклічно розподіляються по трьом чергам. Всі додатні числа додаються в чергу, а кожне від'ємне число вилучає з черги один елемент. Після обробки всієї заданої вхідної послідовності визначити найбільший елемент кожної черги.
18. Змоделювати чергу за допомогою двох стеків. Додавання елемента до черги зводиться до додавання до одного зі стеков, а перевірка, чи черга порожня - до перевірки, чи порожні обидва стеки. При вилученні елемента з черги можливі два випадки. Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається автоматично при перекладанні елементів з одного стеку в інший) і далі задача зводиться до першого випадку.
19. Змоделювати дек, в якому до опису деку додано функцію change, яка міняє значення елементів, що знаходяться в лівому та в правому кінцях деку. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба обміняти значення лівого і правого кінців деку. Після обробки всієї заданої вхідної послідовності знайти суму парних чисел деку.
20. Змоделювати чергу з пріоритетами у якій послідовність елементів черги весь час підтримується впорядкованою, тобто кожний новий елемент додається на те місце в черзі, яке визначається його пріоритетом, а при вилученні завжди вибирається елемент з початку черги. На вході задається послідовність слів. Пріоритет визначається як довжина слова. Якщо слово починається з голосної літери, то воно додається в чергу, якщо з приголосної, то з черги вилучається один елемент. Після обробки всієї заданої вхідної послідовності знайти кількість елементів черги з пріоритетами більшими за 3.
21. Змоделювати дек з обмеженим виходом (тобто додавати в дек можна з обох кінців, а вилучати тільки з одного). Після обробки всієї заданої вхідної послідовності перетворити отриманий дек так, щоб він не містив однакових елементів, що йдуть підряд (тобто замість кожної послідовності однакових елементів має залишитись тільки один елемент, наприклад, з деку з вмістом 22230115555 треба отримати дек з вмістом 23015).
22. Змоделювати циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо. Після обробки всієї заданої вхідної послідовності перевірити, чи всі числа у черзі будуть парними, чи ні.
23. Змоделювати чергу з пріоритетами у якій послідовність елементів черги весь час підтримується впорядкованою, тобто кожний новий елемент додається на те місце в черзі, яке визначається його пріоритетом, а при вилученні завжди вибирається елемент з початку черги. На вході задається послідовність цілих чисел. Пріоритет кожного числа визначається як кількість ціфр у цьому числі. Додатні числа заносяться в чергу, а кожне від’ємне число вилучає з черги один елемент. Після обробки всієї заданої вхідної послідовності знайти найбільший елемент черги.
24. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності перевірити, чи є у деку три однакових числа, які йдуть підряд одне за одним.
25. Змоделювати чергу, в якій до опису черги додано функцію double, яка збільшує в два рази значення кожного елемента черги. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба подвоїти всі елементи черги. Після обробки всієї заданої вхідної послідовності визначити, чи є у черзі хоча б одне число менше за 10.
26. Змоделювати чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву. Після обробки всієї заданої вхідної послідовності знайти середнє арифметичне всіх елементів черги.
27. Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності визначити, чи є у черзі хоча б одне число, що містить тільки однакові цифри.
28. Змоделювати чергу за допомогою масиву, в якому перший елемент масиву, а не окрема змiнна, використовується для зберiгання початку черги і останній елемент масиву, а не окрема змiнна, використовується для зберiгання кінця черги; решта елементів масиву можуть містити елементи самої черги. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по спаданню, чи ні.
29. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності знайти три найбільших елемента черги.
30. Змоделювати чергу, в якій до опису черги додано функцію only, яка вилучає з черги всі елементи, значення яких співпадають з заданим значенням. Кожний раз після операції вилучення, якщо на початку черги опиняється парне число, то з черги вилучаються всі числа з таким самим значенням. Після обробки всієї заданої вхідної послідовності знайти сума всіх парних чисел, що залишились у черзі.
5. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи
2. Постановка задачі
3. Динаміка вмісту черги
3.1. Послідовність 10 цілих (додатніх, від'ємних, нульових, парних і непарних) чисел
3.2. Схематичне зображення черги після обробки кожного числа з вхідної послідовності
3.3. Вибрати один з варіантів у відповідності до завдання:
- перевірка умови (показати всі можливі випадки);
- знаходження суми, або добутку, або кількості, або довжини і т.д.;
- інше
4. Алгоритм розв’язання задачі
5. Результати виконання програми
Висновки
Додатки
IIІ. Змістовне наповнення пунктів:
Постановка задачі має містити повне завдання, тобто спільне завдання для всіх варіантів і індивідуальне завдання для свого вибраного варіанту.
В пункті динаміка вмісту черги (деку) схематичне зображення черги (деку) має відповідати умові індивідуального завдання.
В пункті алгоритм розв’язання задачі надається словесний опис основних прийомів, що використовуються для знаходження алгоритму та написання програми.
В пункті результати виконання програми показуються роздруковані копії екранів з результатами, які відображають всі зміни, що відбуваються у черзі або деку та містять всю необхідну інформацію в такому вигляді, щоб для перевірки правильності виконання програми не виникало необхідності додатково переглядати тексти програм.
В додатках розміщуються тексти програм з коментарями. Кожний додаток підписується, яка саме інформація в ньому надається.
7. КОНТРОЛЬНІ ЗАВДАННЯ
A
B
C
D
E
F
G
H
Go[0] Go[1] Go[2] Go[3] Go[4] Go[5] Go[6] Go[7]
1. На малюнку 1 зображений масив Go , покажчик початку черги Open і покажчик кінця черги Close, за допомогою яких задана черга My. Намалюйте схематичне зображення цієї черги.
2. Перемалюйте малюнок 1 після виконання такої операції: Push (’W’);
Open
1
Close
4
3. Перемалюйте малюнок 1 після виконання такої операції: Pop ();
Мал.1. Реалізація черги My на базі масиву Go
4. Для заданої на малюнку 1 черги My напишіть функцію додавання в чергу елемента X (дотримуйтесь назв згідно з малюнком ).
5. В послідовності 8 2 1 4 8 5 3 парна цифра означає операцію Push, а непарна цифра - операцію Pop. Намалюйте динаміку вмісту черги під час виконання цих операцій над порожньою спочатку чергою.
СПИСОК ЛІТЕРАТУРИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
ЗМІСТ
Мета роботи……………………………………..……………………………………………3
Теоретичні відомості..........….………………………………………………………….…. .3
Порядок виконання роботи..............………………………………………..……..………...5
Завдання на лабораторну роботу ....………………………………………..……..………...6
Вибір індивідуального завдання ...………………………………………………………… 9
Вимоги до оформлення звіту.......................……...……..…………………………………. 9
Контрольні завдання................………..……………………………………………………. 10
Список літератури ………...……….....................…………………………………………..10
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
"Структура даних СТЕК"
з дисципліни
“Програмування. Частина IIІ. Структури даних та алгоритми"
для підготовки студентів напряму
6.050102 “Комп’ютерна інженерія”
Укладач Т.А. Матвейчук, ст. викладач каф.ЕОМ
Редактор
Комп’ютерне складання
Підписано до друку 2012 р.
Формат 70 х 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......
Наклад ..... прим. Зам.
Поліграфічний центр
Видавництва Національного університету “Львівська політехніка”
вул. Колесси, 2, 79000, Львів
25.01.2013 01:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора