Размещено на http://www.allbest.ru/

1

Курсовая работа по дисциплине: «Алгоритмы и структуры данных»

На тему: «Исследование очередей»



Задание на курсовую работу

Тема курсовой работы: «Исследование очередей»

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



Содержание

• Реферат
• Введение
• 1. Теоретические сведения
• 1.1 Основные понятия
• 1.2 Описание «очереди»
• 1.3 Область применения
• 2. Разработка
• 2.1 Методы очереди
• 2.2 Создание очереди с помощью массива
• 2.3 Очередь с приоритетом
• 3. Инструкция пользователя
• Заключение
• Список литературы
• Приложения


Реферат

Целью данной работы служит разработка эффективных алгоритмов на динамических структурах данных.

Динамические структуры данных - это структуры данных, память под которые выделяется и освобождается по мере необходимости.

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

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

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



Введение

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

Исходя из выше изложенного, данная курсовая работа посвящена актуальной теме «Исследование очередей».

Цель работы - изучение динамической структуры данных «очередь».

Для раскрытия темы в работе были поставлены и решены следующие задачи:

– рассмотрены теоретические сведения о структуре данных «очередь»;

– описаны методы работы с очередью;

– разработана программа реализующая алгоритмы работы с очередью.

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

Объект исследования - динамическая структура «очередь».

Предмет исследования - алгоритмы работы с очередью.

В первой главе приведены основные теоретические сведения о структуре данных «очередь». Описана структура данных «очередь» и раскрыта область ее применения.

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

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

В заключении подведены итоги исследования. В приложении приведен код разработанной программы.

Работа состоит из введения, трех глав, заключения, списка источников, включающего 5 наименований.

Общий объем работы составляет 26 страниц.



1. Теоретические сведения

1.1 Основные понятия

В этом разделе мы ознакомимся с динамическими структурами данных и с самими очередями.

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

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

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

Элемент динамической структуры состоит из двух полей:

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

? поле связок, в котором содержатся один или несколько указателей, которые связывают данный элемент с другими элементами структуры.

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

У связного представления данных есть свои достоинства:

- в возможности обеспечения значительной изменчивости структур;

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

- размер структуры ограничивается только размером памяти машины;

Но есть и недостатки:

- работа с указателями требует, как правило, более высокой квалификации от программиста;

- на поля связок расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

Последний минус наиболее серьёзун и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента или информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск и требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, стеки, списки, деревья и т.д.). [3].

1.2 Описание «очереди»

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

Очередь организована согласно дисциплине обслуживания FIFO:

- FIRST - первый;

- INPUT - пришёл;

- FIRST - первый;

- OUTPUT - ушёл;

В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым.

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

Например, у вас имеется 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке 1.

Рисунок 1- Пример очереди.

Так, например, чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.

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

Существует несколько способов реализации очереди:

- с помощью одномерного массива;

- с помощью связанного списка;

- с помощью класса объектно-ориентированного программирования;

Реализация и работа программы самой очереди будет рассмотрена далее.

1.3 Область применения

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



2. Разработка

2.1 Методы очереди

Метод - это та же самая функция, но она работает только с контейнерами STL .

Для работы с очередью вам понадобится знать функции: push(), pop(), front(), back(), empty() .

1. Для добавления в очередь нового элемента нужно воспользоваться функцией - push(). В круглых скобках должно находится значение, которое мы хотим добавить.

2. Если нам понадобилось удалить первый элемент нужно оперировать функцией pop(). В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать. Эти функции тоже не нуждаются в указании аргумента: empty(), back() и front().

3. Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция front().

4. Чтобы обратиться к последнему элементу в очереди вам поможет функция back().

5. Чтобы узнать пуста ли очередь нужно воспользоваться функцией empty().

- Если ваша очередь пуста - возвратит true.

- Если же в ней что-то есть - возвратит false. [5].

Реализация этих функций на язке C++ представлена на рисунке 2.

Рисунок 2 - Код программы.

При запуске консоль будет выглядеть как на рисунке 3:

Рисунок 3 - Работа программы.

2.2 Создание очереди с помощью массива

Очередь можно реализовать через массив, назовём его шаблон очереди - q.

Для реализации нам понадобится создать две дополнительные переменные start и ends. Start будет указывать на первый элемент очереди, a ends на последний элемент.

Чтобы обратиться к последнему элементу нам придется использовать эту конструкцию - queue[ends]. Обращение к первому элементу будет выглядеть аналогично queue[start].

Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start на один.

Для того чтобы проверить пуста ли очередь нам нужно просто проверить условие start == ends:

1. Если результатом условия будет true, то очередь пуста.

2. Если же результат условия false, значит очередь чем-то заполнена.

На рисунке 4 показан пример реализации такой очереди.

Рисунок 4 - Создание очереди с помощью массива.

2.3 Очередь с приоритетом

Очередь с приоритетом (priority_queue) - это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию.

Так самый большой элемент в приоритетной очереди будет стоять на первом месте.

Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже: массив программа очередь

В начале нужно написать priority_queue.

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

И конечно же в самом конце мы должны дать ей имя.

Для добавления элемента в очередь с приоритетом мы должны использовать функцию push(). Но чтобы обратится к первому элементу должны использоваться именно функция - top() (как в стеке). А не функция - front().

Также нельзя использовать функцию back() для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front().[4].

На рисунке 5 приведён пример работы такой программы:

Рисунок 5 - Код очереди с приоритетом.

