Очередь

tux 2012.09.19 Структуры данных https://tux.org.ua/?p=605 4109 0

Очередь — структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит с одной стороны последовательности, удаление — с другой. Т. е. работает по принципу FIFO (First-In, First-Out).

Очередь является динамической структурой — с течением времени изменяется и количество, и набор составляющих ее элементов.
Опишем очередь на языке программирования:

Type
   EXO = ^O;
   O = record
      Data : integer;
      Next : EXO;
   end;

Type

EXO = ^O;

O = record

Data : integer;

Next : EXO;

end;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

Операции над очередью

В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:

Var
BeginO, EndO : EXO;

1 2	Var BeginO, EndO : EXO;

где BeginO – соответствует началу очереди и будет использоваться для удаления элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.

Занесение элемента в очередь

Занесение элемента в очередь реализуется как добавлению элемента в конец списка. Рассмотрите процедуру, описанную ниже.

Procedure writeO(Var BeginO, EndO : EXO; c : integer);
Var
   u : EXO;
Begin
   new(u);
   u^.Data := c;
   u^.Next := Nil;
   if BeginO = Nil {проверяем, пуста ли очередь}
      then
         BeginO := u {ставим указатель начала очереди на первый созданный элемент}
      else
         EndO^.Next := u; {ставим созданный элемент в конец очереди}
   EndO := u; {переносим указатель конца очереди на последний элемент}
End;

Procedure writeO(Var BeginO, EndO : EXO; c : integer);

Var

u : EXO;

Begin

new(u);

u^.Data := c;

u^.Next := Nil;

if BeginO = Nil {проверяем, пуста ли очередь}

then

BeginO := u {ставим указатель начала очереди на первый созданный элемент}

else

EndO^.Next := u; {ставим созданный элемент в конец очереди}

EndO := u; {переносим указатель конца очереди на последний элемент}

End;

Извлечение элемента из очереди

Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка. Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди.

Procedure readO(Var BeginO : EXO; Var c : integer);
Var
   u : EXO;
Function FreeO(x1 : EXO): boolean;
Begin
   FreeO := (x1 = Nil);
End;
Begin
   if FreeO(BeginO)
      then
         writeln('Очередь пуста')
      else
         begin
            c := BeginO^.Data; {считываем искомое значение в переменную с}
            u := BeginO; {ставим промежуточный указатель на первый элемент очереди}
            BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
            dispose(u); {освобождаем память, занятую уже ненужным первым элементом}
         end;
End;

Procedure readO(Var BeginO : EXO; Var c : integer);

Var

u : EXO;

Function FreeO(x1 : EXO): boolean;

Begin

FreeO := (x1 = Nil);

End;

Begin

if FreeO(BeginO)

then

writeln('Очередь пуста')

else

begin

c := BeginO^.Data; {считываем искомое значение в переменную с}

u := BeginO; {ставим промежуточный указатель на первый элемент очереди}

BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}

dispose(u); {освобождаем память, занятую уже ненужным первым элементом}

end;

End;

Рассмотрим работу с очередью на примере:

За один просмотр файла действительных чисел напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.

Program Cherga;
Type
   EXO = ^O;
   O = record
      Data : real;
      Next : EXO;
   End;
Var
   i, a, b : Real;
   Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO;
   f : File of real;
   Stroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : real);
Var
   u : EXO;
Begin
   new(u);
   u^.Data := c;
   u^.Next := Nil;
   if BeginO = Nil {проверяем, пуста ли очередь}
      then
         BeginO := u {ставим указатель начала очереди на первый созданный элемент}
      else
         EndO^.Next := u; {ставим созданный элемент в конец очереди}
   EndO := u; {переносим указатель конца очереди на последний элемент}
End;
Procedure Print(BeginO : EXO);
Var
   u : EXO;
Function FreeO(x1 : EXO): boolean;
Begin
   FreeO := (x1 = Nil);
End;
Begin
   if FreeO(BeginO)
      then
         writeln('Очередь пуста')
      else
         begin
            c := BeginO^.Data; {считываем искомое значение в переменную с}
            u := BeginO; {ставим промежуточный указатель на первый элемент очереди}
            BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
            dispose(u); {освобождаем память, занятую уже ненужным первым элементом}
         end;
End;
Begin
   Min := Nil;
   Vibr := Nil;
   Other := Nil;
   EndMin := Nil;
   EndVibr := Nil;
   EndOther := Nil;
   writeln ('Введите имя файла >');
   readln(Stroka);
   writeln ('Введите промежуток >');
   readln(a, b);
   assign(f, Stroka);
   reset(f);
   while not Eof(f) do
      begin
         read(f, i);
         if i<a
            then
               writeO(Min, EndMin, i)
            else
               if (i>=a) and (i<=b)
                  then
                     writeO(Vibr, EndVibr, i)
                  else
                     writeO(Other, EndOther, i)
      end;
   close(f);
   writeln('Числа, меньшие ', a);
   Print(Min);
   writeln('Числа из промежутка [', a, ',' , b, ']');
   Print(Vibr);
   writeln('Числа, большие ', b);
   Print(Other);
