Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Динамические структуры данных: очереди
|
|
Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура 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;
}
Контрольные вопросы и задания
1. Какую структуру данных называют очередью? Что такое хвост и голова очереди?
2. На базе каких структур данных может быть организована очередь?
3. Приведите из жизни примеры организации чего-либо по принципу очереди.
4. Используя очередь, напечатайте сначала русские символы данной строки, а затем все остальные, сохранив их порядок следования.
5. Составьте и решите задачу с использованием абстрактного типа данных " очередь".
|
|