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

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

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

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

Мы команда учителей и репетиторов со стажем работы более 20 лет. За это время нами проверено и написано более 100 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;

}

Похожие материалы

Реляционная модель данных в системах управления базами данных
Основные понятия реляционных баз данных. Ограничительные условия, поддерживающие целостность.
Интернет-аукционы
Дизайнерская разработки сайта интернет-аукциона с помощью HTML-кода. Использование тегов для
Возможности пакета Mathcad, СУБД Microsoft Access
Особенности применения пакета Mathcad. Решение уравнений и систем уравнений с помощью блока решения
Word
Microsoft Word текстовий редактор для створення редагування текстових документв. Листи факси,
Работа с бинарными данными и реестром Windows на платформе .NET
В статье описывается набор классов, которые могут использоваться для быстрой работы с бинарными