|
Динамические структуры данных: очереди
Очередь — это информационная структура, в которой для
добавления элементов доступен только один конец, называемый хвостом, а
для удаления — другой, называемый головой. В англоязычной литературе для
обозначения очередей довольно часто используется аббревиатура 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;
First^.P^.N := Vsp;
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.
|
Пример. Напечатать в порядке возрастания первые 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.
|
Контрольные вопросы и задания
- Какую структуру данных называют очередью? Что такое хвост и голова
очереди?
- На базе каких структур данных может быть организована очередь?
- Приведите из жизни примеры организации чего-либо по принципу очереди.
- Используя очередь, напечатайте сначала русские символы данной строки, а
затем все остальные, сохранив их порядок следования.
- Составьте и решите задачу с использованием абстрактного типа данных
"очередь".
|
Динамические структуры данных