Название: Динамические структуры данных: очереди
Вид работы: реферат
Рубрика: Информатика и программирование
Размер файла: 15.04 Kb
Скачать файл: referat.me-137324.docx
Краткое описание работы: Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой.
Динамические структуры данных: очереди
Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура 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;
}
Похожие работы
-
Динамические структуры данных
При разработке программ во многих случаях достаточно использовать простые переменные и массивы. Память под такие объекты выделяется либо на этапе компиляции, либо на этапе выполнения программы.
-
Односвязный список на основе указателей
Рассмотрение понятия абстрактного типа данных. Реализация операций добавления элемента в пустой список и после указанных данных, удаления конкретного элемента и распечатки записей. Разработка интерфейса, исключающего нелигитимное модифицирование данных.
-
Моделирование работы. Simula
Моделирование работы в машинном зале в терминах Simula. Схема решения задачи в терминах языка Симула. Глобальные переменные и массивы.
-
Алгоритмические языки и программирование
Московский авиационный институт (технический университет) ------------------------ Кафедра вычислительной математики и программирования К У Р С О В А Я Р А Б О Т А
-
Модель системы массового обслуживания на GPSS
Постановка задачи. В студенческом машинном зале расположены две мини-ЭВМ и одно устройство подготовки данных (УПД). Студенты приходят с интервалом 8±3 мин. и треть из них хочет испытать УПД и ЭВМ, а остальные только ЭВМ. Допустимое количество студентов в машинном зале 4 чел., включая работающего на УПД.
-
Отображение АСД на СДХ
Отображения на вектор. Представление АСД в списковой памяти. Структуры данных.
-
Динамические структуры данных: дек
Понятие класса как собрания информации, которая включает в себя данные и функции. Создание класса "Дек". Реализация методов: добавления элемента в начало и в конец дека, удаление элемента из начала и конца дека, проверка дека на наличие в нем элементов.
-
Динамические структуры данных
Разработка алгоритмов на динамических структурах данных. Описание структуры данных "стек". Процедуры добавления и удаления элемента, очистки памяти. Код распечатки содержимого всего стека. Инструкция пользователя, код программы, контрольный пример.
-
Разработка программ с использованием динамической памяти
Указатели как одна из наиболее трудных для освоения возможностей С и одно из наиболее мощных свойств языка программирования. Возможность моделировать передачу по ссылке и создавать и манипулировать динамическими структурами данных. Обработка списков.
-
Динамические структуры данных: двоичные деревья
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов.