1 2 – 2
d e n – 2
Подсказка: воспользуйтесь списком, записи которого включают в себя множество символов. Для слов, составленных из одинаковых символов, эти множества совпадают.
Глава 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).
Рис.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).
