Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


Тема: Очереди. Основные операции над очередью.

Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.

Изобразим очередь графически:

При программировании на Паскале также считается, что для очереди не существует обход элементов. Доступ возможен только к нижнему элементу структуры.

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

Очередь является динамической структурой – с течением времени изменяется и ее длина, и набор составляющих ее элементов.

Опишем очередь на языке программирования:

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

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

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

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 readO(Var BeginO, EndO : 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;

Задание. Напишите программу, содержащую все необходимые процедуры и функции работы с очередью.

Задание. Чтобы наглядно рассмотреть работу очереди, наберите следующую программу.

Program Demidenko;
Uses
  Crt, Graph;
Type
  sp=^spis;
  spis=record
       elem : byte;
       next : sp;
  End;
Var
  a,
  b : byte;
  s : string;
  gd, gm, c : integer;
  head, some, x : sp;
  bol : boolean;
  ch : char;
Procedure OutHead(x, y : integer);
Begin
  Line(x+20,y+35,x+20,y+20);
  Line(x+20,y+20,x+17,y+25);
  Line(x+20,y+20,x+23,y+25);
  Line(x+23,y+25,x+17,y+25);
  OutTextXY(x+6, y+38, 'head');
End;
Procedure OutX(x, y : integer);
Begin
  Line(x+40,y-15,x+40,y);
  Line(x+40,y,x+37,y-5);
  Line(x+40,y,x+43,y-5);
  Line(x+43,y-5,x+37,y-5);
  OutTextXY(x+28,y-25,'x');
End;
Procedure wiv(x,y:integer;ss:sp);
Begin
  Line(x,y,x+50,y);
  Line(x,y,x,y+20);
  Line(x,y+20,x+50,y+20);
  Line(x+50,y,x+50,y+20);
  Line(x+30,y,x+30,y+20);
  if some=ss
    then
      Begin
        Line(x+40,y-15,x+40,y);
        Line(x+40,y,x+37,y-5);
        Line(x+40,y,x+43,y-5);
        Line(x+43,y-5,x+37,y-5);
        OutTextXY(x+28,y-25,'tail');
      End;
  if ss^.elem<255
    then
      Begin
        str(ss^.elem,s);
        outtextxy(x+10,y+10,s);
      End;
  if ss^.next<>nil
    then
      Begin
        Line(x+40,y+10,x+60,y+10);
        Line(x+60,y+10,x+60,y-10);
        Line(x+60,y-10,x+100,y-10);
        Line(x+100,y-10,x+100,y);
        Line(x+100,y,x+97,y-5);
        Line(x+100,y,x+103,y-5);
        Line(x+103,y-5,x+97,y-5);
        Wiv(x+70, y, ss^.next);
      End
    else
      Begin
        Line(x+40,y+10,x+40,y+30);
        Line(x+40,y+30,x+37,y+25);
        Line(x+40,y+30,x+43,y+25);
        Line(x+43,y+25,x+37,y+25);
        Line(x+35,y+32,x+45,y+32);
        Line(x+36,y+35,x+44,y+35);
        Line(x+38,y+38,x+42,y+38);
      End;
End;
Procedure InsertOch(x : byte);
Begin
  Cleardevice;
  OutTextXY(50,20,'NEW(SOME^.NEXT)');
  new(some^.next);
  some^.next^.next:=nil;
  some^.next^.elem:=255;
  Wiv(20,100,head^.next);
  OutHead(20,100);
  Delay(1000);
  Cleardevice;
  OutTextXY(50,20,'SOME:=SOME^.NEXT');
  some := some^.next;
  some^.next := nil;
  Wiv(20,100,head^.next);
  OutHead(20,100);
  Delay(1000);
  Cleardevice;
  Outtextxy(50,20,'SOME^.NEXT:=NIL');
  Str(x,s);
  OutTextXY(50,40,'SOME^.ELEM:='+s);
  some^.elem := x;
  Wiv(20,100,head^.next);
  OutHead(20,100);
  Delay(1000);
end;
Procedure DelOch;
Begin
  Cleardevice;
  if head^.next^.elem=255
    then
      Begin
        OutTextXY(50,20,'Элемент не существует!');
        Delay(1000);
      End
    else
      if head^.next^.next<>nil
        then
          Begin
            OutTextXY(50,20,'X:=HEAD');
            OutTextXY(50,40,'HEAD:=HEAD^.NEXT');
            Wiv(20,100,head^.next);
            OutX(15,100);
            OutHead(90,100);
            Delay(1000);
            Cleardevice;
            OutTextXY(50,20,'DISPOSE(X)');
            Wiv(20,100,head^.next);
            OutX(20,100);
            OutHead(90,100);
            Setcolor(red);
            Line(20,90,70,130);
            Line(70,90,20,130);
            Setcolor(white);
            Delay(1000);
            Cleardevice;
            head:=head^.next;
            Wiv(20,100,head^.next);
            OutHead(20,100);
          End
        else
          Begin
            OutTextXY(50,20,'DISPOSE(HEAD)');
            Wiv(20,100,head^.next);
            OutHead(20,100);
            setcolor(red);
            Line(20,90,70,130);
            Line(70,90,20,130);
            setcolor(white);
            delay(1000);
            cleardevice;
            OutHead(20,100);
            head^.next^.elem:=255;
            some:=head;
          End;
End;
Begin
  TextBackGround(black);
  ClrScr;
  bol:=false;
  gD := Detect;
  InitGraph(gD, gM,'c:tp7bgi');
  new(head);
  some:=head;
  some^.next:=nil;
  Repeat
  OutTextXY(50,200,'1 * Добавить элемент');
  OutTextXY(50,220,'2 * Удалить элемент');
  OutTextXY(50,240,'Esc Выход');
  ch:=readkey;
  case ch of
    '1' : Begin
      OutTextXY(50,260,'Введите число:');
      Gotoxy(23,17);
      readln(b);
      InsertOch(b);
    End;
    '2' : DelOch;
      #27 : Begin
      CloseGraph;
      Halt;
    End;
  End;
  until bol;
  CloseGraph;
End.

Примеры решения задач

Задание. Рассмотрите приведенные примеры задач. Наберите программы на компьютере, дополните их комментарием и протестируйте их. Имейте в виду, что уже рассмотренные выше подпрограммы в текстах задач пропущены. Будьте готовы объяснить учителю алгоритмы решения задач и продемонстрировать их графически.

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

Program MordovskihK;
Type
  EXO = ^O;
  O = record
       Data : integer;
       Next : EXO;
  End;
Var
  i : Real;
  Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO;
  f : File of real;
  Stroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : real);
  . . .
