Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Protected. fHead: pNode; // поле - указатель на начало списка узлов






fHead: pNode; // поле - указатель на начало списка узлов

fNodesNumber: Word; // поле - количество узлов графа

fArcsNumber: Word; // поле - количество дуг графа

Public

property Head: pNode read fHead write fHead;

property NodesNumber: Word read fNodesNumber write fNodesNumber;

property ArcsNumber: Word read fArcsNumber write fArcsNumber;

function NodeValue(Node: pNode): tValue; // значение узла Node

function NodeAddr(v: tValue): pNode; // адрес узла графа со значением v

function ArcAddr(Node1, Node2: pNode): pArc; // смежность узлов

function HeadNode(ArcNode: pArc): pNode; // начальный узел дуги

function RearNode(ArcNode: pArc): pNode; // конечный узел дуги

function Empty: Boolean; // наличие узлов в графе

procedure AddArc(Node1, Node2: pNode); // включение дуги

procedure DeleteArc(Node1, Node2: pNode); // исключение дуги

procedure AddNode(v: tValue); // включение узла

function DeleteNode(DisNode: pNode): tValue; // исключение узла

procedure Build(var f: Text); // построение графа

procedure Revision(var f: Text); // просмотр графа

procedure Clear; // удаление всех узлов графа

constructor Create; // конструктор графа

destructor Destroy; // деструктор графа

end; // tOrGraph

4. Реализация основных операций над ориентированным графом

Вычисление адреса узла графа по значению его информационной части фактически представляет собой поиск этого узла в списке узлов:

function tOrGraph.NodeAddr(v: tValue): pNode; // адрес узла со значением v

Var

Node: pNode;

Begin

if fHead= nil

then NodeAddr: = nil

Else begin

Node: = fHead;

while (Node^.NextNode< > nil) and (Node^.Value< > v) do Node: =Node^.NextNode;

if Node^.Value=v then NodeAddr: = Node else NodeAddr: = nil;

end;

end; // function tOrGraph.NodeAddr

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

function tOrGraph.ArcAddr(Node1, Node2: pNode): pArc;

// Проверка смежности узлов Node1 и Node2

Var

Arc: pArc;

Begin

ArcAddr: = nil; Arc: =Node1^.ArcList;

if Arc< > nil then begin // поиск узла Node2 в списке дуг узла Node1

while (Arc^.NextArc< > nil) and (Arc^.RearNode< > Node2) do Arc: = Arc^.NextArc;

if Arc^.RearNode=Node2 then ArcAddr: = Arc;

end;

end; // function tOrGraph.ArcAddr

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

function tOrGraph.HeadNode(ArcNode: pArc): pNode;

// Начальный узел дуги

Var

Node: pNode;

Arc: pArc;

Begin

Node: = fHead; HeadNode: = nil;






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.