Занятие 3. Очереди. Основные операции над очередью.

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

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

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

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

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

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

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:\tp7\bgi\');

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.

Занятие 4. Самостоятельное решение задач

Задачи для самостоятельного решения:

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

2. Дан текстовый файл. Проанализировав в программе содержимое файла, выберите из него имена и занесите в очередь. Выведите содержимое очереди на экран и посчитайте количество элементов образованной очереди. Решение в программе оформляйте через подпрограммы.

3. Проверьте на равенство две очереди. Решение в программе оформляйте через подпрограммы.

4. Найдите среди трех (4, 5) очередей две одинаковые. Решение в программе оформляйте через подпрограммы.

5. Организовать три очереди с одинаковым количеством элементов, содержащие соответствено имена, отчества и фамилии людей. Составьте очередь из элементов, содержащих наиболее полную информацию о людях, воспользовавшись уже созданными очередями и запросив какую-то дополнительную информацию. Решение в программе оформляйте через подпрограммы.

6. Создайте файл символьного типа. Организовывая очереди по N элементов, cоздайте файл слов по N символов в каждом. Решение в программе оформляйте через подпрограммы.

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

8. Используя очередь, проверьте, какие строки текстового файла являются симметричными. Решение в программе оформляйте через подпрограммы.

9. Используя очередь, проверьте на равенство два текстовых файла. Решение в программе оформляйте через подпрограммы.

10. Создайте две очереди. Проверьте, является ли одна из очередей частью другой. Решение в программе оформляйте через подпрограммы.