Реферат

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 3.6.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. Реферат на тему Achilleus Essay Research Paper AchilleusAchilleus leader of
3. Доклад Carl Louis Ferdinand von Lindemann
4. Реферат на тему Industrial Revolution Governm Essay Research Paper How
5. Реферат Телевидение - как приоритетный вид рекламирования
6. Курсовая Изучение гендерных и возрастных особенностей агрессивного поведения
7. Контрольная работа Теплоэнергетика 2
8. Контрольная работа на тему Научные и вненаучные знания
9. Курсовая на тему Средства обозначения разнонаправленного горизонтального движения
10. Реферат на тему Old Man And The Sea And Santiago