Разработка визуализатора

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Оглавление

Введение

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.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 ()

Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди.

В данном курсовом проекте рассматривается организация очереди на основе массива.

1.3 Вставка структур

Программный пример представляет процедуру, выполняющую вставку элемента в любое место очереди.

{ Вставка элемента в очередь }

Const

MAX_EVENT = 100;

Type

EvtType = string[80];

Var

event: array[1. MAX_EVENT] of EvtType;

spos, rpos, t: integer;

ch: char;

done: boolean;

{ добавить в очередь }

procedure Qstore (q: EvtType);

begin

if spos=MAX_EVENT then

WriteLn ('List full')

Else

Begin

event[spos] := q;

spos := spos+1;

end;

end; End.

1.4 Извлечение

Извлечение элемента из очереди выполняется просто. Из массива извлекается первый элемент, и весь массив смещается влево, а последний элемент удаляется.

{ Извлечение элемента из очереди }

function Qretrieve: EvtType;

begin

if rpos=spos then

begin

WriteLn ('No appointments scheduled.);

Qretrieve := '';

end else

begin

rpos := rpos+1;

Qretrieve := event[rpos-1];

end;

end;

На практике в односвязных списках используется преимущественно операция удаления элемента, следующего за данным, так как проход по всему списку — слишком дорогостоящая операция. Получается, также, что мы не можем быстро удалить текущий элемент. [2]

массив алгоритм интерфейс данные

1. 5 Анализ сложности алгоритма

Пространственная сложность — О (n) т. е. линейная зависимость от размера очереди. Удвоение размера задачи удвоит и необходимое время. Сложность обычной вставки О (1) (Устойчивое время работы не зависит от размера задачи). 3]

1.6 Класс входных данных, для которых применим алгоритм или структура

Входными данными в данном алгоритме могут выступать любые натуральные числа. При написании программы и её тестирования использовались данные целого типа integer, в диапазоне значений -2 147 483 648 … 2 147 483 647.

1.7 Примеры практических задач, где может использоваться данный алгоритм

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.

2. Разработка визуализатора

2. 1 Выбор средств разработки

В качестве средства разработки был выбран объектно-ориентированный язык высокого уровня Delphi, как не единственный, а более освоенный изученный объектно-ориентированный язык программирования.

2.2 Определение отображаемых элементов, проектирование интерфейса

Разработка и проектирование интерфейса были продуманы и реализованы в ходе выполнения курсовой работы.

Для создания интерфейса в среде разработки Delphi7 были выбраны следующие элементы:

1. Label -для создания надписей и элементов графики.

2. Edit — для вводимых пользователем значений.

3. Button — клавиши управления.

4. StringGrid — для отображения массива.

2. 3 Разработка алгоритмов прямого пошагового выполнения визуализации и выполнения отката

//Запись очереди в таблицу типа TStringGrid.

procedure QueueToSg (const aQueue: TQueue; aSg: TStringGrid);

var

i, j: Integer;

begin

aSg. Rows[0]. Clear;

aSg. Rowcount:=2;

if aQueue. Cnt = 0 then begin

aSg. ColCount: =1;

aSg. Cells[0, 0] := '';

end else begin

aSg. ColCount := aQueue. cnt;

for i := 0 to aQueue. cnt-1 do

aSg. Cells[i, 0]: =aQueue. Arr[i];

end;

for j := 0 to aQueue. Cnt do asg. Cells[j, 1]:='… ';

if aQueue. start<>-1 then

begin

asg. Cells[aQueue. start, 1]:='start';

asg. Cells[aQueue. ent, 1]:='end';

if aQueue. start=aQueue. ent then asg. Cells[aQueue. ent, 1]:='start end';

end;

if (aQueue. free<>-1) and (aQueue. cnt=0) then

asg. Cells[aQueue. free, 1]:='free';

end;

procedure enq (var aQueue: TQueue; const aData: TData);

var

j: integer;

begin

with aQueue do begin

if cnt< length (arr) then begin

inc (cnt);

arr[cnt-1]: =adata;

inc (ent);

if start=-1 then inc (start);

if cnt=length (arr) then

free: =-1

ELSE inc (free);

end else

begin

form1. edit3. text:=arr[start];

arr[start]: =adata;

inc (start);

ent: =start-1;

if start> length (arr)-1 then start: =0;

end;

end;

end;

//Изъятие элемента из начала очереди.

function popr (var aQueue: TQueue): string;

var

i, j: Integer;

begin

if aQueue. cnt=0 then exit;

popr: =aQueue. arr[aQueue. start];

aQueue. arr[aQueue. start]:='';

aQueue. free:=aQueue. start;

if aQueue. cnt<>0 then

with aQueue do begin

if start=ent then

begin

start: =-1;

ent: =-1;

cnt: =0;

free: =0;

end;

if start=0 then begin

for i := 0 to cnt-2 do

arr[i]: =arr[i+1];

aQueue. arr[aQueue. Cnt-1]:='';

dec (ent);

dec (cnt);

end;

if start> ent then begin

for i := start to cnt-2 do

arr[i]: =arr[i+1];

aQueue. arr[aQueue. Cnt-1]:='';

dec (cnt);

end;

if start=cnt then begin

start: =0;

end; end;

Блок-схема алгоритма процедуры представлена в Приложении 1 и 2

2.4 Особенности программной реализации

Для удобства реализации программы был выбран элемент Delphi10 stringrid — таблица. В нее выводится очередь для того чтобы показать какие элементы находятся сейчас в очереди.

2.5 Методика и результаты тестирования

Для начала необходимо ввести рандом чисел. По умолчанию он равен 5. Затем, при нажатии на кнопку рандом чисел числа меняются. Затем мы можем извлечь число из начала очереди. Для этого нам надо нажать кнопку извлечь элемент. Для вставки элемента в очередь необходимо ввести число и нажать кнопку вставить элемент. Так же мы можем добавить или уменьшить количество элементов в очереди.

Тестирование.

1). Зададим рандом из 5 чисел.

2). Увеличим очередь.

3). Добавим число.

4). Извлечём число.

Программа работает исправно.

Заключение

В данной курсовой работе была реализована очередь на основе циклического массива. В ходе выполнения были изучены алгоритмы удаления, вставки в массиве. Так же была разработана программа на языке высокого уровня Delphi, предназначенная для визуализации процесса работы данных алгоритмов. Цель моей работы — написать алгоритм, который будет отображать реализацию очереди, была достигнута в данной работе.

Источники

1. Односвязный список [Электронный ресурс]

http: //веб-информ. рф/C++/6/22/2205

2. Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Изд. дом ДиаСофтЮП, 2003

3. Списки [электронный ресурс] http: //ru. wikipedia. org/

4. Макконнелл Дж. Основы современных алгоритмов М.: Техносфера, 2004

Приложение 1

Блок схема функции popr.

Приложение 2

Блок схема функции push

ПоказатьСвернуть
Заполнить форму текущей работой