Министерство образования и науки Российской Федерации
Государственно-образовательное учреждение
высшего профессионального образования
Вологодский государственный университет
Кафедра: Автоматики и вычислительной техники
Дисциплина: Построение и анализ алгоритмов
Пояснительная записка
Очередь в циклическом массиве.
Выполнил: Чегодаев А.П
Группа ЭМ-11
Проверил: Андрианов И.А.
Вологда
2014 Г.
Оглавление
Введение 3
1. Очередь в циклическом массиве. 3
1.1. Описание работы алгоритма 3
1.2. Способы построения 3
1.3. Вставка структур 5
1.4. Извлечение. 6
1.5. Анализ сложности алгоритма 6
1.6. Класс входных данных, для которых применим алгоритм или структура 7
1.7. Примеры практических задач, где может использоваться данный алгоритм. 7
2. Разработка визуализатора. 7
2.1. Выбор средств разработки 7
2.2. Определение отображаемых элементов, проектирование интерфейса 8
2.3. Разработка алгоритмов прямого пошагового выполнения визуализации и выполнения отката 8
2.4. Особенности программной реализации 10
2.5. Методика и результаты тестирования 10
Тестирование. 11
Заключение. 12
Источники 13
Приложение 1. 14
Приложение 2. 15
Введение 4
1. Очередь в циклическом массиве. 4
1.1. Описание работы алгоритма 4
1.2. Способы построения 4
1.3. Вставка структур 6
1.4. Извлечение. 7
1.5. Анализ сложности алгоритма 7
1.6. Класс входных данных, для которых применим алгоритм или структура 8
1.7. Примеры практических задач, где может использоваться данный алгоритм. 8
2. Разработка визуализатора. 8
2.1. Выбор средств разработки 8
2.2. Определение отображаемых элементов, проектирование интерфейса 9
2.3. Разработка алгоритмов прямого пошагового выполнения визуализации и выполнения отката 9
2.4. Особенности программной реализации 11
2.5. Методика и результаты тестирования 11
Тестирование. 12
Заключение. 13
Источники 14
Приложение 1. 15
Приложение 2. 16
Введение
Независимо от типа решаемых задач, любая программа оперирует какими-то данными, а сама программа представляет собой методы управления и обработки этих данных. Существует множество разных алгоритмов организации данных, одной из них является очередь. Для лучшего понимания алгоритмов создают специальные визуализаторы, демонстрирующие принцип действия заданного алгоритма в данной курсовой работе разрабатывается визуализатор очереди в циклическом массиве.
1. Очередь в циклическом массиве.
1.1. Описание работы алгоритма
Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
1.2. Способы построения
Существует несколько способов реализации очереди в языках программирования.
Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end. Представлен на рисунке:
рис.1.2.1
Обычно 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()
Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди.
В данном курсовом проекте рассматривается организация очереди на основе массива.