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

Описание работы алгоритма

 

Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел» (FIFO, First In - First Out). Добавление элемента (принято обозначать словом enqueue - поставить в очередь) возможно лишь в конец очереди, выборка - только из начала очереди (что принято называть словом dequeue - убрать из очереди), при этом выбранный элемент из очереди удаляется.

Способы построения

 

Существует несколько способов реализации очереди в языках программирования.

Первый способ представляет очередь в виде массива и двух целочисленных переменных 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()

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

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

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

 

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

{ Вставка элемента в очередь }_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.

Извлечение

 

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

{ Извлечение элемента из очереди }Qretrieve:EvtType;rpos=spos then('No appointments scheduled.);:= '';else:= rpos+1;:= event[rpos-1];;;

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

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

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

 

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

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

 

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

 

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

 

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

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

 

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

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

 

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

 

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

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

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

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

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

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

Заключение

 

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

 

   
Источники

 

1. Односвязный список [Электронный ресурс]://веб-информ.рф/C++/6/22/2205

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

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

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

   
Приложение 1

 

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

 

   
Приложение 2

 

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

Описание работы алгоритма

 

Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел» (FIFO, First In - First Out). Добавление элемента (принято обозначать словом enqueue - поставить в очередь) возможно лишь в конец очереди, выборка - только из начала очереди (что принято называть словом dequeue - убрать из очереди), при этом выбранный элемент из очереди удаляется.

Способы построения

 

Существует несколько способов реализации очереди в языках программирования.

Первый способ представляет очередь в виде массива и двух целочисленных переменных 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()

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

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

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

 

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

{ Вставка элемента в очередь }_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.

Извлечение

 

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

{ Извлечение элемента из очереди }Qretrieve:EvtType;rpos=spos then('No appointments scheduled.);:= '';else:= rpos+1;:= event[rpos-1];;;

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

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

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

 

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

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

 

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

 

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

 

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

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

 

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

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

 

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