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

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

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

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

Наша небольшая команда бывших и действующих преподавателей и авторов со стажем работы от 5-ти лет всегда вам поможет. Всего нами написано и проверено более 10 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;

}

Подобные материалы

Беспроводные сети Wi-Fi
Типы беспроводных сетей: PAN (персональные), WLAN (беспроводные локальные), WWAN (беспроводные сети
Распределенные вычисления на FreePascal под Windows
Установка и настройка MPICH. Простейшая MPI-программа на FreePascal. Запуск MPI-программы. Более
Информатика
ПЛАН-ПPОСПЕКТ учебника ИНФОPМАТИКА для студентов естественнонаучных напpавлений и специальностей
Создание и описание базы данных СТУДЕНТЫ (Отчет по курсу Базы данных)
Отчет по курсу «Базы данных». Задача: создать базу данных «Студенты». Структура базы данных.
Графический метод решения задач линейного программирования
Графический метод как наиболее простой и наглядный метод линейного программирования, его сущность и