Песни о Паскале — страница 87 из 112

{ размещаем указатель в голове очереди }
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 – на второй
      (или на тот-же самый, если в очереди всего один элемент) }
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-й главе, превратила эту карту в следующий файл.

A B D F I
B A C I H
C B D
D A C E
E D F
F A E G
G H I F
H G I B
I A B G H

В каждой строке файла представлены соседи одной страны: первый символ – это название самой страны, а последующие – её соседи, перечисленные в произвольном порядке. В любом порядке могут следовать и сами строки, – от этого карта не изменится, согласны? Итак, этот файл содержал данные для поиска кратчайшего маршрута.

Данные были, только решение куда-то ускользало. Вот берег озера, где спрятался Ник. Его рука в который раз царапает на мокром песке одну и ту же картинку (рис. 131).

Рис.131 – Картинка на мокром песке

Здесь вместо разделяющих царства границ, Ник нацарапал соединяющие их дороги. «Вот по этим дорогам поедут купцы, – размышлял он, – но как именно?». Озарение явилось внезапно. «Постой-ка, мне знакома эта картинка! Неужто граф? Я что-то читал о них, надо бы вспомнить!». Оставим ненадолго озаренного Ника, и выясним, что это за штука такая – граф?

Видимое представление графа

Слово «граф» намекает на рисование, графику. Но программисты и математики признают графом не любую картинку. Граф для них – это сеть связанных между собой объектов. Объекты называют вершинами или узлами графа, а связи между ними – ребрами или дугами. В англоязычной литературе используют термины Node – узел, и Link – связь.

Вот знакомая картинка – схема московского метро (Рис. 132), это пример графа. Здесь станции являются узлами графа, а пути между ними – ребрами. Соседние узлы графа называют смежными. Кстати, нырнувший в метро пассажир решает ту же задачу, что и Ник: ищет кратчайший путь между двумя станциями.

Рис.132 – Схема московского метрополитена – это граф

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

Мы рассмотрели внешнее, видимое представлении графа, теперь обратимся к его внутреннему представлению в памяти компьютера.

Внутреннее представление графа

С внутренним представлением графа вы отчасти знакомы. Не удивляйтесь, ведь односвязный список – это тоже граф. Элементы списка – это узлы графа, а связи между элементами – это ребра. И хотя связь между узлами списка однонаправленная, такие графы тоже имеют право на жизнь. Разве нет дорог с односторонним движением?

Рис. 133 – Односвязный список – это разновидность графа

Годится ли такой список для представления графа, нацарапанного Ником? Рисунок на песке очевидно сложнее списка, – в нём много связей между узлами. К тому же связи на схеме Ника двунаправленные, ведь по дорогам можно ехать в обе стороны. Для представления такого графа требуется что-то похитрее списка. Но в этой замысловатой конструкции найдется место и односвязным спискам.