Рис.128 – Размещение в очереди трех строк
Кажется, что этот рисунок совпадает с рисунком для стека. Так оно и есть. Только элементы теперь извлекаются в ином порядке. Первым элементом в очереди назначим тот, что в хвосте списка. Значит, по сравнению со стеком, в очереди все наоборот: первым элементом очереди является последний элемент списка, и для доступа к нему придется пробежать по всей цепочке ссылок.
Это обстоятельство вынудит нас изменить процедуру удаления первого элемента очереди. Теперь перед удалением надо заполучить указатель на предпоследний элемент списка. В нём надлежит поставить заглушку NIL, чтобы отцепить первый элемент очереди (рис. 129). В этом состоит главная премудрость обращения с очередью строк.
Рис.129 – Отцепление первого элемента очереди
Так же как и для стека, для очереди надо запрограммировать, по меньшей мере, две операции: установку и извлечение из нее.
Процедуру установки в очередь PutInQue объявим так:
procedure PutInQue(var Que: PRec; const arg: string);
Два её параметра – это ссылка на очередь (на голову списка) и помещаемая в очередь строка.
Для извлечения из очереди потребуется уже не процедура, а функция, назовем её GetFromQue, и объявим так:
function GetFromQue(var Que: PRec; var arg: string): boolean;
Здесь опять заметно сходство со стеком: как только очередь окажется пустой, функция сообщит об этом, вернув значение FALSE. И тогда мы отвергнем возвращаемый через ссылку arg результат.
Осталось обсудить ещё одну мелочь: организацию входных данных с тем, чтобы отличать мальчиков от девочек. Имена детей поместим в файл «P_56_2.IN», а для различения мальчиков и девочек, впечатаем имена девочек с некоторым отступом (с одним или несколькими пробелами в начале строки). Вот пример такого входного файла.
Ваня
Петя
Гриша
Маша
Наташа
Коля
Семен
Света
Теперь вы готовы рассмотреть программу «P_56_2».
{ P_56_2 – Запись в танцевальный кружок, версия 2 }
type PRec = ^TRec; { Тип указатель на запись }
TRec = record { Тип запись для хранения связанных строк }
mStr : string[31]; { хранимая строка (имя) }
mNext : PRec; { указатель на следующую запись }
end;
{ Процедура размещения строки в очереди }
procedure PutInQue(var Que: PRec; const arg: string);
var p: PRec;
begin
New(p); { создаем новую переменную-запись }
p^.mStr:= arg; { размещаем строку }
{ размещаем указатель в голове очереди }
p^.mNext:= Que; { указатель на предыдущую запись }
Que:=p; { текущая запись в голове очереди }
end;
{ Извлечение строки из начала очереди (из конца списка) }
function GetFromQue(var Que: PRec; var arg: string): boolean;
var p1, p2: PRec;
begin
GetFromQue:= Assigned(Que);
if Assigned(Que) then begin
{ Поиск первого элемента очереди }
p1:= Que; p2:=p1;
{ если в очереди только один элемент, цикл не выполнится ни разу! }
while Assigned(p1^.mNext) do begin
p2:=p1; { текущий }
p1:=p1^.mNext; { следующий }
end;
{ теперь p1 указывает на первый элемент очереди, а p2 – на второй
(или на тот-же самый, если в очереди всего один элемент) }
arg:= p1^.mStr; { извлекаем данные }
if p1=p2 { если в очереди был один элемент… }
then Que:= nil { очередь стала пустой }
else p2^.mNext:= nil; { а иначе "отцепляем" первый элемент }
Dispose(p1); { освобождаем память первого элемента }
end;
end;
var
Boys : PRec; { очередь мальчиков }
Girls : PRec; { очередь девочек }
S1, S2 : String; { строки с именами }
Boy: boolean; { признак чтения имени мальчика }
F_In, F_Out : Text; { входной и выходной файла }
begin {--- Главная программа ---}
{ Очищаем очереди мальчиков и девочек }
Boys := nil ; { очередь мальчиков }
Girls := nil; { очередь девочек }
Assign(F_In, 'P_56_2.in'); Reset(F_In);
Assign(F_Out,'P_56_2.out'); Rewrite(F_Out);
{ Цикл обработки входного потока }
while not Eof(F_In) do begin
Readln(F_In, S1); { выбираем имя из входного потока }
Boy:= S1[1]<>' '; { строки с именами девочек начинаются с пробела! }
while S1[1]=' ' do Delete(S1,1,1);
if Boy
then begin { если это мальчик…}
if GetFromQue(Girls, S2) { если в очереди есть девочка }
then Writeln(F_Out,S1+' + '+S2) { пару -> в выходной поток }
else PutInQue(Boys, S1); { а иначе мальчика в очередь }
end
else begin { а если это девочка…}
if GetFromQue(Boys, S2) { если в очереди есть мальчик }
then Writeln(F_Out,S2+' + '+S1) { пару -> в выходной поток }
else PutInQue(Girls, S1); { а иначе девочку в очередь }
end
end;
Close(F_In); Close(F_Out);
end.
Вот результат обработки входного файла:
Ваня + Маша
Петя + Наташа
Гриша + Света
Как видите, из 8 детей сформированы лишь три пары, и кто-то ожидает в сторонке.
Итоги
• Односвязные списки – это основа для построения разнообразных структур данных, в том числе очередей и стеков.
• Очереди и стеки, построенные на списках, могут хранить данные любых типов, при этом общий объём хранимых данных ограничивается лишь размером кучи.
• Не засоряйте кучу ненужными переменными, удаляйте их процедурой Dispose.
А слабо?
А) В Borland Pascal (только в нём) существует встроенная функция по имени MemAvail (от Memory – «память», Available – «доступный»). Функция возвращает свободный на текущий момент объём памяти в куче.
Если вы работаете в Borland Pascal, вставьте в процедуру Push и функцию Pop следующие операторы печати:
Writeln(’Push :’, MemAvail);
и
Writeln(’Pop :’, MemAvail);
Проследите таким образом за изменением объёма свободной памяти в куче.
Б) В главе 45 было высказано предположение, что для записи в танцевальный кружок достаточно одной очереди. Покажите это, создав соответствующую программу. Чем потребуется дополнить механизм работы с очередью?
Глава 57
Графомания
Я чуть не забыл о придворном программисте Нике! В 49-й главе он решил задачу о минимальной сумме пошлин. Тогда же купцы уговорили его взяться за программу для поиска кратчайшего маршрута между двумя странами. Купцы страдали от пошлин и хотели сократить свои расходы на границах. Ник принял заказ и впал в размышления.
