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

Заказать работу

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

}

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://comp-science.narod.ru

Другие материалы

  • Образ страны: структура и динамика
  • ... другому, так и в трансформациях основных выделяемых типов географических образов. За пределами конкретных образно-географических типологий динамика и структура образа страны в большой степени может зависеть от мощных макрогеокультурных образов, лежащих в основе целого образно-географического." ...

  • Моделирование динамических процессов в пневмоцилиндре
  • ... была составлена расчётная схема, а также составлены дифференциальные уравнения, описывающие динамические процессы в пневмоцилиндре. На основании дифференциальных уравнений была разработана модель пневмоцилиндра. Получены графики, описывающие изменение перемещения поршня в зависимости от изменения ...

  • Изучение внутренней структуры кимберлитовмещающей толщи и поиски кимберлитовых тел сейсморазведкой МОГТ и МПВ
  • ... амплитуд. Подобная картина наблюдается также на Мархинском кимберлитовом теле неясной морфологии, расположенном в этом же районе. Интрузии основного состава (дайки и пласты траппов) по своей внутренней структуре отличаются от кимберлитовых трубок более однородным строением, следовательно, имеют ...

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

  • Медико-психологические последствия боевой психической травмы: клинико-динамические и лечебно-реабилитационные аспекты
  • ... патофизиологический уровень; адаптивная перестройка психологических процессов – в дизадаптирующие патопсихологические изменения. Формируется механизм боевого стрессорного повреждения психобиологического субстрата личности – боевой психической травмы, который проявляется болезненными расстройствами ...

  • Генезис и структура символического в структурной киноэстетике Эйзенштейна
  • ... природу к организму. И если основание определения детерминировано, то основание на основе преднамеренности рефлексии – спонтанно. В контексте структурной киноэстетики Эйзенштейна структура кинофразы предстает как связь «органического целого» (значения) и элемента периферийной серии («цепочки») ...

  • Динамическое программирование (задача о загрузке)
  • ... критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»: 1.2 Примеры задач динамического программирования Задача планирования рабочей силы: При выполнении некоторых проектов число рабочих, необходимых для выполнения какого-либо ...

  • Анализ задачи общего воздействия динамическим магнитным полем на человека и формирование требований на технические средства комплексной магнитотерапии
  • ... лечения; ·     конструирование эффективных технических средств для создания заданных полей вокруг человека; ·     исследование механизмов воздействия динамических магнитных полей (ДМП) на организм человека и его важнейшие функции; ·   & ...

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

  • Динамические и статистические закономерности в природе
  • ... и импульса). Все физические законы делятся на две большие группы: динамические и статистические. Динамическими называют законы, отражающие объективную закономерность в форме однозначной связи физических величин. Динамическая теория — это теория, представляющая совокупность физических законов. ...

  • Об оценке динамических конкурентных преимуществ банка
  • ... с прямыми и потенциальными конкурентами на рынке банковских услуг в целом или на отдельном его сегменте. Для осуществления оценки динамических конкурентных преимуществ банка был предложен методический подход, в основе которого лежит расчет интегрального показателя, всесторонне характеризующего ...

  • Мономиальные динамические системы
  • ... 000 - , 001 - , 010 - , 011 - , 100 - , 101 - , 110 - , 111 - . Фазовое пространство  изображено на рисунке 1.2.3. Рис. 1.2.3. Фазовое пространство . Теорема 1.2.1. Пусть  – мономиальная динамическая система. Тогда  – система конечных элементов тогда, и только тогда, когда и ...

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

  • Линейные списки. Стек. Дек. Очередь
  • ... » или F10. Заключение В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие ...

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

Каталог учебных материалов

Свежие работы в разделе

Наша кнопка

Разместить ссылку на наш сайт можно воспользовавшись следующим кодом:

Контакты

Если у вас возникли какие либо вопросы, обращайтесь на email администратора: admin@kazreferat.info