Procedure PrintO(u : EXO);
  . . .
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, x, i)
          else
            if (i>=a) and (i<=b)
              then
                writeO(Vibr, x, i)
              else
                writeO(Other, x, i)
    end;
  close(f);
  writeln('Числа, меньшие ', а);
  Print(Min);
  writeln('Числа из промежутка [', а, b, ']');
  Print(Vibr);
  writeln('Числа, большие ', b);
  Print(Other);
End.

Пример 2. Из заданного текста перенести все цифры в конец каждой строки, сохранив их порядок.

Program BaranovA;
Type
  EXO = ^O;
  O = record
       Data : integer;
       Next : EXO;
  End;
Var
  i : integer;
  O1, EndO1, O2, EndO2 : EXO;
  f1, f2 : text;
  Name, NewName, Stroka, NewStroka : string;
Procedure writeO(Var BeginO, EndO : EXO; k : char);
  . . .
Procedure readO(u : EXO);
  . . .
ModifStr(St : string, NewSt : string);
Var
  l : char;
  O1 := Nil;
  EndO1 := Nil;
  O2 := Nil;
  EndO2 := Nil;
  NewSt := '';
  for i := 1 to Length(St) do
    if St[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '8', '9', '0']
      then
        writeO(O2, EndO2, St[i])
      else
        writeO(O1, EndO1, St[i]);
        while O1 <> Nil do
          begin
            readO(O1, EndO1, l);
            NewSt := NewSt + l;
          end;
        while O2 <> Nil do
          begin
            readO(O2, EndO2, l);
            NewSt := NewSt + l;
          end;
End;
Begin
  write('Введите имя исходного файла: ');
  readln(Name);
  write('Введите имя файла-результата: ');
  readln(NewName);
  assign(f1, Name);
  assign(f2, NewName);
  reset(f1);
  rewrite(f2);
  while not Eof(f1) do
    begin
      readln(f1, Stroka);
      ModifStr(Stroka, NewStroka);
      writeln(f2, NewStroka);
    end;
  close(f1);
  close(f2);
End.
Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.