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

p^.mNext:= p1^.mLinks; { указатель на следующий берем из заголовка }

p1^.mLinks:= p; { заголовок указывает на новый узел }

end;

{ Процедура чтения графа из текстового файла }

procedure ReadData(var F: Text);

var C : Char;

p, q : PNode;

begin

Reset(F);

while not Eof(F) do begin

if not Eoln(F) then begin { если строка не пуста }

Read(F, C); { читаем имя страны }

C:=UpCase(C); { перевод в верхний регистр }

p:= GetPtr(C); { а может эта страна уже существует? }

if not Assigned(p)

then p:= MakeNode(C); { если нет, – создаем }

while not Eoln(F) do begin { чтение стран-соседей до конца строки }

Read(F, C);

C:= UpCase(C);

if C in ['A'..'Z'] then begin { если это имя страны, а не пробел }

q:= GetPtr(C); { проверяем существование страны }

if not Assigned(q) { если не существует, – создаем }

then q:= MakeNode(C);

Link(p, q); { связываем страну p с q }

end

end

end;

Readln(F); { переход на следующую строку файла }

end;

Close(F);

end;

{ Процедура распечатки графа }

procedure ExpoData(var F: Text);

var p : PNode;

q : PLink;

begin

Rewrite(F);

p:= List; { начало просмотра списка стран (узлов) }

while Assigned(p) do begin

Write (F, p^.mName); { название страны }

q:= p^.mLinks; { начало просмотра списка соседей }

while Assigned(q) do begin

Write(F, ' ', q^.mLink^.mName); { название соседа }

q:= q^.mNext; { следующий сосед }

end;

Writeln(F); { конец строки }

p:= p^.mNext; { следующая страна }

end;

Close(F);

end;

var F_In, F_Out : Text; { входной и выходной файла }

begin {--- Главная программа ---}

List:= nil;

Assign(F_In, 'P_57_1.in');

ReadData(F_In); { читаем граф из входного файла }

Assign(F_Out,'P_57_1.out');

ExpoData(F_Out); { печатаем в выходной файл }

end.

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

G I H F

E F D

H I G B

C D B

I H G B A

F G E A

D E C A

B H I C A

A I F D B

Это явно отличается от входных данных, разница налицо, неужели ошибка? Да, порядок следования узлов не совпадает. И порядок перечисления связей в строках тоже. Но нарисованный по этим данным граф оказался копией исходного! Все потому, что порядок перечисления узлов и ребер графа не важен, главное – связи между узлами.

Ознакомившись с графами, мы готовы теперь последовать за придворным программистом Ником. Так айда в следующую главу!

• Граф – это структура, состоящая из узлов и соединяющих их ребер.

• В памяти компьютера граф можно представить списком узлов и списками связей.

• Двунаправленные ребра графа представляются парой указателей.

• Порядок перечисления узлов и связей графа не имеет значения, поскольку не влияет на форму графа.

А) Когда-то страны континента (рис. 130) не поддерживали дипломатических связей. Изобразите отвечающий этой эпохе граф, отражая ребрами дипломатические отношения. Кстати, такой граф без ребер называют лесом.

Б) В пору расцвета континента все страны установили между собой дипломатические отношения. Нарисуйте подобающий граф.

В) В период политического кризиса соседние страны перессорились между собой и разорвали дипломатические отношения. Какие ребра графа уцелели? Нарисуйте его.

Г) Пусть названия стран представляются не буквами, а словами. Возьмите карту Европы и создайте входной файл для нескольких соседних стран, например:

Франция Испания Италия Бельгия Швейцария

Италия Франция Швейцария Словения

и так далее, перечисляя страны-соседи и отделяя их одним или несколькими пробелами. Напишите программу для ввода и вывода такого графа. Что придется изменить в структуре узла?

Ознакомившись с графами, вернемся к программисту Нику, который все ещё царапает прибрежный песочек. «Если бы, – бормочет Ник, – мне надо было попасть из страны «E» в страну «H», то я бы поехал так». И он прочертил жирные стрелки, ведущие к цели через узлы «F» и «G» (рис. 138). «Но это я сообразил, глядя на карту, а без карты можно блуждать вот так», – и нацарапал стрелки, показанные пунктиром.