Сделай Сам Свою Работу на 5

Построение математической модели





Оглавление

Введение. 3

Постановка задачи. 4

Построение математической модели. 7

Разработка алгоритма. 9

Основной алгоритм.. 9

Запись в файл. 10

Очистка очереди. 10

Расширение массива. 11

Контрольные примеры.. 13

Запуск программы.. 13

Создание очереди. 13

После создания очереди. 14

Добавление элемента в очередь. 14

Успешное добавление. 15

Отмена добавления. 15

После добавления элемента. 15

Ситуация с несколькими элементами очереди. 16

Очистка очереди. 17

Печать. 17

Обработка элемента очереди. 18

Переполнение очереди. 20

Альтернативный вид интерфейса. 21

Реализация алгоритма. 22

Список использованной литературы.. 29


Введение

 

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

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



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


Постановка задачи

 

Конечной целью выполнения данной работы является создание графического приложения, демонстрирующего модель очереди на основе динамического массива.

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



Доступные операции с очередью:

· Удаление элемента

· Добавление элемента

· Очистка очереди

· Обработка элемента

· Печать очереди

· Просмотр элемента очереди по индексу

 

 


Анализ технической литературы

 

Для разработки модели очереди можно воспользоваться одной из двух наиболее распространенных методологий:

1. Построение очереди на основе динамического массива

2. Построение на основе связного списка

 

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.



Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.

В линейном списке каждый из элементов представляет собой некий объект класса, помимо данных содержащий в себе ссылку на следующий элемент (в случае односвязного списка) и на предыдущий (при двусвязном списке). Если очередь циклическая, то последний элемент содержит указатель на первый элемент последовательности.

Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

 


Построение математической модели

 

Логически очередь представляет собой некую последовательность объектов, которые обрабатываются в порядке старшинства, то есть, первый объект, добавленный в очередь, будет обработан первым.

За основу модели элемента очереди в данной работе берутся целые числа. Очередь является объектом класса, хранящим метки start и end, количество элементов.

Имеется некоторый набор процедур:

1. Удалить элемент из начала очереди

2. Добавить элемент в конец очереди

3. Очистить очередь

4. Создать новую очередь

5. Печатать очередь

6. Обработать элемент очереди

 

При создании очереди, ей можно задать фиксированный размер, если же он не указан, то, по умолчанию, он принимается равным единице.

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

При удалении необходимо проверять массив на пустоту, иначе может произойти исключительная ситуация, ведущая к ошибке.

Интерфейсная часть приложения, демонстрирующего модель очереди, выполнена на языке C# . Данный язык предоставляет широкие возможности настройки пользовательского интерфейса, стилизации и украшения внешнего вида приложения.

Логическая часть выполнена на языке C++, чтобы удовлетворять требованиям задания курсовой работы. Поскольку в языке C# программист работает с управляемым кодом, ему нет необходимости вручную выделять и освобождать память под объекты, так как это делается автоматически в процессе выполнения приложения. Задание курсовой работы требует именно динамического управления памятью для работы с массивом элементов очереди.

Таким образом, логическая часть выполнена в виде отдельного модуля, собранного в библиотеку DLL, подключаемую к интерфейсной части через ресурсы.

 


Разработка алгоритма

Основной алгоритм

 


Запись в файл

Очистка очереди

Расширение массива


Контрольные примеры

Запуск программы

 

Пользователь может создать новую очередь, переключиться на другой вид интерфейса (переключить вид) или закрыть программу, другие опции недоступны по причине невозможности произвести указанные действия с пустой очередью.

 

Создание очереди

 

После щелчка по кнопке «Создать очередь» появляется следующее окно, разрешающее пользователю ввести количество элементов будущей очереди. Невозможно ввести символы, кроме цифр, отличных от нуля, или оставить строку пустой, поскольку кнопка подтверждения будет недоступной.

 

После создания очереди

 

После создания очереди становится доступной операция добавления, кнопка создания становится неактивной, потому что не может существовать более одной очереди одновременно.

 

 

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.