End.

Program Cherga;

Type

EXO = ^O;

O = record

Data : real;

Next : EXO;

End;

Var

i, a, b : Real;

Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO;

f : File of real;

Stroka : string;

Procedure writeO(Var BeginO, EndO : EXO; c : real);

Var

u : EXO;

Begin

new(u);

u^.Data := c;

u^.Next := Nil;

if BeginO = Nil {проверяем, пуста ли очередь}

then

BeginO := u {ставим указатель начала очереди на первый созданный элемент}

else

EndO^.Next := u; {ставим созданный элемент в конец очереди}

EndO := u; {переносим указатель конца очереди на последний элемент}

End;

Procedure Print(BeginO : EXO);

Var

u : EXO;

Function FreeO(x1 : EXO): boolean;

Begin

FreeO := (x1 = Nil);

End;

Begin

if FreeO(BeginO)

then

writeln('Очередь пуста')

else

begin

c := BeginO^.Data; {считываем искомое значение в переменную с}

u := BeginO; {ставим промежуточный указатель на первый элемент очереди}

BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}

dispose(u); {освобождаем память, занятую уже ненужным первым элементом}

end;

End;

Begin

Min := Nil;

Vibr := Nil;

Other := Nil;

EndMin := Nil;

EndVibr := Nil;

EndOther := Nil;

writeln ('Введите имя файла >');

readln(Stroka);

writeln ('Введите промежуток >');

readln(a, b);

assign(f, Stroka);

reset(f);

while not Eof(f) do

begin

read(f, i);

if i<a

then

writeO(Min, EndMin, i)

else

if (i>=a) and (i<=b)

then

writeO(Vibr, EndVibr, i)

else

writeO(Other, EndOther, i)

end;

close(f);

writeln('Числа, меньшие ', a);

Print(Min);

writeln('Числа из промежутка [', a, ',' , b, ']');

Print(Vibr);

writeln('Числа, большие ', b);

Print(Other);

End.

Практическая часть

Заполнить массив 5х5 случайными числами. Создать очередь из элементов массива, причем чтобы начало очереди содержало среднее арифметическое элементов массива. Вывести очередь на экран.

Program Cherga2;
const n=5;
{описание компонент очереди}
type
   List=^Tlist;
   Tlist=record
      data:real;{тип елеменетов в очереди}
      next:List;{указатель на следующий элемент}
   end;
var a:array[1..n,1..n] of real;
   sr,c:real;
   i,j:byte;
   pbegin,pend,u:List;{переменные типа указатель-начало, конец и вспомогательная}
begin
   randomize;
   {создаем массив и находим в нем среднее}
   sr:=0;
   writeln('Исходный массив:');
   for i:=1 to n do
      begin
         for j:=1 to n do
            begin
               a[i,j]:=10*random;
               sr:=sr+a[i,j];
               write(a[i,j]:5:2);
            end;
         writeln;
      end;
   sr:=sr/(n*n);
   writeln('Среднее=',sr:0:2);
   {создаем очередь из одного элемента-среднее}
   new(pbegin);
   pbegin^.next:=nil;
   pbegin^.data:=sr;
   pend:=pbegin;
   {добавляем в конец очереди элементы массива}
   for i:=1 to n do
   for j:=1 to n do
      begin
         new(u);
            u^.next:=nil;
            pend^.next:=u;
            pend:=u;
            pend^.data:=a[i,j];
      end;
   {выводим элементы очереди на экран}
   for i:=1 to n*n+1 do
      begin
         c:=pbegin^.data;
         write(c:5:2);
         pbegin:=pbegin^.next;
      end;
   readln
end.

Program Cherga2;

const n=5;

{описание компонент очереди}

type

List=^Tlist;

Tlist=record

data:real;{тип елеменетов в очереди}

next:List;{указатель на следующий элемент}

end;

var a:array[1..n,1..n] of real;

sr,c:real;

i,j:byte;

pbegin,pend,u:List;{переменные типа указатель-начало, конец и вспомогательная}

begin

randomize;

{создаем массив и находим в нем среднее}

sr:=0;

writeln('Исходный массив:');

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=10*random;

sr:=sr+a[i,j];

write(a[i,j]:5:2);

end;

writeln;

end;

sr:=sr/(n*n);

writeln('Среднее=',sr:0:2);

{создаем очередь из одного элемента-среднее}

new(pbegin);

pbegin^.next:=nil;

pbegin^.data:=sr;

pend:=pbegin;

{добавляем в конец очереди элементы массива}

for i:=1 to n do

for j:=1 to n do

begin

new(u);

u^.next:=nil;

pend^.next:=u;

pend:=u;

pend^.data:=a[i,j];

end;

{выводим элементы очереди на экран}

for i:=1 to n*n+1 do

begin

c:=pbegin^.data;

write(c:5:2);

pbegin:=pbegin^.next;

end;

readln

end.

очередь, программирование

Переменная. Массив. Стек

#:

Очередь

Содержание

Операции над очередью

Занесение элемента в очередь

Извлечение элемента из очереди

Практическая часть

Похожие материалы:

Оставить комментарий