Динамические структуры данных: очереди

Что означает Динамические структуры данных: очереди и что это такое? В разделе Информатика, программирование дан подробный ответ и объяснение на вопрос.

Здесь выложено готовое сочинение на тему Динамические структуры данных: очереди, которое вы так же можете использовать как реферат.

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

Наша небольшая команда бывших и действующих преподавателей и авторов со стажем работы от 5-ти лет всегда вам поможет. Всего нами написано и проверено более 10 000 различных работ на образовательные темы. С нами вы получите действительно качестенный материал с уникальным текстом и обязательно хорошую оценку. Удачи в учебе!

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура 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;

}

Подобные материалы

Зашита информации - методы и объекты
Информационная безопасность человека и общества. Технические средства охраны объектов и защиты от
MS Excel
Вычисления в Excel. Формулы и функции: Использование ссылок и имен, перемещение и копирование
Засоби управління перевантаженнями і політики відкидання пакетів
Використання аналзу трафку для попередження перевантажень мереж. Полтика вдкидання хвоста ефект
Написание программы "Угадайка"
Технические характеристики игрового приложения для операционной системы Microsoft Windows.
Розвиток інформаційних технологій в системі охорони здоров’я України
Загальна характеристика комункацй та нформац. Розвиток нформацйних систем в медичних закладах.