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

Теперь всё сказанное изобразим блок-схемой (рис. 137).

Чтобы облегчить себе дальнейший труд, заготовим две функции и процедуру, а именно:

• функцию для поиска узла по его имени;

• функцию для создания нового узла;

• процедуру для установки связи между двумя узлами.

Функцию поиска узла по его имени объявим так:

function GetPtr(aName : char): PNode;

Она ищет во вспомогательном списке узел по заданному в параметре имени. В случае успеха, функция вернет указатель на узел, а иначе – NIL.

Функция MakeNode создает новый узел графа с заданным именем, вставляет его во вспомогательный список узлов и возвращает указатель на этот узел.

function MakeNode(aName : Char): PNode;

И, наконец, процедура установки связей Link добавляет в список связей первого узла элемент связи со вторым узлом.

procedure Link(p1, p2 : PNode);

Все три подпрограммы очень просты, поскольку работают со списками.

Немногим сложнее будет процедура распечатки графа, она объявлена так:

procedure ExpoData(var F: Text);

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

Остальные детали алгоритма пояснены в программе «P_57_1».

{ P_57_1 – Ввод и вывод графа }

type PNode = ^TNode; { Указатель на запись-узел }

PLink = ^TLink; { Указатель на список связей }

TLink = record { Тип список связей }

mLink : PNode; { указатель на смежный узел }

mNext : PLink; { указатель на следующую запись в списке }

end;

TNode = record { Тип запись для хранения страны (узла графа) }

mName : Char; { Название страны (одна буква) }

mLinks: PLink; { список связей с соседями (смежными узлами) }

mNext : PNode; { указатель на следующую запись в списке }

end;

var List : PNode; { список всех стран континента (узлов графа) }

{ Функция поиска страны (узла графа) по имени страны }

function GetPtr(aName : char): PNode;

var p : PNode;

begin

p:= List; { поиск начинается с головы списка }

{ проходим по элементам списка }

while Assigned(p) do begin

if p^.mName= aName

then break { нашли! }

else p:= p^.mNext; { а иначе следующий }

end;

GetPtr:= p;

end;

{ Функция создает новую страну (узел), вставляет в глобальный список List

и возвращает указатель на новый узел }

function MakeNode(aName : Char): PNode;

var p : PNode;

begin

New(p); { создаем переменную }

p^.mName:= aName; { копируем имя }

p^.mLinks:=nil; { список связей пока пуст }

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

List:= p; { заголовок указывает на новый узел }

MakeNode:= p; { результат выполнения функции }

end;

{ Процедура установки связи узла p1 с узлом p2 }

procedure Link(p1, p2 : PNode);

var p : PLink;

begin

New(p); { создаем переменную–связь }

p^.mLink:= p2; { поле mLink должно указывать на p2 }

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) не поддерживали дипломатических связей. Изобразите отвечающий этой эпохе граф, отражая ребрами дипломатические отношения. Кстати, такой граф без ребер называют лесом.