Студопедия

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

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

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






Then begin. NewNode:=New(pNode); NewNode^.Value:=v;






NewNode: =New(pNode); NewNode^.Value: =v;

NewNode^.NextNode: =fHead; NewNode^.ArcList: = nil;

fHead: =NewNode; Inc(fNodesNumber); end

else Writeln('Узел со значением ', v, ' в графе уже есть');

end; // procedure tOrGraph.AddNode

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

function tOrGraph.DeleteNode(DisNode: pNode): tValue;

// Исключение узла DisNode из графа с исключением инцидентных ему дуг

// и возвращение информации, содержащейся в исключенном узле

Var

Node, PrevNode: pNode; // текущий и предшествующий узлы

Arc, PrevArc: pArc; // текущая и предшествующая дуги

Begin

// 1. Удаление дуг, исходящих из узла DisNode

While DisNode^.ArcList< > nil do begin

Arc: =DisNode^.ArcList; DisNode^.ArcList: = Arc^.NextArc;

Dispose(Arc); Dec(fArcsNumber);

end;

// 2. Поиск и удаление дуг, входящих в узел DisNode

Node: =fHead;

While Node< > nil do begin

Arc: =Node^.ArcList; PrevArc: = nil;

if Arc< > nil then begin // если список дуг узла Node не пуст

While (Arc^.RearNode< > DisNode) and (Arc^.NextArc< > nil) do begin

PrevArc: =Arc; Arc: = Arc^.NextArc;

end;

if Arc^.RearNode=DisNode

then begin // удаление

if PrevArc= nil

then Node^.ArcList: = Arc^.NextArc // удаляется первая дуга

else PrevArc^.NextArc: = Arc^.NextArc; // удаляется не первая дуга

Dispose(Arc); Dec(fArcsNumber);

end;

end;

Node: =Node^.NextNode;

end;

// 3. Исключение узла DisNode из списка узлов графа

DeleteNode: =DisNode^.Value; PrevNode: = nil; Node: =fHead;

While DisNode< > Node do begin

PrevNode: =Node; Node: = Node^.NextNode;

end;

if PrevNode= nil

then fHead: =DisNode^.NextNode // Node – первый узел

else PrevNode^.NextNode: =DisNode^.NextNode; // Node – не первый узел

Dispose(Node); Dec(fNodesNumber);

end; // function tOrGraph.DeleteNode

При выполнении операции просмотра графа в файл поочередно выводятся узлы графа и для каждого узла перечисляются исходящие из него дуги:

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

Var

Node: pNode;

Arc: pArc;

Begin

Node: = fHead;

While Node< > nil do begin

Write(f, 'Узел ', NodeValue(Node), ': ');

Arc: =Node^.ArcList;






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