3. Инструкция пользователя

Задачей программы, представленной в приложении А, является заполнение очереди людьми и дальнейшая работа с ней (изменение её содержимого). На рисунке 5 представлена полностью рабочая программа.

Рисунок 6 - Меню программы

На рисунке 6 меню программы, содержащее 3 рабочие кнопки:

А - предназначена для подтверждения вводимого значения и добавления нового человека;

Б - при нажатии на неё, пользователю выдаётся обрабатываемый в этот момент человек;

В - кнопка позволяет отобразить человек, прошедших и освободивших очередь.

Рисунок 7 - Рабочие кнопки.

Для ввода данных о человеке необходимо внести их в поле textbox, далее нужно нажать на кнопку «добавить человека», как показано на рисунке 8:

Рисунок 8 - Поле для ввода.

Рисунок 9 показывает, что в таблице listBox отображаются все вводимые нами значения:

Рисунок 9 - Поле отображения.

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

Рисунок 10 - Сейчас ожидает.

Нажимая на кнопку оставшаяся очередь мы получаем информацию обо всех пользователях, находящихся в очереди в обслуживании, включая человека, который сейчас ожидает (в нашем случае это Григорий), все эти данные отображают в таблице под кнопкой, как и показано на рисунке 11:

Рисунок 11 - Сейчас находятся в очереди.

Задачей программы, представленной в приложении Б, является заполнение очереди цифрами и дальнейшая работа с ней (изменение её содержимого). На рисунке 11 представлена полностью рабочая программа.

Рисунок 12. Меню программы.

В поле (рисунок 13) «очередь» добавляются nэлементов очереди, указанных в поле «размер очереди» (рисунок 14):

Рисунок 13. Поле отображения элементов очереди.

Рисунок 14.Размер очереди.

После выполнения программы результат будет отображаться в поле «обработанная очередь» (рисунок 15):

Рисунок 15. Обработанная очередь.

При нажатии кнопки 1 (рисунок 16) решает задачу программы;

При нажатии кнопки 2 (рисунок 17) обнуляет результат и очищает все;

Рисунок 16. Слева- кнопка 1, справа- кнопка 2.

Рисунок 17. Поле результата.

На рисунке 17 изображено поле результатов. В нем показывается какой элемент (1111 или 0) добавился в середину очереди.



Заключение

Цель работы состояла в том, чтобы изучить динамическую структуру данных «очередь». Цель достигнута полностью. Практическая значимость работы заключается в разработке приложения реализующего алгоритмы работы с очередью. В качестве инструмента использовалась среда Microsoft Visual Studio.

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

Программа разрабатывалась на языке C# с использованием стандартных библиотек. Для решения задачи были изучены приемы работы с очередью на языке C#. В ходе разработки расширены знания в области программирования на языке C#.



Список литературы

1. Справочная система MSDN.

2. Павловская Т.А. C#. Программирование на языке высокого уровня / Т.А. Павловская. - Питер, 2014. - 427 с.

3. Троелсен Э. C# и платформа.NET / Э.Троелсен - Apress, Питер, 2004. - 359 с.

4. Шилдт Г. C# 4.0 Полное руководство / Г.Шилдт - Вильямс Издательский дом, 2011. - 1057 с.

5. Хейлсберг А. Язык программирования C# / А.Хейлсберг, М.Торгерсен, С.Вилтамут - Питер СПб, 2012. - 784 с.



Приложения

Приложение А

Листинг программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace WindowsFormsApplication12

{

public partial class Form1 : Form

{

Queue<string> persons = new Queue<string>();

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

listBox1.Items.Add(textBox1.Text);

persons.Enqueue(textBox1.Text);

textBox1.Text = string.Empty;

}

private void button2_Click(object sender, EventArgs e)

{

// получаем первый элемент без его извлечения

label1.Text = persons.Peek();

}

private void button3_Click(object sender, EventArgs e)

{

// Извлекаем первый элемент в очереди - Tom

// теперь в очереди Bill, John

if (persons.Count!=0)

{

listBox2.Items.Add(string.Format("{0}", persons.Dequeue()));

}

else

{

MessageBox.Show("В очереди никого нет!");

}

}

}

}



Приложение Б

Листинг программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace WindowsFormsApplication14

{

public partial class Form1 : Form

{

Queue<int> ochered = new Queue<int>();

Random rnd = new Random();

public Form1()

{

InitializeComponent();

MaximumSize = this.Size;

}

private void Form1_Load(object sender, EventArgs e)

{

}

private void button1_Click(object sender, EventArgs e)

{

for (int i = 0; i < numericUpDown1.Value; i++)

{

ochered.Enqueue(rnd.Next(100));

}

var list = ochered.ToList();

int var1 = 0000;

int var2 = 1111;

int var3 = 0;

for (int i = 0; i < numericUpDown1.Value; i++)

{

listBox1.Items.Add(ochered.Dequeue());

}

if (list.Count % 2 == 0)

{

list.Insert(list.Count / 2, var1);

var3 = var1;

}

else

{

list.Insert(list.Count / 2, var2);

var3=var2;

}

foreach (var item in list)

{

listBox2.Items.Add(item);

}

label3.Text = string.Format("Добавлено: {0}", var3);

}

private void button2_Click(object sender, EventArgs e)

{

listBox2.Items.Clear();

listBox1.Items.Clear();

ochered.Clear();

}

}

}

Размещено на Allbest.ru

...