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

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

Глава 57 Графомания

Я чуть не забыл о придворном программисте Нике! В 49-й главе он решил задачу о минимальной сумме пошлин. Тогда же купцы уговорили его взяться за программу для поиска кратчайшего маршрута между двумя странами. Купцы страдали от пошлин и хотели сократить свои расходы на границах. Ник принял заказ и впал в размышления.

На рис. 130 показан вид из космоса на континент, где проживал Ник. Тамошние страны именовались, как вы помните, латинскими буквами.

Рис.130 – Карта континента

Программа, что создал Ник в 38-й главе, превратила эту карту в следующий файл.