Динамічні структури даних: черги
Черга
- Це інформаційна структура, в якій для додавання елементів доступний
тільки один кінець, званий хвостом, а для видалення - другий, званий
головою. В англомовній літературі для позначення черг досить часто
використовується абревіатура 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
If 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
