Песни о Паскале
Шрифт:
В) Создайте программу для подсчета в файле слов, составленных из одних и тех же символов: цифр и букв, например: «end» и «deen», «121» и «221». Для каждой такой группы слов программа должна напечатать перечень входящих в них символов (каждый символ – по разу) и количество обнаруженных слов этой группы, например, для приведенных выше слов будет напечатано:
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 – Порядок следования в стеке первых трех строк
После извлечения элемента из стека (в данном случае – строки) отпадет нужда в хранившей его динамической переменной. К чему засорять память? Ведь этот ценный ресурс нам ещё пригодится. Так давайте удалять из кучи ненужные динамические переменные.
Работу начнем, как обычно, с конструирования элемента списка. Этим элементом будет запись, включающая строку и указатель на следующую запись.
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 }