Песни о Паскале

Глава 56 И снова очереди, и снова стеки…

Новейшая версия полицейской базы данных и частотный анализатор текста укрепили ваш опыт по части динамических переменных. И все-таки, один момент нами упущен. Пока мы лишь добавляли данные в кучу, не утруждая себя её очисткой, – в решаемых задачах этого не требовалось. Но так будет не вечно, когда-то придется освобождать кучу от ненужных переменных. В этой главе мы рассмотрим два таких случая на примере знакомых нам очередей и стеков.

Однажды, это было 1-го апреля, придворный программист Ник получил от приятеля странную «электрошку». Письмо содержало загадочный текст, очень похожий на программу, вот несколько его первых строк.

end.

Close(F);

while Pop(S) do Writeln(F, S);

{ Пока стек не пуст, извлекаем и печатаем строки }

Assign(F, 'P_56_1.out'); Rewrite(F);

{ Открываем выходной файл }

Close(F);

end;

Приятель умолял Ника найти здесь ошибку.

Приняв во внимание 1-е апреля, Ник заподозрил розыгрыш и всмотрелся в эту абракадабру внимательней. Вскоре он сообразил, что строки в файле следуют в обратном порядке: последняя стоит первой, а первая – последней. Достойным ответом приятелю, – рассудил Ник, – будет правильный текст этой же программы. Но как переставить строки? Вручную, редактором текста? «Не царское это дело! – возмутился его разум, – пусть этим займется компьютер». И Ник написал программу для преобразования файла. Последуем за Ником.

Вы уже знакомы со стеком – временным хранилищем данных, из которого последний вставленный элемент извлекается первым (сообразно с дисциплиной LIFO). Стек – отличное средство для перестановки данных шиворот навыворот и задом наперед. Хранилищем данных в нашем первом стеке была строка, а хранимыми элементами – символы (загляните в главу 45). Скромные возможности того стека не помешали нам решить задачу о сортировочной горке.

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

Вспомним порядок элементов при вставке их в список: последний элемент оттесняет соседей, становясь на первое место. А это значит, что, извлекая элементы от головы к хвосту списка, мы получим их в обратном порядке (рис. 127).

После извлечения элемента из стека (в данном случае – строки) отпадет нужда в хранившей его динамической переменной. К чему засорять память? Ведь этот ценный ресурс нам ещё пригодится. Так давайте удалять из кучи ненужные динамические переменные.

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

type PRec = ^TRec;     { Тип указатель на запись }

    TRec = record     { Тип запись для хранения связанных строк }

    mStr : string; { хранимая строка }

    mNext : PRec; { указатель на следующую запись }

    end;

Напомню, что со стеком выполняются, по меньшей мере, две операции: помещение в стек PUSH, и извлечение из стека POP. В нашем случае процедура записи в стек будет объявлена так:

procedure Push(const arg : string);

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

Теперь об извлечении из стека. Здесь надо получить не только строку, но и сигнал о состоянии стека: пуст он, или в нём ещё валяется что-то. Поэтому операцию извлечения из стека оформим булевой функцией.

function Pop(var arg : string): boolean;

Строка будет возвращаться через параметр arg, – это ссылка на переменную. Но, если функция вернет FALSE, это будет сигналом того, что стек пуст и строка не возвращена.

На этом закончим рассуждения и обратимся к программе «P_56_1».

{ P_56_1 – перестановка строк файла }

type PRec = ^TRec;     { Тип указатель на запись }

    TRec = record     { Тип запись для хранения связанных строк }

    mStr : string; { хранимая строка }

    mNext : PRec; { указатель на следующую запись }

    end;

var Stack : PRec; { Голова (вершина) стека }

    { Процедура размещения строки в стеке }

procedure Push(const arg : string);

var p : PRec;

begin

New(p);     { создаем новую переменную-запись }

p^.mStr:= arg;     { размещаем строку }

{ размещаем в голове стека }

p^.mNext:= Stack; { указатель на предыдущую запись }

Stack:=p;     { текущая запись в голове стека }

end;

    { Процедура извлечения строки из стека }

function Pop(var arg : string): boolean;

var p : PRec;

begin

Pop:= Assigned(Stack); { Если стек не пуст, то TRUE }

if Assigned(Stack) then begin { Если стек не пуст… }

arg:= Stack^.mStr;     { извлекаем данные из головы стека }

p:= Stack;     { временно копируем указатель на голову }

Stack:= Stack^.mNext; { переключаем голову на следующий элемент }

Dispose(p);     { удаляем ненужный элемент }

end

end;

var F : text; S : string;

begin     {--- Главная программа ---}

Stack:= nil; { Инициализация стека пустым значением }

{ Открываем входной файл }

Assign(F, 'P_56_1.pas'); Reset(F);

{ Пока не конец файла, читаем строки и помещаем в стек }

while not Eof(F) do begin

    Readln(F, S); Push(S);

end;

Close(F);

{ Открываем выходной файл }

Assign(F, 'P_56_1.out'); Rewrite(F);

{ Пока стек не пуст, извлекаем и печатаем строки }

while Pop(S) do Writeln(F, S);

Close(F);

end.

Процедура Push повторяет процедуру вставки элемента в список. А в теле функции Pop гляньте на выделенные операторы. После извлечения строки ненужный теперь элемент стека уничтожается процедурой Dispose(p), – так освобождается память. Но перед этим указатель на следующий элемент надо сохранить в голове списка, иначе мы потеряем ссылку на цепочку оставшихся элементов.

Изваяв программу, Ник испытал её волшебное действие на её собственном тексте. Каково же было его удивление, когда результат совпал с абракадаброй, полученной от приятеля! Вот такое чудесное совпадение!

Ох уж эти танцы… Задачу о танцевальном кружке мы решили в 45-й главе. Освежите её в памяти, поскольку новый вариант решения будет похож на первый.

Только теперь мы изменим имена мальчиков и девочек. В том варианте, как вы помните, дети носили однобуквенные имена, и мы представили их символами. Теперь же мы дадим им настоящие человеческие имена, но для этого и очередь организуем иначе. Как? Вы уже догадались – посредством односвязного списка (рис. 128).

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

Это обстоятельство вынудит нас изменить процедуру удаления первого элемента очереди. Теперь перед удалением надо заполучить указатель на предпоследний элемент списка. В нём надлежит поставить заглушку NIL, чтобы отцепить первый элемент очереди (рис. 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 было высказано предположение, что для записи в танцевальный кружок достаточно одной очереди. Покажите это, создав соответствующую программу. Чем потребуется дополнить механизм работы с очередью?