Реферат

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

Работа добавлена на сайт 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. Реферат Введение в организационное поведение 3
2. Реферат Опознание в уголовном процессе
3. Реферат на тему Online Dating Essay Research Paper I m
4. Отчет по практике Искусствоведение г Ярославля
5. Реферат Наукова організація фінансово-господарського контролю і аудиту
6. Диплом Анализ формирования финансовых результатов деятельности предприятия на примере ООО Водокана
7. Реферат на тему What Is Art And Why Is It
8. Биография на тему Щербатов Михаил Михайлович
9. Реферат на тему Themes In Carver Essay Research Paper John
10. Реферат на тему Jurassic ParkDNA Essay Research Paper A Brief