Новые книги
 Вниманию читателей предлагается справочник по PHP.Справочник предназначается для людей, уже освоивших азы программирования на языке PHP. Справочник создан на основе информации, предоставленной на сайте «Справочник Web-языков» www.spravkaweb.ru. |
 Windows XP – это одна из самых популярных операционных систем. Дома, на работе, в Интернет-кафе вы не сможете работать на компьютере, не умея работать с этой операционной системой.С помощью этой книги вы быстро освоите все необходимые навыки для работы с Windows XP. Прочитав ее, вы узнаете, как установить, настроить и управлять этой операционной системой. |
39. Очереди
Очередью называется динамическая структура данных, добавление ком-
поненты в которую производится в один конец, а выборка осуществляется
с другого конца. Очередь работает по принципу:
FIFO (First-In, First-Out) -
поступивший первым, обслуживается первым.
Для формирования очереди и работы с ней необходимо иметь три пере-
менные типа указатель, первая из которых определяет начало очереди,
вторая - конец очереди, третья - вспомогательная.
Описание компоненты очереди и переменных типа указатель дадим сле-
дующим образом:
type
PComp=^Comp;
Comp=record
D:T;
pNext:PComp
end;
var
pBegin, pEnd, pAux: PComp;
где pBegin - указатель начала очереди, pEnd - указатель конца очере-
ди, pAux - вспомогательный указатель.
Тип Т определяет тип данных компоненты очереди.
Начальное формирование очереди выполняется следующими операторами:
ЙННННН» ЙННННН» ЙННННН»
New(pBegin); є *ДДєДДДї є є є є
ИНННННј і єНННННє ИНННННј
pBegin АДД>є є pEnd
ИНННННј
ЙННННН» ЙННННН» ЙННННН»
pBegin^.pNext:=NIL; є *ДДєДДДї є є є є
ИНННННј і єНННННє ИНННННј
pBegin АДД>є NIL є pEnd
ИНННННј
ЙННННН» ЙННННН» ЙННННН»
pBegin^.D:=D1; є *ДДєДДДї є D1 є є є
ИНННННј і єНННННє ИНННННј
pBegin АДД>є NIL є pEnd
ИНННННј
ЙННННН» ЙННННН» ЙННННН»
pEnd:=pBegin; є *ДДєДДДї є D1 є ЪДДДєДД* є
ИНННННј і єНННННє і ИНННННј
pBegin АДД>є NIL є<ДДЩ pEnd
ИНННННј
Добавление компоненты в очередь производится в конец очереди:
New(pAux);
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є
ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј
pBegin АДД>є NIL є<ДДЩ pEnd є є<ДДЩ pAux
ИНННННј ИНННННј
pAux^.pNext:=NIL;
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є
ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј
pBegin АДД>є NIL є<ДДЩ pEnd є NIL є<ДДЩ pAux
ИНННННј ИНННННј
pBegin^.pNext:=pAux;
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є
ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј
pBegin АДД>є * є<ДДЩ pEnd є NIL є<ДДЩ pAux
ИНННННј ИНННННј
і ^
і і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
pEnd:=pAux;
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є є *ДДєДДДї є є ЪДДДєДД* є
ИНННННј і єНННННє ИНННННј і єНННННє і ИНННННј
pBegin АДД>є * є pEnd АДД>є NIL є<ДДЩ pAux
ИНННННј ИНННННј
і ^
і і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
pEnd^.D:=D2;
ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є є D2 є ЪДДДєДД* є
ИНННННј і єНННННє єНННННє і ИНННННј
pBegin АДД>є *ДДєДДДДДДДДДДДДДДДДДДДД>є NIL є<ДДЩ pEnd
ИНННННј ИНННННј
Добавление последующих компонент производится аналогично.
Выборка компоненты из очереди осуществляется из начала очереди,
одновременно компонента исключается из очереди. Пусть в памяти ЭВМ
сформирована очередь, состоящая из трех элементов:
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є є D2 є є D3 є ЪДДДєДД* є
ИНННННј і єНННННє єНННННє єНННННє і ИНННННј
pBegin АДД>є *ДДєДДДДДД>є *ДДєДДДДДД>є NIL є<ДДЩ pEnd
ИНННННј ИНННННј ИНННННј
Выборка компоненты выполняется следующими операторами:
D1:=pBegin^.D;
pBegin:=pBegin^.pNext;
ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»
є *ДДєДДДї є D1 є є D2 є є D3 є ЪДДДєДД* є
ИНННННј і єНННННє єНННННє єНННННє і ИНННННј
pBegin і є є ЪДД>є *ДДєДДДДДД>є NIL є<ДДЩ pEnd
і ИНННННј і ИНННННј ИНННННј
і і
АДДДДДДДДДДДДДЩ
Пример. Составить программу, которая формирует очередь, добавляет
в нее произвольное количество компонент, а затем читает все компонен-
ты и выводит их на экран дисплея. В качестве данных взять строку сим-
волов. Ввод данных - с клавиатуры дисплея, признак конца ввода -
строка символов END.
Program QUEUE;
uses Crt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= record
sD:Alfa;
pNext:PComp
end;
var
pBegin, pEnd: PComp;
sC: Alfa;
Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);
begin
New(pBegin);
pBegin^.pNext:=NIL;
pBegin^.sD:=sC;
pEnd:=pBegin
end;
Procedure AddQueue(var pEnd:PComp; var sC:Alfa);
var pAux: PComp;
begin
New(pAux);
pAux^.pNext:=NIL;
pEnd^.pNext:=pAux;
pEnd:=pAux;
pEnd^.sD:=sC
end;
Procedure DelQueue(var pBegin: PComp; var sC: Alfa);
begin
sC:=pBegin^.sD;
pBegin:=pBegin^.pNext
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateQueue(pBegin,pEnd,sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddQueue(pEnd,sC)
until sC='END';
writeln(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');
repeat
DelQueue(pBegin,sC);
writeln(sC);
until pBegin=NIL
end.