Разработка визуализатора
Оглавление
Введение
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
Извлечение
Извлечение элемента из очереди выполняется просто. Из массива извлекается
первый элемент, и весь массив смещается влево, а последний элемент удаляется.
{ Извлечение элемента из очереди }Qretrieve:EvtType;rpos=spos then('No
appointments scheduled.);:= '';else:= rpos+1;:= event[rpos-1];;;
На практике в односвязных списках используется преимущественно операция
удаления элемента, следующего за данным, так как проход по всему списку -
слишком дорогостоящая операция. Получается, также, что мы не можем быстро
удалить текущий элемент. [2]
массив
алгоритм интерфейс данные
1.5 Анализ
сложности алгоритма
Пространственная сложность - О(n) т.е. линейная зависимость от размера
очереди. Удвоение размера задачи удвоит и необходимое время. Сложность обычной
вставки О(1) (Устойчивое время работы не зависит от размера задачи).[3]
1.6 Класс входных данных, для которых применим алгоритм или структура
Входными данными в данном алгоритме могут выступать любые натуральные
числа. При написании программы и её тестирования использовались данные целого
типа integer, в диапазоне значений -2147483648 … 2147483647.
1.7 Примеры
практических задач, где может использоваться данный алгоритм
Очередь в программировании используется, как и в реальной жизни, когда
нужно совершить какие-то действия в порядке их поступления, выполнив их
последовательно. Примером может служить организация событий в Windows. Когда
пользователь оказывает какое-то действие на приложение, то в приложении не
вызывается соответствующая процедура (ведь в этот момент приложение может
совершать другие действия), а ему присылается сообщение, содержащее информацию
о совершенном действии, это сообщение ставится в очередь, и только когда будут
обработаны сообщения, пришедшие ранее, приложение выполнит необходимое
действие.
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно
длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на
первый незанятый элемент.
2. Разработка визуализатора
.1 Выбор
средств разработки
В качестве средства разработки был выбран объектно-ориентированный язык
высокого уровня Delphi, как не единственный, а более освоенный изученный
объектно-ориентированный язык программирования.
2.2
Определение отображаемых элементов, проектирование интерфейса
Разработка и проектирование интерфейса были продуманы и реализованы в
ходе выполнения курсовой работы.
Для создания интерфейса в среде разработки Delphi7 были выбраны следующие
элементы:
1. Label -для создания надписей и элементов графики.
. Edit - для вводимых пользователем значений.
. Button - клавиши управления.
. StringGrid - для отображения массива.
.3 Разработка
алгоритмов прямого пошагового выполнения визуализации и выполнения отката
//Запись очереди в таблицу типа TStringGrid.QueueToSg(const aQueue :
TQueue; aSg : TStringGrid);,j : Integer;.Rows[0].Clear;.Rowcount:=2;aQueue.Cnt
= 0 then begin.ColCount :=1;.Cells[0, 0] := '';else begin.ColCount :=
aQueue.cnt;i := 0 to aQueue.cnt-1 do.Cells[i, 0] :=aQueue.Arr[i];;j := 0 to
aQueue.Cnt do asg.Cells[j,1]:='...';aQueue.start<>-1
then.Cells[aQueue.start,1]:='start';.Cells[aQueue.ent,1]:='end';aQueue.start=aQueue.ent
then asg.Cells[aQueue.ent,1]:='start end';;(aQueue.free<>-1) and
(aQueue.cnt=0) then.Cells[aQueue.free,1]:='free';;enq(var aQueue : TQueue;
const aData : TData);:integer;aQueue do begincnt<length(arr) then
begin(cnt);[cnt-1]:=adata;(ent);start=-1 then inc(start);cnt=length(arr)
then:=-1inc(free);else.edit3.text:=arr[start];[start]:=adata;(start);:=start-1;start>length(arr)-1
then start:=0;;;;
Блок-схема алгоритма процедуры представлена в Приложении 1 и 2
.4
Особенности программной реализации
Для удобства реализации программы был выбран элемент Delphi10 stringrid -
таблица. В нее выводится очередь для того чтобы показать какие элементы
находятся сейчас в очереди.
2.5 Методика
и результаты тестирования
Для начала необходимо ввести рандом чисел. По умолчанию он равен 5.
Затем, при нажатии на кнопку рандом чисел числа меняются. Затем мы можем
извлечь число из начала очереди. Для этого нам надо нажать кнопку извлечь
элемент. Для вставки элемента в очередь необходимо ввести число и нажать кнопку
вставить элемент . Так же мы можем добавить или уменьшить количество элементов
в очереди.
Тестирование.
1). Зададим рандом из 5 чисел.
). Увеличим очередь.
). Добавим число.
). Извлечём число.
Программа работает исправно.
Заключение
В данной курсовой работе была реализована очередь на основе циклического
массива. В ходе выполнения были изучены алгоритмы удаления, вставки в массиве.
Так же была разработана программа на языке высокого уровня Delphi,
предназначенная для визуализации процесса работы данных алгоритмов. Цель моей
работы - написать алгоритм, который будет отображать реализацию очереди, была
достигнута в данной работе.
Источники
1. Односвязный
список [Электронный ресурс]://веб-информ.рф/C++/6/22/2205
. Бакнелл
Д. Фундаментальные алгоритмы и структуры данных в Delphi. Изд.дом ДиаСофтЮП,
2003
3. Списки [электронный
ресурс] <#"783926.files/image002.gif">
Приложение 2
Блок схема функции push
