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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

"Магнитогорский государственный технический университет им. Г.И. Носова"

Институт энергетики и автоматизированных систем

Кафедра вычислительной техники и программирования

КУРСОВАЯ РАБОТА

по дисциплине: "Модели и структуры данных"

на тему: "Приоритетная очередь"

Исполнитель: Богатырёв А.В., студент 2 курса, группа АВп-14

Руководитель: Гладышева М.М., доцент кафедры ВТиП

Магнитогорск, 2016.

Оглавление

• Вступление
• 1. Списки. Варианты реализации списков
• 1.1 Обработка двусвязных списков
• 1.1.1 Вставка элемента в список
• 1.1.2 Удаление элемента из списка
• 2. Очереди
• 2.1 Очереди. Варианты реализации очередей
• 2.1.1 Массив
• 2.1.2 Связный список
• 2.1 Очереди с приоритетами
• 3. Программная реализация
• 3.1 Описание используемых типов данных, классов, структур
• 3.2 Конструкторы класса
• 3.3 Добавление элемента в очередь
• 3.4 Удаление элемента из очереди
• 3.5 Доступ к первому элементу в очереди
• 3.6 Удалить первый элемент очереди
• 3.7 Очистить очередь
• 3.8 Вывод элементов очереди на экран
• 3.9 Узнать размер очереди
• 3.10 Трансформация очереди в массив
• 4. Анализ результатов
• 4.1 Результат работы программы
• Заключение
• Список литературы
• Приложение

Вступление

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

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

В курсовом проекте рассматривается разработка класса "очередь с приоритетами" на языке С++, с использованием объектно-ориентированного проектирования. Разработаны алгоритмы обработки очереди, методы вставки, удаления, вывода на экран элементов. Предусмотрено сохранение правильного порядка элементов в очереди при каждой операции.

приоритетная очередь алгоритм

1. Списки. Варианты реализации списков

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

У определённой таким образом структуры данных имеются некоторые свойства:

· Размер списка - количество элементов в нём, исключая последний "нулевой" элемент, являющийся по определению пустым списком.

· Тип элементов - тот самый тип , над которым строится список; все элементы в списке должны быть этого типа.

· Отсортированность - список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).

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

· Сравниваемость - списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

В С++ списки реализуются в виде элементов структуры данных или объектов класса, связанных между собой указателями. При этом выделяют:

· Односвязный список (Однонаправленный связный список)

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

· Двусвязный список (Двунаправленный связный список)

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

· Кольцевой связный список

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

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

1.1 Обработка двусвязных списков

Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы. На рис. 1.1.1 показана организация ссылок в двусвязном списке.

Рис. 1.1.1 Двусвязные списки

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

1.1.1 Вставка элемента в список

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

Рис. 1.1.1.1 Операции с двусвязными списками (Здесь new - вставляемый элемент, а info - поле данных)

1.1.2 Удаление элемента из списка

Удаление элемента из списка по значению осуществляется по принципу изображенному на рис 1.1.2.1.

Рис. 1.1.2.1 Удаление элемента двусвязного списка

2. Очереди

2.1 Очереди. Варианты реализации очередей

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

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

2.1.1 Массив

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

Рис. 2.1 Реализация очереди при помощи массива

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

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

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

2.1.2 Связный список

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

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

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

2.1 Очереди с приоритетами

Очередь с приоритетом - абстрактный тип данных в программировании, поддерживающий три операции:

· InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом

· GetNext: извлечь из очереди и вернуть элемент с наивысшим приоритетом. Другие названия: "PopElement (Off)", "GetMinimum"

· PeekAtNext (необязательная операция): просмотреть элемент с наивысшим приоритетом без извлечения

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

· INSERT (ключ, значение) - добавляет пару в хранилище;

· MIN - возвращает пару с минимальным значением ключа .

· EXTRACT_MIN - возвращает пару с минимальным значением ключа, удаляя её из хранилища.

