Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).
Очередь разумнее всего моделировать, отобразив её на двунаправленный кольцевой список. В этом случае в заглавном звене будет присутствовать информация как об указателе на голову, так и на хвост очереди.
Выделим типовые операции над очередями:
добавление элемента в очередь (помещение в хвост);
удаление элемента из очереди (удаление из головы);
проверка, пуста ли очередь;
очистка очереди.
Вот модуль, содержание которого составляют реализованные типовые операции над очередями.
{Язык Pascal}
Unit Spisok2;
Interface
Type BT = LongInt;
U = ^Zveno;
Zveno = Record Inf : BT; N, P: U End;
Procedure V_Och(Var First : U; X : BT);
Procedure Iz_Och(Var First : U; Var X : BT);
Procedure Ochistka(Var First: U);
Function Pust(First : U) : Boolean;
Implementation
Procedure V_Och;
Var Vsp : U;
Begin
New(Vsp);
Vsp^.Inf := X;
If First = Nil then begin Vsp^.N := Vsp; Vsp^.P := Vsp; First := Vsp end
else begin Vsp^.N := First; Vsp^.P := First^.P; First^.P^.N := Vsp; First^.P := Vsp; end;
End;
Procedure Iz_Och;
Var Vsp : U;
Begin
x:=first^.inf;
if First^.p=first
then begin
dispose(first);
first:= nil
end
else
begin
Vsp := First;
First := First^.N;
First^.P := Vsp^.P;
Dispose(Vsp)
end
End;
Procedure Ochistka;
Var Vsp : BT;
Begin
While Not Pust(First) Do Iz_Och(First, Vsp)
End;
Function Pust;
Begin
Pust := First = Nil
End;
Begin
End.
// ЯзыкС++
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
typedef long BT;
struct U{
BT Inf;
U *N, *P;};
U *V_Och(U *First, BT X)
{ U *Vsp;
Vsp = (U*) malloc (sizeof(U));
Vsp->Inf=X;
if (!First) {Vsp->N=Vsp; Vsp->P=Vsp; First=Vsp;}
else {Vsp->N=First; Vsp->P=First->P; First->P->N=Vsp; First->P=Vsp;}
return First;}
U *Iz_Och(U *First, BT &X)
{ U *Vsp;
X=First->Inf;
if (First->P==First) {free(First); First=NULL;}
else {Vsp=First; First=First->N; First->P=Vsp->P; free(Vsp);}
return First;}
int Pust(U *First)
{ return !First;}
U *Ochistka(U *First)
{ BT Vsp;
while (!Pust(First)) First=Iz_Och(First, Vsp);
return First;
}
Пример. Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5.
Алгоритм решения. Введем три очереди x2, x3, x5, в которых будем хранить элементы, которые соответственно в 2, 3, 5 раз больше напечатанных, но еще не напечатаны. Рассмотрим наименьший из ненапечатанных элементов; пусть это x. Тогда он делится нацело на одно из чисел 2, 3, 5. x находится в одной из очередей и, следовательно, является в ней первым (меньшие напечатаны, а элементы очередей не напечатаны). Напечатав x, нужно его изъять и добавить его кратные. Длины очередей не превосходят числа напечатанных элементов.
{Язык Pascal}
Program Example;
Uses Spisok2;
Var X2, X3, X5 : U; X : BT; I, N : Word;
Procedure PrintAndAdd(T : BT);
Begin
If T <> 1 Then Write(T : 6);
V_Och(X2, T * 2); V_Och(X3, T * 3); V_Och(X5, T * 5);
End;
Function Min(A, B, C : BT) : BT;
Var Vsp : BT;
Begin
If A < B Then Vsp := A Else Vsp := B;
If C < Vsp Then Vsp := C;
Min := Vsp
End;
Begin
X2 := Nil; X3 := Nil; X5 := Nil;
Write('Сколько чисел напечатать? '); ReadLn(N);
PrintAndAdd(1);
For I := 1 To N Do
Begin
X := Min(X2^.Inf, X3^.Inf, X5^.Inf);
PrintAndAdd(X);
If X = X2^.Inf Then Iz_Och(X2, X);
If X = X3^.Inf Then Iz_Och(X3, X);
If X = X5^.Inf Then Iz_Och(X5, X);
End;
Ochistka(X2); Ochistka(X3); Ochistka(X5);
WriteLn
End.
// ЯзыкС++
#include "spis2.cpp"
void PrintAndAdd(BT T);
BT Min (BT A, BT B, BT C);
U * X2, *X3, *X5;
void main ()
{ BT X; long I, N;
X2 = NULL; X3 = NULL; X5 = NULL;
cout << "Сколько чисел напечатать? "; cin >> N;
PrintAndAdd(1);
for (I=1;I<=N; I++)
{ X = Min(X2->Inf, X3->Inf, X5->Inf);
PrintAndAdd(X);
if (X==X2->Inf) X2=Iz_Och(X2, X);
if (X==X3->Inf) X3=Iz_Och(X3, X);
if (X==X5->Inf) X5=Iz_Och(X5, X);
}
X2=Ochistka(X2); X3=Ochistka(X3); X5=Ochistka(X5); cout << endl;
}
void PrintAndAdd(BT T)
{ if (T!=1) {cout.width(6); cout << T;}
X2=V_Och(X2, T*2);
X3=V_Och(X3, T*3);
X5=V_Och(X5, T*5);
}
BT Min (BT A, BT B, BT C)
{ BT vsp;
if (A < B) vsp=A; else vsp=B;
if (C < vsp) vsp=C;
return vsp;
}
Другие работы по теме:
Системы массового обслуживания
Понятие и критерии оценивания системы массового обслуживания, определение ее типа, всех возможных состояний. Построение размеченного графа состояний. Параметры, характеризующие ее работу, интерпретация полученных характеристик, эффективность работы.
Физкультура
В этом реферате описаны разные упражнения для разминки.
Лекция по Квантовой физике
1.1.Предмет классической физики: вещество и излучение. Описание эволюции физических систем происходит с помощью “динамических переменных”. Для систем с материальной точкой динамические переменные – r→(t), p→ (t); в ДСК: x(t), y(t), z(t); px(t), py(t), pz(t). С помощью динамических переменных определяется динамическое состояние физической системы в некоторый момент времени.
Факторные теории личности
Теории стали развиваться после распространения факторного анализа как инструмента количеств, измерений и классификации признаков. В психологических исследованиях Факторные теории личности были ориентированы на эмпирические исследования.
Оптимизация работы многофункциональных центров
Цель написания данной статьи – разработка предложений по оптимизации работы многофункциональных центров предоставления государственных и муниципальных услуг, в частности – в Воронеже и Воронежской области.
Расчет алгоритма управления АСУ
Кривая разгона. Динамические параметры и математическое описание кривой разгона. Алгоритм управления. Выбор переходного процесса и настройки параметров алгоритмов управления АСУ. Регулирование в программе SIMULINC. Оптимизация переходного процесса.
а по теме динамика управляемых преобразовательных устройств
Введение. Цели регулирования пу. Анализ простейшей системы позиционного регулирования, сравнительная оценка идеального релейного и линейного регуляторов по быстродействию. Непрерывное и импульсное регулирование, их оценка по энергетике
Контрольные системы управления
Планирование этапов производства, изменение производительности при новом их распределении. Анализ структуры имитационной модели, элементов, из которых построена модель, и связей между ними. Описание моделирования бизнес-процесса реинжиниринга в офисе.
Математическое моделирование работы систем массового обслуживания
ЛАБОРАТОРНАЯ РАБОТА Математическое моделирование работы систем массового обслуживания Задание Вариант 1. Газозаправочная станция для автомобилей располагает двумя газовыми насосами. В очереди, ведущей к насосам, могут расположиться не более пяти автомашин, включая те, которые обслуживаются.
Структуры данных
Постановка задачи. Основные понятия и определения. Абстрактные структуры данных.
14 Упражнений
Реферат по физкультуре Киев – 1998 Исходное положение — ноги на ширине плеч, руки на поясе. Наклоны головы вперед на счет “раз”, исходное положение на “два”, “три” наклон головы назад, “четыре” исходное положение. Проделать десять раз.
BMW
Заднеприводной седан среднего класса со спортивным характером. Отменная управляемость и прекрасные динамические характеристики объединяются в этом автомобиле с престижным и узнаваемым внешним видом и высокой надежностью.
Структуры в С++
Такие типы данных, как int, float, char и long, являются неотъемлемой частью C/C++ и вам не нужно писать никакого кода, чтобы сообщить компилятору о том, что означают эти слова.
Динамические структуры данных
При разработке программ во многих случаях достаточно использовать простые переменные и массивы. Память под такие объекты выделяется либо на этапе компиляции, либо на этапе выполнения программы.
Динамические структуры данных: дек
Понятие класса как собрания информации, которая включает в себя данные и функции. Создание класса "Дек". Реализация методов: добавления элемента в начало и в конец дека, удаление элемента из начала и конца дека, проверка дека на наличие в нем элементов.
Моделирование работы. Simula
Моделирование работы в машинном зале в терминах Simula. Схема решения задачи в терминах языка Симула. Глобальные переменные и массивы.
Модель системы массового обслуживания на GPSS
Постановка задачи. В студенческом машинном зале расположены две мини-ЭВМ и одно устройство подготовки данных (УПД). Студенты приходят с интервалом 8±3 мин. и треть из них хочет испытать УПД и ЭВМ, а остальные только ЭВМ. Допустимое количество студентов в машинном зале 4 чел., включая работающего на УПД.
Разновидности мультипрограммирования
Общая характеристика основных операций с процессами. Мультипрограммирование как способ организации вычислительного процесса. Цели, алгоритмы и оценка эффективности систем пакетной обработки. Достоинства и недостатки интерактивных операционных систем.
Имитационное моделирование работы систем массового обслуживания
Определение функциональных характеристик систем массового обслуживания (СМО) на основе имитационного моделирования; синтез СМО с заданными характеристиками. Разработка программы на языке SIMNET II; расчет процесса работы СМО; подбор требуемого параметра.
Создание базы данных, состоящей из одной таблицы
Проектирование структуры базы данных. Конструирование структуры будущих таблиц баз данных, основные приемы их заполнения и редактирования. Простая сортировка значений таблицы. Поиск записей по образцу. Как правильно сохранить и загрузить базу данных.
Алгоритмические языки и программирование
Московский авиационный институт (технический университет) ------------------------ Кафедра вычислительной математики и программирования К У Р С О В А Я Р А Б О Т А
Программирование на языках высокого уровня 3
Программирование на языках высокого уровня ч2 Лабораторная №1 Задача 1 Составить программу на языке С/С++, содержащую: - объявления и инициализацию указателей на различные типы объектов:
Динамические структуры данных 4
Динамические структуры данных. Указатели До сих пор мы имели дело с переменными, которые размещаются в памяти согласно определенным правилам, а именно, для локальных переменных, описанных в подпрограмме, память отводиться при вызове подпрограммы; при выходе из нее эта память освобождается, а сами переменные прекращают существование.
Динамические структуры данных стеки
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
Моделирование торгового центра
Министерство Образования Республики Таджикистан Таджикский Технический Университет Кафедра «АСОИ и У» Лабораторная работа на тему: «Моделирование торгового центра»
Создание базы данных состоящей из одной таблицы
Проектирование структуры базы данных. Конструирование структуры будущих таблиц баз данных основные приемы их заполнения и редактирования. Простая сортировка значений таблицы. Поиск записей по образцу. Как правильно сохранить и загрузить базу данных.
Модель системы массового обслуживания на GPSS
Постановка задачи. В студенческом машинном зале расположены две мини-ЭВМ и одно устройство подготовки данных (УПД). Студенты приходят с интервалом 8±3 мин. и треть из них хочет испытать УПД и ЭВМ, а остальные только ЭВМ. Допустимое количество студентов в машинном зале 4 чел., включая работающего на УПД.
Динамические структуры данных 5
Федеральное государственное автономное образовательное учреждение высшего профессионального образования Уральский федеральный университет имени первого Президента России Б.Н. Ельцина
Учет и анализ банкротств 2
Конспект лекций УЧЕТ И АНАЛИЗ БАНКРОТСТВ Составление ликвидационного баланса Ключевым бухгалтерским документом предприятия банкрота является ликвидационный баланс, в котором отражаются все активы предприятия составляющие его конкурсную массу, а также результаты рассмотрения требований кредиторов.