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

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;