Очередь с приоритетом может хранить несколько пар с одинаковыми ключами.

Если очередь пуста, то можно считать, что операции MIN и EXTRACT_MIN возвращают некоторую специальную константу UNDEF. В разных реализациях очереди с приоритетом семантика и названия операций могут отличаться.

3. Программная реализация

3.1 Описание используемых типов данных, классов, структур

Для решения поставленной задачи использован шаблон структуры Priority, работающей с полями T inf - информационное поле (принимает данные любого типа), unsigned p - приоритет данного в очереди (p>0).

Рис. 3.1.1 структура Priority

Так же использован шаблон класса DKList. При создании объекта класса выбирается принцип формирования очереди (по увеличению или уменьшению приоритетов) (bool up = 0). Все поля шаблона закрыты для доступа извне (protected). Каждый объект класса имеет поля:

· Priority<T> inf; - информационное поле (содержит данные любого типа)

· DKList *next; - указатель на следующий элемент очереди

· DKList *prev; - указатель на предыдущей элемент очереди

· static DKList *first; - указатель на начало очереди

· static DKList *last; - указатель на конец очереди

Поля *first, *last объявлены как static (статические), по этому они инициализируются перед началом работы программы (до main ()) и являются общими для всех объектов класса DKList:

template <typename T, bool bl> DKList<T, bl>* DKList<T, bl>:: first = NULL;

template <typename T, bool bl> DKList<T, bl>* DKList<T, bl>:: last = NULL;

Так же каждый объект класса обладает методами:

· DKList () - конструктор класса по умолчанию

· DKList (T i, unsigned pr) - конструктор класса с параметрами

· void AddElem (DKList* p) - добавить указатель на элемент в очередь

· void AddElem (T i, unsigned pr) - создать элемент с параметрами и добавить в очереди

· bool DelElem (T inf) - удалить элемент из очереди

· Priority<T>* GetElem () - доступ к первому элементу очереди

· bool DelFirst () - удалить первый элемент очереди

· void free () - очистить очередь

· void Show () - вывод элементов очереди на экран

· unsigned ListSize () - узнать размер очереди

· T* ListToArr () - конвертировать очередь в массив типа T

Рис. 3.1.2 класс DKList

Так же для удобного формирования меню программы используется объект перечислительного типа данных enum {}

Рис. 3.1.3 enum (без имени)

3.2 Конструкторы класса

Конструктор класса без параметров предназначен для создания временного элемента очереди, который потом будет заполнен данными (используется для первичного создания объекта класса через который будет осуществляется обработка очереди):

DKList (): next (NULL), prev (NULL) {

inf. inf = 0;

inf. p = 0;

}

Конструктор с параметрами создает элемент очереди с данными типа T (передаются при помощи переменной T i) и приоритетом p (unsigned pr). Такой элемент еще не добавлен в очередь и существует сам по себе:

DKList (T i, unsigned pr): next (NULL), prev (NULL) {

inf. inf = i;

inf. p = pr;

}

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

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

При попытке добавления элемента по параметрам (данные, приоритет элемента) метод void AddElem (T i, unsigned pr) создает на основе полученных параметров объект типа DKList (new DKList (i, pr)) и передает его в перегрузку метода AddElem () принимающую указатель на объект класса:

void AddElem (T i, unsigned pr) {

AddElem (new DKList (i, pr));

}

Метод void AddElem (DKList* p) осуществляет привязывание элемента p к очереди. При добавлении учитывается три варианта:

· Очередь пустая

· Вставка в первую позицию

· Вставка в конец очереди

· Вставка в середину

Если список пустой, элемент p становится первым и последним элементом очереди:

DKList *f = first;

if (! f) {

last = first = p;

return;

}

Далее если очередь не пустая происходит поиск позиции элемента в очереди согласно указанному приоритету:

while (f->next &&

(up? f->inf. p < p->inf. p: f->inf. p > p->inf. p))

f = f->next;

