Зміст
Введення
1. Черга в циклічному масиві.
1.1 Опис роботи алгоритму
1.2 Способи побудови
1.3 Вставка структур
1.4 Витяг.
1.5 Аналіз складності алгоритму
1.6 Клас вхідних даних, для яких застосуємо алгоритм або структура
1.7 Приклади практичних завдань, де може використовуватися даний алгоритм.
2. Розробка визуализатора.
2.1 Вибір засобів розробки
2.2 Визначення відображаються елементів, проектування інтерфейсу
2.3 Розробка алгоритмів прямого покрокового виконання візуалізації та виконання відкоту
2.4 Особливості програмної реалізації
2.5 Методика і результати тестування
Тестування.
Висновок.
Джерела
Додаток 1.
Додаток 2.
Введення
Незалежно від типу розв'язуваних завдань, будь-яка програма оперує якимись даними, а сама програма є методи управління і обробки цих даних. Існує безліч різних алгоритмів організації даних, однією з них є черга. Для кращого розуміння алгоритмів створюють спеціальні візуалізатори, що демонструють принцип дії заданого алгоритму в даній роботі розробляється визуализатор черзі в циклічному масиві.
1. Черга в циклічному масиві
. 1 Опис роботи алгоритму
Черга - структура даних з дисципліною доступу до елементів" перший прийшов - першим вийшов» (FIFO, First In - First Out). Додавання елемента (прийнято позначати словом enqueue - поставити в чергу) можливе лише в кінець черги, вибірка - тільки з початку черги (що прийнято називати словом dequeue - прибрати з черги), при цьому обраний елемент з черги видаляється.
. 2 Способи побудови
Існує кілька способів реалізації черги в мовах програмування.
Перший спосіб являє чергу у вигляді масиву і двох цілочисельних змінних start і end. Представлений на малюнку:
ріс.1.2.1
Зазвичай start вказує на голову черги, end - на елемент, який заповниться, коли в чергу увійде новий елемент. При додаванні елемента в чергу в q [end] записується новий елемент черги, а end зменшується на одиницю. Якщо значення end стає менше 1, то ми як би циклічно обходимо масив і значення змінної стає рівним n. Витяг елемента з черги проводиться аналогічно: після вилучення елемента q [start] з черги змінна start зменшується на 1. З такими алгоритмами одна комірка з n завжди буде незайнятої (так як черга сn елементами неможливо відрізнити від порожній), що компенсується простотою алгоритмів.
Переваги даного методу: можлива незначна економія пам'яті в порівнянні з другим способом; простіше в розробці.
Недоліки: максимальна кількість елементів у черзі обмежена розміром масиву. При його переповненні вимагається перевиделеніе пам'яті і копіювання всіх елементів в новий масив.
Другий спосіб заснований на роботі з динамічною пам'яттю. Черга представляється як лінійного списку, в якому додавання/видалення елементів йде строго з відповідних його кінців.
Переваги даного методу: розмір черги обмежений лише обсягом пам'яті.
Недоліки: складніше в розробці; потрібно більше пам'яті; при роботі з такою чергою пам'ять сильніше фрагментується; робота з чергою трохи повільніше.
Черга може бути побудована з двох стеків S1 і S2 як показано нижче:
Процедура enqueue (x) :. push (x)
Процедура dequeue ():
якщо S2 порожній:
якщо S1 порожній:
повідомити про помилку: черга порожня
поки S1 не пустили: .push (S1.pop ()) S2.pop ()
Такий спосіб реалізації найбільш зручний в якості основи для побудови персистентной черги.
У даному курсовому проекті розглядається організація черзі на основі масиву.
. 3 Вставка структур
Програмний приклад представляє процедуру, що виконує вставку елемента в будь-яке місце черги.
{Вставка елемента в чергу} _EVENT=100; =String [80] ;: array [1..MAX_EVENT] of EvtType ;, rpos, t: integer;: char;: boolean;
{додати в чергу} Qstore (q: EvtType); spos=MAX_EVENT then ( List full ) [spos]:=q;:=spos + 1 ;;; End.
1.4 Витяг
Витяг елемента з черги виконується просто. З масиву витягується перший елемент, і весь масив зміщується вліво, а останній елемент видаляється.
{Витяг еле...
