Студопедия

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

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

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






  • 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 :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.