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

Деревенец Олег Виленович

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).

Рис.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 – на второй