Приоритетная очередь. Курсовая работа (т). Информационное обеспечение, программирование.
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Информационное обеспечение, программирование
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!
Похожие работы на - Приоритетная очередь
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Нужна качественная работа без плагиата?
Не нашел материал для своей работы?
Поможем написать качественную работу Без плагиата!
Министерство образования и науки
Российской Федерации
Федеральное государственное бюджетное
образовательное учреждение высшего образования
"Магнитогорский государственный
технический университет им. Г.И. Носова"
Институт энергетики и
автоматизированных систем
Кафедра вычислительной техники и
программирования
по дисциплине: "Модели и
структуры данных"
Исполнитель: Богатырёв А.В., студент 2 курса, группа АВп-14
Руководитель: Гладышева М.М., доцент кафедры ВТиП
1. Списки. Варианты реализации списков
2.1 Очереди. Варианты реализации очередей
3.1 Описание используемых типов данных, классов, структур
3.5 Доступ к первому элементу в очереди
3.8 Вывод элементов очереди на экран
3.10 Трансформация очереди в массив
При решении различных задач часто возникает необходимость
хранения данных в структурах отличных от стандартных массивов С++. При этом
используют искусственные структуры данных (списки, деревья, векторы и т.д.),
наиболее популярными являются списки, их также удобно использовать при создании
очередей элементов.
Удобнее всего обрабатывать очереди с приоритетами будет при
помощи соответствующего класса. Для создания и описания класса в курсовом
проекте будут рассмотрены принципы описания и работы списков и очередей в С++,
на основе чего будет описан соответствующий класс.
В курсовом проекте рассматривается разработка класса
"очередь с приоритетами" на языке С++, с использованием
объектно-ориентированного проектирования. Разработаны алгоритмы обработки
очереди, методы вставки, удаления, вывода на экран элементов. Предусмотрено
сохранение правильного порядка элементов в очереди при каждой операции.
Список - это абстрактный тип данных
<#"866098.files/image001.gif">, над которым строится
список; все элементы в списке должны быть этого типа.
· Отсортированность -
список может быть отсортирован в соответствии с некоторыми критериями
сортировки (например, по возрастанию целочисленных значений, если список
состоит из целых чисел).
· Возможности доступа -
некоторые списки в зависимости от реализации могут обеспечивать программиста
селекторами для доступа непосредственно к заданному по номеру элементу.
· Сравниваемость - списки
можно сравнивать друг с другом на соответствие, причём в зависимости от
реализации операция сравнения списков может использовать разные технологии.
В С++ списки реализуются в виде элементов структуры данных
или объектов класса, связанных между собой указателями. При этом выделяют:
В односвязном списке можно передвигаться только в сторону
конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое
текущего узла, невозможно.
По двусвязному списку можно передвигаться в любом направлении
- как к началу, так и к концу. В этом списке проще производить удаление и
перестановку элементов, так как всегда известны адреса тех элементов списка,
указатели которых направлены на изменяемый элемент.
Разновидностью связных списков является кольцевой
(циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным.
Последний элемент кольцевого списка содержит указатель на первый, а первый (в
случае двусвязного списка) - на последний.
Каждый из вариантов реализации списков имеет свои достоинства
и недостатки. Для описания очереди с приоритетами будет использован двусвязный
список.
Двусвязный список состоит из элементов данных, каждый из
которых содержит ссылки как на следующий, так и на предыдущий элементы. На рис.
1.1.1 показана организация ссылок в двусвязном списке.
Наличие двух ссылок вместо одной предоставляет несколько
преимуществ. Вероятно, наиболее важное из них состоит в том, что перемещение по
списку возможно в обоих направлениях. Это упрощает работу со списком, в
частности, вставку и удаление. Помимо этого, пользователь может просматривать
список в любом направлении. Еще одно преимущество имеет значение только при
некоторых сбоях. Поскольку весь список можно пройти не только по прямым, но и
по обратным ссылкам, то в случае, если какая-то из ссылок станет неверной,
целостность списка можно восстановить по другой ссылке.
При вставке нового элемента в двусвязный список могут быть
три случая: элемент вставляется в начало, в середину и в конец списка. Эти
операции показаны на рис. 1.1.1.1.
Рис. 1.1.1.1 Операции с двусвязными списками (Здесь new -
вставляемый элемент, а info - поле данных)
Удаление элемента из списка по значению осуществляется по
принципу изображенному на рис 1.1.2.1.
Рис. 1.1.2.1 Удаление элемента двусвязного списка
Очередь - структура данных
<#"866098.files/image008.gif">
Рис. 2.1 Реализация очереди при помощи
массива
Обычно start указывает на голову очереди,
end - на элемент, который заполнится, когда в очередь войдёт новый элемент. При
добавлении элемента в очередь в q [end] записывается новый элемент очереди, а
end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы
циклически обходим массив и значение переменной становится равным n. Извлечение
элемента из очереди производится аналогично: после извлечения элемента q
[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна
ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно
отличить от пустой), что компенсируется простотой алгоритмов.
Преимущества данного метода: возможна
незначительная экономия памяти по сравнению со вторым способом; проще в
разработке.
Недостатки: максимальное количество
элементов в очереди ограничено размером массива. При его переполнении требуется
перевыделение памяти и копирование всех элементов в новый массив.
· MIN - возвращает пару с минимальным значением
ключа .
· EXTRACT_MIN - возвращает
пару с минимальным значением
ключа, удаляя её из хранилища.
Очередь с приоритетом может хранить
несколько пар с одинаковыми ключами.
Если очередь пуста, то можно считать, что
операции MIN и EXTRACT_MIN возвращают некоторую специальную константу UNDEF. В
разных реализациях очереди с приоритетом семантика и названия операций могут
отличаться.
Для решения поставленной задачи
использован шаблон структуры Priority, работающей с полями T inf - информационное поле
(принимает данные любого типа), unsigned p - приоритет данного в очереди (p>0).
Так же использован шаблон класса DKList. При создании объекта
класса выбирается принцип формирования очереди (по увеличению или уменьшению
приоритетов) (bool up = 0). Все поля шаблона закрыты для доступа извне (protected). Каждый объект класса
имеет поля:
· Priority
inf; - информационное поле (содержит данные любого типа)
· DKList
*next; - указатель на следующий элемент очереди
· DKList
*prev; - указатель на предыдущей элемент очереди
· static
DKList *first; - указатель на начало очереди
· static
DKList *last; - указатель на конец очереди
Поля *first, *last объявлены как static (статические), по этому
они инициализируются перед началом работы программы (до main ()) и являются общими
для всех объектов класса DKList:
template DKList* DKList:: first = NULL;
template DKList* DKList:: last = NULL;
Так же каждый объект класса обладает методами:
· DKList
() - конструктор
класса по умолчанию
· DKList (T i, unsigned pr) - конструктор класса с
параметрами
· void
AddElem (DKList* p) - добавить указатель на элемент в очередь
· void AddElem (T i, unsigned pr) - создать элемент с
параметрами и добавить в очереди
· bool
DelElem (T inf) - удалить элемент из очереди
· Priority*
GetElem () - доступ
к первому элементу очереди
· bool
DelFirst () - удалить
первый элемент очереди
· void
free () - очистить
очередь
· void
Show () - вывод
элементов очереди на экран
· unsigned
ListSize () - узнать
размер очереди
· T*
ListToArr () - конвертировать очередь в массив типа T
Так же для удобного формирования меню программы используется
объект перечислительного типа данных enum {}
Конструктор класса без параметров предназначен для создания
временного элемента очереди, который потом будет заполнен данными (используется
для первичного создания объекта класса через который будет осуществляется
обработка очереди):
DKList (): next (NULL), prev
(NULL) {
Конструктор с параметрами создает элемент очереди с данными
типа T
(передаются при помощи переменной T i) и приоритетом p (unsigned pr). Такой элемент еще не
добавлен в очередь и существует сам по себе:
DKList (T i, unsigned pr): next
(NULL), prev (NULL) {. inf = i;. p = pr;
Существует два варианта добавления элемента в очередь: по
параметрам элемента и по указателю на уже готовый элемент типа DKList.
При попытке добавления элемента по параметрам (данные,
приоритет элемента) метод void AddElem (T i,
unsigned pr) создает на основе полученных параметров объект типа DKList (new DKList (i, pr)) и передает его в
перегрузку метода AddElem () принимающую указатель на объект класса:
void AddElem (T i, unsigned pr)
{(new DKList (i, pr));
Метод void AddElem (DKList* p) осуществляет привязывание
элемента p
к очереди. При добавлении учитывается три варианта:
Если список пустой, элемент p становится первым и
последним элементом очереди:
DKList *f = first;(! f) { = first = p;
Далее если очередь не пустая происходит поиск позиции
элемента в очереди согласно указанному приоритету:
(up? f->inf. p <
p->inf. p: f->inf. p > p->inf. p))
Если элемент нужно поместить в конец очереди, проверяется
расстановка приоритетов в для элемента и элемент становится первым в очереди:
&& (up? f->inf. p
< p->inf. p: f->inf. p > p->inf. p)) {>next = p;>prev = f;
Если элемент нужно поместить в первую позицию:
else if (f == first) {>next =
f;>prev = p;= p;
Если элемент не подходит ни в первую, ни в
последнюю позицию в очереди, он помещается в середину, согласно приоритету:
else {f->prev->next =
p;>prev = f->prev;>next = f;
Метод bool DelElem (T inf) осуществляет удаление элемента из очереди по
значению. При этом проверяется наличие элемента в очереди и в случае успешного
удаления возвращается 1, иначе - 0. Поиск элемента проводит цикл:
Если значение переданное в DelElem () совпадает из одним из
значений элементов, происходит удаление. При этом учитываются варианты, если
элемент находится в первой, последней позициях, в средине очереди и если в
очереди больше одного элемента.
Если элемент находится в первой позиции (в очереди больше
одного элемента):
if (first->next) {(f ==
first) {= first->next;>prev = NULL;
Иначе, если элемент в последней позиции:
if (f == last) {= last->prev;>next
= NULL;f;
f->prev->next =
f->next;>next->prev = f->prev;
И, если в очереди был только один элемент, он удаляется:
Согласно принципу очереди доступ осуществляется к первому в
очереди элементу (с наибольшим приоритетом). Такой элемент будет иметь
статический указатель first, что позволяет получить к нему доступ при помощи
метода Priority* GetElem ():
Priority* GetElem ()
{(first)& (first->inf);NULL;
Для доступа к последующим элементам очереди, нужно обработать
(удалить) первый из них, для чего используется метод: bool DelFirst (), удаляющий первый элемент или возвращающий 0,
если очередь уже пустая:
bool DelFirst () {if
(first)DelElem (first->inf. inf);
Для очистки очереди и освобождения оперативной памяти
компьютера используется метод void free (), который последовательно удаляет все элементы
очереди, начиная с первого:
void free () {(first! =
NULL)(first->inf. inf);
Метод void Show () выводит через пропуск все элементы очереди на
экран в формате: "ЗНАЧЕНИЕ|ПРИОРИТЕТ" или "NULL", если в очереди
нет элементов:
void Show () {DKList *f =
first;(! f) {<< "NULL";;
}(f) {<< f->inf. inf
<< '|' << f->inf. p << '\t';
Для запроса размеров (количества элементов) очереди
используется метод unsigned ListSize (), который возвращает количество элементов как
целочисленную без знаковую константу:
unsigned ListSize () {*f =
first;n = 0;(f)= f->next, ++n; n;
Метод T* ListToArr () возвращает указатель типа T на массив состоящий из
значений элементов очереди, расположенных в порядке увеличения (уменьшения)
приоритетов:
T* ListToArr () {n = ListSize
();*f = first;*arr;(! n)NULL;= new T [n];= 0;(f)[n++] = f->inf. inf, f =
f->next;
Для тестирования описанного класса 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 (для упрощения модели,
будут использованы целые числа). При выборе пунктов меню пользователем, будут
вызываться соответствующие методы класса.
При запуске программа выдает запрос на выбор пункта меню:
Выбор первого пункта позволяет добавить элемент в очередь:
Второй пункт выводит все элементы очереди на экран и их
количество:
Пункт три позволяет получить доступ (увидеть) первый элемент
в очереди и эго приоритет:
Четвертый пункт выведет адрес массива, сформированного из
элементов очереди:
Пункты 5-7 удалят соответствующие элементы очереди (согласно
запроса и выведут сообщения).
Пункт восемь завершит работу программы.
В результате курсового проектирования разработан класс и
программа, для обработки очередей с приоритетами
Учтены все условия обработки очереди:
Вставка элемента в очередь согласно приоритету
2 Доступ к первому по очереди элементу
Удаление элемента из очереди (первого по очереди,
указанного по значению)
Вывод элементов очереди на экран
Формирование массива из значений элементов очереди
1. Рамбо
Дж., Блаха М. UML 2.0. Объектно-ориентированное
моделирование и разаботка.2-изд. - СПб.: Питер, 2007. - 544 с.: ил.
2. Н.Б.
Культин, С/С++ в задачах и примерах. СПб: БХВ-Петербург, 2001, - 854 стр.
. Основы
объектно-ориентированного программирования. Язык программирования С++/ Волкова
И.А., Иванов А.В., Карпов Л.Е. - Учебное пособие для студентов 2 курса. - М.:
Издательский отдел факультета ВМК МГУ (лицензия ИД № 05899 от 24.09.2001), 2011
- 112 с.
. Джейсуол
Н.К. Очереди с приоритетами. - М.: Мир, 1973. - 279 с.
using namespace std; struct Priority {inf;p;
}; class DKList { // обявление класса очереди с полем типу T, up определяет направление возрастания
Priority inf; // информационное
поле*next; // указатель на следующий элемент*prev; // указатель на предыдущий
элемент
static DKList *first;DKList
*last;:(): next (NULL), prev (NULL) // конструктор по умолчанию
}(T i, unsigned pr): next
(NULL), prev (NULL) // конструктор для информационного поля и приоритета
}AddElem (DKList* p) { // метод добавление элемента
DKList *f = first;(! f) { // если очередь
пустая
}(f->next && (up?
f->inf. p < p->inf. p: f->inf. p > p->inf. p)) // ищем место= f->next;(! f->next && (up? f->inf. p < p->inf.
p: f->inf. p > p->inf. p)) { // если конец очереди>next = p;>prev = f;= p;
}if (f == first) { // если начало очереди>next = f;>prev = p;= p;
}{ // если середина очереди>prev->next
= p;
p->prev = f->prev;>next
= f;>prev = p;
}AddElem (T i, unsigned pr)
{(new DKList (i, pr));
}DelElem (T inf) { // метод удаления по
значению
DKList *f = first;(f &&
f->inf. inf! = inf)=
f->next;(! f) // элемент не найден
return 0;(first->next) {(f ==
first) { // если это начало= first->next;>prev = NULL;f;1;
}(f == last) { // если конец очереди= last->prev;>next = NULL;f;1;
}>prev->next =
f->next;>next->prev = f->prev;f;1;
}* GetElem () { // метод получения первого элемента из очереди(first)& (first->inf);NULL;
}DelFirst () { // метод удаление первого элемента(first)DelElem (first->inf. inf);0;
}free () { // очистка списка(first! = NULL)(first->inf. inf);
}Show () { // метод вывода елементов на
экран*f = first;(! f) { // если очередь пустая
}(f) {<< f->inf. inf
<< '|' << f->inf. p << '\t';= f->next;
}ListSize () {*f = first;n =
0;(f)= f->next, ++n;n;
}* ListToArr () {n = ListSize
();*f = first;*arr;(! n)NULL;= new T [n];= 0;(f)[n++] = f->inf. inf, f =
f->next;arr;
};
DKList* DKList:: first = NULL; DKList* DKList:: last = NULL;{= 0,MenuAdd,,,,,,,
<< "\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"
} while (m <= MenuStart || m
> MenuExit);m;
}main () {
lst; *pr;tmp, *a;n;bl = true;(bl)(menu ())
{MenuAdd:("cls");<<
"Input value of element: ";>> tmp;<< "Input
priority: ";>> n;. AddElem (tmp, n);<< "\tElement
successfully added";();();;MenuShow:("cls");<< "Elements
(value|priority): ";. Show ();<< "\nThere are " <<
lst. ListSize () << " elements.
";();();;MenuToArr:("cls");(a = lst. ListToArr ()) {<<
"Array [" << a << "]: ";(unsigned i = 0; i <
lst. ListSize (); ++i)<< a [i] << '\t';<< "\n\tElements
successfully copied!" << endl;
}<< "\tList
NULL!";();();;MenuGet:("cls");(pr = lst. GetElem ()) {<<
"Value of first element: " << pr->inf << endl;<<
"Priority of first element: " << pr->p;
}<< "\tList
NULL!";();();;MenuDel:("cls");(lst. DelFirst ())<<
"\tFirst element deleted!";<< "\tList
NULL!";();();;MenuDelElem:("cls");<< "Input value of
element: ";>> tmp;(lst. DelElem (tmp))<< "\tElement
successfully deleted";<< "\tNo found this
element!";();();;MenuFree:("cls");. free ();<<
"\tElements deleted!";();();;MenuExit:("cls");= false;.
free ();
Похожие работы на - Приоритетная очередь Курсовая работа (т). Информационное обеспечение, программирование.
Эссе На Тему Наркотические Вещества Кратко
Дипломная работа по теме Технологія виробництва медичного скла
Практика Усзн Дневник
Реферат по теме Трудовой контракт
Реферат: Букеевская Орда
Доклад: Доменико Скарлатти (Scarlatti)
Реферат: Теории эволюции и процесс видообразования
Эссе Значение Растений В Жизни Человека
Реферат: Методика преподавания темы “Электромагнитные колебания” в средней школе с использованием компьютерных технологий
Дипломная работа по теме Особенности и проблемы регионального брендинга в России
Свободные Операционные Системы Реферат
Курсовая работа по теме Особенности финансов коммерческих организаций
Доклад Дипломной Работы Россия
Курсовая работа по теме Здоровое питание на страже здоровья
Курсовая работа по теме Эллипсометрическое измерение температуропроводности наноструктурированных материалов с использованием импульсного лазерного излучения
Реферат: Индевор корабль
Курсовая работа: Въездной туризм и эффективность использования национального туристского потенциала в его развитии. Скачать бесплатно и без регистрации
Готовые Эссе По Предмету Этика
Декабрьское Сочинение Образец Написания
Контрольная Работа На Тему Міжнародна Діяльність Автомобільного Концерну Bmw
Реферат: Особенности статуса законодательного представительного органа государственной власти субъекта
Похожие работы на - Терроризм как система насилия: явления, причины, противодействие
Похожие работы на - Риски в банковской деятельности