Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-06-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 20.2.2025


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

#include

#include

#include

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 > N;

PrintAndAdd(1);

for (I=1;IInf, 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


1. Курсовая на тему Захист населення при радіаційному забрудненні
2. Реферат на тему Пищеварительный тракт
3. Реферат на тему UnH1d Essay Research Paper Lyme Disease
4. Реферат Принципиальные переговоры
5. Курсовая на тему Новые образовательные технологии как средство повышения качества образования
6. Реферат Электронно вычислительные машины и вычислительные системы
7. Сочинение на тему Притчи Господа нашего Иисуса Христа
8. Реферат Пассажирские перевозки 5
9. Диплом Особенности трудового договора о работе в районах Крайнего Севера и местностях приравненных
10. Реферат на тему Податная реформа Петра Великого