Неизвестно - Prolog

добавить( ДД, 5, Д).

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

9. 4. Отображение деревьев

Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель

write( Т)

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

Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).

Рис. 9. 16. (а) Обычное изображение дерева. (b) То же дерево,

отпечатанное процедурой отобр(дуги добавлены для ясности).

Давайте определим процедуру

отобр( Т)

так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:

Для того, чтобы отобразить непустое дерево Т, необходимо:

(1) отобразить правое поддерево дерева Т с отступом вправо на расстояние Н;

(2) отпечатать корень дерева Т;

(3) отобразить левое поддерево дерева Т с отступом вправо на расстояние Н.

Величина отступа Н, которую можно выбирать по желанию, - это дополнительный параметр при отображении деревьев. Введем процедуру

отобр2( Т, Н)

печатающую дерево Т с отступом на Н пробелов от левого края листа. Связь между процедурами отобри отобр2такова:

отобр( Т) :- отобр2( Т, 0).

На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.

отобр( Т) :-

отобр2( Т, 0).

отобр2( nil, _ ).

отобр2( дер( L, X, R), Отступ) :-

Отступ2 is Отступ + 2,

отобр2( R, Отступ2),

tab( Отступ), write( X), nl,

отобр( L, Отступ2).

Рис. 9. 17. Отображение двоичного дерева.

Упражнение

9. 14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.

Посмотреть ответ

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

9. 5. Графы

9. 5. 1. Представление графов

Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер , причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами . Дуги задаются упорядоченными парами. Такие графы называются направленными . Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 6.18 показаны примеры графов.

В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Например, графы, показанные иа рис. 9.18, можно представить в виде следующего множества предложений:

связь( а, b).

связь( b, с).

. . .

дуга( s, t, 3).

дуга( t, v, 1).

дуга( u, t, 2).

. . .

Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. Тогда (ненаправленный) граф рис. 9.18 примет вид:

G1 = граф( [a, b, c, d],

[р( а, b), р( b, d), р( b, с), p( c, d)] )

Рис. 9. 18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.