Олег Деревенец - Песни о Паскале

1 2 – 2

d e n – 2

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

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

Однажды, это было 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 { Тип запись для хранения связанных строк }