Общая схема реализации автомата как списка.

Атрибуты вершин графа.

На каждую стрелку отдельное поле, хранящее указатель на вершину, к которой ведёт эта стрелка.

Светофор

1 2 3 4 5 6 7 8

К

З

Ж

5 7 3

7. 5

type tIndex=1..nMax;

tList=record

content:array[tIndex] of tNode;

head:tIndex;

end;

tNode=record

info:tInfo; {Атрибуты вершины}

next:tIndex;

end;

tGraphNode=record

info:tInfo[tIndex] of tNode;

left,right:tIndex;

end;

Варианты – перечень полей-указателей. Например, для бинарного дерева – left,right:tIndex. Либо массив-указатель, либо список.

Новый способ требует больше памяти. Окупится ли «жертва» эффективной вставки и удаления? Убедимся в этом (оставим на время проблемы, связанные с обработкой кучи).

Задача. Включить в список List компоненту x после компоненты.

procedure Include(var List:tList;x:tInfo;AfterPtr:tIndex);

var NewPtr:tIndex;

begin

{Взять первый свободный индекс NewPtr из кучи}

GetHeap(List,NewPtr); After NewPtr

with List do  

ai

x

begin

content[NewPtr].next:=content[AfterPtr].next;

content[AfterPtr].next:=NewPtr;

content[NewPtr].info:=x;

end;

end;

Замечание: процедура Include корректно работает, если известна ссылка на предыдущую компоненту, после которой надо вставлять.

Техническая проблема: она не может включать в пустой список. Не хочется писать отдельную процедуру для включения в пустой список. Проверять же непустоту списка в процедуре Include неэффективно.

Решение: расширить тип Index до 0..nMax и при инициализации списка поставить в него фиктивную нулевую компоненту («болванчик» или «фантом»).

procedure Init(List:tList);

begin

with list do

begin

content[0].next:=0;

head:=0;

end;

{Инициализировать кучу}

end;

{Удаление элемента из списка, стоящего после компоненты AfterPtr}

procedure Exclude(var list:tList;AfterPtr:tIndex);

AfterPtr

 j

a_i+1

j₂

a_i+2

a_i

a_i

j₁

 (удаление)

{Работает в предположении, что удалённая компонента существует}

var ThisPtr:tIndex;

begin

with list do

begin

ThisPtr:=content[AfterPtr].next;

content[AfterPtr].next:=content[ThisPtr].next;

{Сборка мусора – возвратить освободившуюся компоненту в кучу}

PutHeap(List,ThisPtr);

end;

end;