Если элемент нужно поместить в конец очереди, проверяется расстановка приоритетов в для элемента и элемент становится первым в очереди:

if (! f->next

&& (up? f->inf. p < p->inf. p: f->inf. p > p->inf. p)) {

f->next = p;

p->prev = f;

last = p;

}

Если элемент нужно поместить в первую позицию:

else if (f == first) {

p->next = f;

f->prev = p;

first = p;

}

Если элемент не подходит ни в первую, ни в последнюю позицию в очереди, он помещается в середину, согласно приоритету:

else {f->prev->next = p;

p->prev = f->prev;

p->next = f;

f->prev = p;

}

3.4 Удаление элемента из очереди

Метод bool DelElem (T inf) осуществляет удаление элемента из очереди по значению. При этом проверяется наличие элемента в очереди и в случае успешного удаления возвращается 1, иначе - 0. Поиск элемента проводит цикл:

while (f && f->inf. inf! = inf)

f = f->next;

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

Если элемент находится в первой позиции (в очереди больше одного элемента):

if (first->next) {

if (f == first) {

first = first->next;

first->prev = NULL;

delete f;

return 1;

}

Иначе, если элемент в последней позиции:

if (f == last) {

last = last->prev;

last->next = NULL;

delete f;

return 1;

}

Иначе, если в средине очереди:

f->prev->next = f->next;

f->next->prev = f->prev;

delete f;

return 1;

И, если в очереди был только один элемент, он удаляется:

else {

delete first;

first = last = NULL;

return 1;

}

3.5 Доступ к первому элементу в очереди

Согласно принципу очереди доступ осуществляется к первому в очереди элементу (с наибольшим приоритетом). Такой элемент будет иметь статический указатель first, что позволяет получить к нему доступ при помощи метода Priority<T>* GetElem ():

Priority<T>* GetElem () {

if (first)

return & (first->inf);

else

return NULL;

}

3.6 Удалить первый элемент очереди

Для доступа к последующим элементам очереди, нужно обработать (удалить) первый из них, для чего используется метод: bool DelFirst (), удаляющий первый элемент или возвращающий 0, если очередь уже пустая:

bool DelFirst () {if (first)

return DelElem (first->inf. inf);

else

return 0;

}

3.7 Очистить очередь

Для очистки очереди и освобождения оперативной памяти компьютера используется метод void free (), который последовательно удаляет все элементы очереди, начиная с первого:

void free () {

if (first! = NULL)

do

DelElem (first->inf. inf);

while (first);

}

3.8 Вывод элементов очереди на экран

Метод void Show () выводит через пропуск все элементы очереди на экран в формате: "ЗНАЧЕНИЕ|ПРИОРИТЕТ" или "NULL", если в очереди нет элементов:

void Show () {DKList *f = first;

if (! f) {

cout << "NULL";

return;

}

while (f) {

cout << f->inf. inf << '|' << f->inf. p << '\t';

f = f->next;

}

}

3.9 Узнать размер очереди

Для запроса размеров (количества элементов) очереди используется метод unsigned ListSize (), который возвращает количество элементов как целочисленную без знаковую константу:

unsigned ListSize () {

DKList *f = first;

int n = 0;

while (f)

f = f->next, ++n;

return n;

}

3.10 Трансформация очереди в массив

Метод T* ListToArr () возвращает указатель типа T на массив состоящий из значений элементов очереди, расположенных в порядке увеличения (уменьшения) приоритетов:

T* ListToArr () {

int n = ListSize ();

DKList *f = first;

T *arr;

if (! n)

return NULL;

arr = new T [n];

n = 0;

while (f)

arr [n++] = f->inf. inf, f = f->next;

return arr;

}

4. Анализ результатов

Для тестирования описанного класса DKList сформируем меню, где каждый пункт будет отвечать за соответствующий метод класса (int menu ()):

· Add element - добавить элемент

· Show elements - вывод элементов на экран

· Get first element - доступ к первому элементу

· Copy priority-list to array - сформировать массив на основе очереди

· Delete first element - удалить первый элемент

· Delete element by value - удалить элемент по значению

· Free memory - удалить очередь

· Exit - завершение работы программы

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

4.1 Результат работы программы

При запуске программа выдает запрос на выбор пункта меню:

Выбор первого пункта позволяет добавить элемент в очередь:

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

Пункт три позволяет получить доступ (увидеть) первый элемент в очереди и эго приоритет:

Четвертый пункт выведет адрес массива, сформированного из элементов очереди:

Пункты 5-7 удалят соответствующие элементы очереди (согласно запроса и выведут сообщения).

Пункт восемь завершит работу программы.

Заключение

В результате курсового проектирования разработан класс и программа, для обработки очередей с приоритетами

Учтены все условия обработки очереди:

1 Вставка элемента в очередь согласно приоритету

2 Доступ к первому по очереди элементу

3 Удаление элемента из очереди (первого по очереди, указанного по значению)

4 Вывод элементов очереди на экран

5 Формирование массива из значений элементов очереди

6 Удаление очереди

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

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

1. Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разаботка.2-изд. - СПб.: Питер, 2007. - 544 с.: ил.

2. Н.Б. Культин, С/С++ в задачах и примерах. СПб: БХВ-Петербург, 2001, - 854 стр.

3. Основы объектно-ориентированного программирования. Язык программирования С++/ Волкова И.А., Иванов А.В., Карпов Л.Е. - Учебное пособие для студентов 2 курса. - М.: Издательский отдел факультета ВМК МГУ (лицензия ИД № 05899 от 24.09.2001), 2011 - 112 с.

4. Джейсуол Н.К. Очереди с приоритетами. - М.: Мир, 1973. - 279 с.

Приложение

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

#include <iostream>

using namespace std;

template <typename T> struct Priority {

T inf;

unsigned p;

};

template <typename T = int, bool up = 0> class DKList { // обявление класса очереди с полем типу T, up определяет направление возрастания

Priority<T> inf; // информационное поле

DKList *next; // указатель на следующий элемент

DKList *prev; // указатель на предыдущий элемент

static DKList *first;

static DKList *last;

public:

DKList (): next (NULL), prev (NULL) // конструктор по умолчанию

{

inf. inf = 0;

inf. p = 0;

}

DKList (T i, unsigned pr): next (NULL), prev (NULL) // конструктор для информационного поля и приоритета

{

inf. inf = i;

inf. p = pr;

}

void AddElem (DKList* p) { // метод добавление элемента

DKList *f = first;

if (! f) { // если очередь пустая

last = first = p;

return;

}

while (f->next && (up? f->inf. p < p->inf. p: f->inf. p > p->inf. p)) // ищем место

f = f->next;

if (! f->next && (up? f->inf. p < p->inf. p: f->inf. p > p->inf. p)) { // если конец очереди

f->next = p;

p->prev = f;

last = p;

}

else if (f == first) { // если начало очереди

p->next = f;

f->prev = p;

first = p;

}

else { // если середина очереди

f->prev->next = p;

p->prev = f->prev;

p->next = f;

f->prev = p;

}

}

void AddElem (T i, unsigned pr) {

AddElem (new DKList (i, pr));

}

bool DelElem (T inf) { // метод удаления по значению

DKList *f = first;

while (f && f->inf. inf! = inf)

f = f->next;

if (! f) // элемент не найден

return 0;

if (first->next) {

if (f == first) { // если это начало

first = first->next;

first->prev = NULL;

delete f;

return 1;

}

if (f == last) { // если конец очереди

last = last->prev;

last->next = NULL;

delete f;

return 1;

}

f->prev->next = f->next;

f->next->prev = f->prev;

delete f;

return 1;

}

else {

delete first;

first = last = NULL;

return 1;

}

}

Priority<T>* GetElem () { // метод получения первого элемента из очереди

if (first)

return & (first->inf);

else

return NULL;

}

bool DelFirst () { // метод удаление первого элемента

if (first)

return DelElem (first->inf. inf);

else

return 0;

}

void free () { // очистка списка

if (first! = NULL)

do

DelElem (first->inf. inf);

while (first);

}

void Show () { // метод вывода елементов на экран

DKList *f = first;

if (! f) { // если очередь пустая

cout << "NULL";

return;

}

while (f) {

cout << f->inf. inf << '|' << f->inf. p << '\t';

f = f->next;

}

}

unsigned ListSize () {

DKList *f = first;

int n = 0;

while (f)

f = f->next, ++n;

return n;

}

T* ListToArr () {

int n = ListSize ();

DKList *f = first;

T *arr;

if (! n)

return NULL;

arr = new T [n];

n = 0;

while (f)

arr [n++] = f->inf. inf, f = f->next;

return arr;

}

};

template <typename T, bool bl> DKList<T, bl>* DKList<T, bl>:: first = NULL;

template <typename T, bool bl> DKList<T, bl>* DKList<T, bl>:: last = NULL;

enum {

MenuStart = 0,MenuAdd,

MenuShow,

MenuGet,

MenuToArr,

MenuDel,

MenuDelElem,

MenuFree,

MenuExit

};

int menu () {

int m;

do {

system ("cls");

cout << "Menu: "

<< "\n [" << MenuAdd << "] - Add element"

<< "\n [" << MenuShow << "] - Show elements"

<< "\n [" << MenuGet << "] - Get first element"

<< "\n [" << MenuToArr << "] - Copy priority-list to array"

<< "\n [" << MenuDel << "] - Delete first element"

<< "\n [" << MenuDelElem << "] - Delete element by value"

<< "\n [" << MenuFree << "] - Free memory"

<< "\n [" << MenuExit << "] - Exit"

<< "\nYour choise: ";

cin >> m;

} while (m <= MenuStart || m > MenuExit);

return m;

}

int main () {

DKList<int> lst;

Priority<int> *pr;

int tmp, *a;

unsigned n;

bool bl = true;

while (bl)

switch (menu ())

{

case MenuAdd:

system ("cls");

cout << "Input value of element: ";

cin >> tmp;

cout << "Input priority: ";

cin >> n;

lst. AddElem (tmp, n);

cout << "\tElement successfully added";

getchar ();

getchar ();

break;

case MenuShow:

system ("cls");

cout << "Elements (value|priority): ";

lst. Show ();

cout << "\nThere are " << lst. ListSize () << " elements. ";

getchar ();

getchar ();

break;

case MenuToArr:

system ("cls");

if (a = lst. ListToArr ()) {

cout << "Array [" << a << "]: ";

for (unsigned i = 0; i < lst. ListSize (); ++i)

cout << a [i] << '\t';

cout << "\n\tElements successfully copied!" << endl;

}

else

cout << "\tList NULL!";

getchar ();

getchar ();

break;

case MenuGet:

system ("cls");

if (pr = lst. GetElem ()) {

cout << "Value of first element: " << pr->inf << endl;

cout << "Priority of first element: " << pr->p;

}

else

cout << "\tList NULL!";

getchar ();

getchar ();

break;

case MenuDel:

system ("cls");

if (lst. DelFirst ())

cout << "\tFirst element deleted!";

else

cout << "\tList NULL!";

getchar ();

getchar ();

break;

case MenuDelElem:

system ("cls");

cout << "Input value of element: ";

cin >> tmp;

if (lst. DelElem (tmp))

cout << "\tElement successfully deleted";

else

cout << "\tNo found this element!";

getchar ();

getchar ();

break;

case MenuFree:

system ("cls");

lst. free ();

cout << "\tElements deleted!";

getchar ();

getchar ();

break;

case MenuExit:

system ("cls");

bl = false;

lst. free ();

break;

}

system ("pause");

return 0;

}

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