Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Лабораторная работа №6
|
|
Стеки, очереди и деки – реализация на базе списков и массивов
Цели работы:
– Усвоить понятия «стек», «очередь», «дек».
– Получить практические навыки по реализации абстрактных структур данных стеков, очередей и деков на базе массивов и списков.
– Создать проект в системе Qt Creator, в котором осуществляется работа с одной из изучаемых структур данных и выполняется вывод на экран отображения содержимого этой структуры.
–
6.1 теоретические сведения
Стеком (stack, магазин) называют упорядоченный набор элементов, в котором занесение (добавление) новых элементов и удаление (выборка) существующих производятся только с одного его конца, называемого вершиной стека.
Стеки обслуживают дисциплину «последним пришел, первым ушел» (LIFO – Last in, first out).
Очередь (queue) – это упорядоченный набор элементов, в котором занесение (добавление) новых элементов осуществляется с одного его конца, называемого «концом очереди», а удаление (выборка) существующих производится из другого его конца, называемого началом очереди.
Очереди обслуживают дисциплину «первым пришел, первым ушел» (FIFO – First in, first out).
Дек это список, у которого обе позиции (начало и конец) доступны для добавления и взятия элемента. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на вход или выход: дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека).
ТЕКСТ ПРОГРАММЫ
bool priorityInsert(TQueue & que, TElQ newEl) {
if (isOverflow(que.PBQ, que.PEQ))
return false;
if ((newEl % 10) < (que.storage[que.PBQ] % 10))
INSERT(que, newEl);
else {
if (que.PBQ == 0) {
que.PBQ = QUEUE_SIZE - 1;
que.storage[0] = newEl;
}
else {
que.PBQ--;
que.storage[que.PBQ + 1] = newEl;
}
return true;
}
}
void showQueue(TQueue que) {
for (int i = que.PBQ; i! = que.PEQ; i++) {
if (i == QUEUE_SIZE - 1)
i = -1;
cout < < que.storage[i + 1] < < " ";
}
cout < < " \nТекущая позиция начала очереди " < < que.PBQ < < endl;
cout < < " Текущая позиция окончания очереди " < < que.PEQ < < endl;
}
РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ ПРОЕКТА
В таблице 6.1 приведены значения элементов очереди
| Позиция | |||||||||
| Значение |
Таблица 6.1 – значения элементов очереди
Изначально заполняем позиции очереди стандартным методом числами 67, 67, 12, 44, 8. После заполняем очередь, используя добавление с учетом приоритета, вводя числа 11, 11, 9, 8. Итоговый результат будет таков:
9 8 67 67 12 44 8 11 11
На рисунке 6.1 изображен результат работы функции добавления элемента в очередь с учетом приоритета.
Рисунок 6.1 – результат добавления элемента в очередь с учетом приоритета
ВЫВОД
Во время лабораторной работы мы усвоили понятия «стек», «очередь», «дек», получили практические навыки по реализации абстрактных структур данных стеков, очередей и деков на базе массивов и списков и создали проект, в котором осуществляется работа с одной из изучаемых структур данных и выполняется вывод на экран отображения содержимого этой структуры.
|
|