Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

К сожалению, мы не можем использовать описанный в главе 3 класс связного списка, поскольку нам требуется доступ к узлам, а этот класс был разработан с целью сокрытия структуры узлов. Это один из случаев, когда нельзя использовать заранее стандартные классы и требуется выполнить кодирование от начала до конца. В случае применения двухсвязного списка это не так страшно, поскольку эта структура достаточно проста. Мы создадим связный список с явными начальным и конечным узлами. В результате удаление обычного узла превращается в исключительно простую задачу. Удаление узлов будет выполняться с применением обоих методов Dequeue и Remove класса расширенной очереди по приоритету.

Операции постановки в очередь и пузырькового подъема лишь немногим более сложны. Вначале мы создаем дескриптор, выделяя узел для элемента, и добавляем его в связный список узлов. Поскольку мы добавляем дескрипторы к сортирующему дереву, для доступа к элементам потребуется выполнять разыменование дескрипторов, а при перемещении элемента по сортирующему дереву индекс его новой позиции необходимо сохранять внутри узла. Код реализации методов постановки в очередь и пузырькового подъема приведен в листинге 9.10.

Листинг 9.10. Постановка в очередь и пузырьковый подъем в расширенной очереди по приоритету

procedure TtdPriorityQueueEx.pqBubbleUp(aHandle : pointer);

var

FromInx : integer;

ParentInx : integer;

ParentHandle : PpqexNode;

Handle : PpqexNode absolute aHandle;

begin

{если анализируемый дескриптор больше дескриптора родительского элемента, нужно их нужно поменять местами и продолжить процесс с новой позиции}

{Примечание: родительский узел дочернего узла, имеющего индекс n, имеет индекс (n-1)/2}

FromInx := Handle^.peInx;

if (FromInx > 0) then begin

ParentInx := (FromInx - 1) div 2;

ParentHandle := PpqexNode(FList.List^[ParentInx]);

{если элемент имеет родительский элемент и больше нее о...}

while (FromInx > 0) and

(FCompare (Handle^.peItem, ParentHandle^.peItem) > 0) do

begin

{нужно переместить родительский элемент вниз по дереву}

FList.List^[FromInx] := ParentHandle;

ParentHandle^.peInx := FromInx;

FromInx := ParentInx;

ParentInx := (FromInx - 1) div 2;

ParentHandle := PpqexNode(FList.List^[ParentInx]);

end;

end;

{сохранить элемент в правильной позиции}

FList.List^[FromInx] := Handle;

Handle^.peInx := FromInx;

end;

function TtdPriorityQueueEx.Enqueue(aItem : pointer): TtdPQHandle;

var

Handle : PpqexNode;

begin

{создать новый узел для связного списка}

Handle := AddLinkedListNode(FHandles, aItem);

{добавить дескриптор в конец очереди}

FList.Add(Handle);

Handle^.peInx := pred(FList.Count);

{теперь нужно выполнить его пузырьковый подъемна максимально возможный уровень}

if (FList.Count > 1) then

pqBubbleUp(Handle);

{вернуть дескриптор}

Result := Handle;

end;

Подобно методу Enqueue, все эти косвенные ссылки несколько усложняют метод Dequeue, но в коде все же можно распознать стандартные операции исключения из очереди и просачивания.

Листинг 9.11. Исключение из очереди и просачивание в расширенной очереди по приоритету

procedure TtdPriorityQueueEx.pqTrickleDown(aHandle : TtdPQHandle);

var

FromInx : integer;

MaxInx : integer;

ChildInx : integer;

ChildHandle : PpqexNode;

Handle : PpqexNode absolute aHandle;

begin

{если анализируемый элемент меньше одного из своих дочерних элементов, его нужно поменять местами с большим дочерним элементом и продолжить процесс из новой позиции}

FromInx := Handle^.peInx;

MaxInx := pred(FList.Count);

{вычислить индекс левого дочернего узла}

ChildInx := succ(FromInx * 2);

{если имеется по меньшей мере правый дочерний элемент, необходимо вычислить индекс большего дочернего элемента...}

while (ChildInx <= MaxInx) do

begin

{если есть хоть один правый дочерний узел, вычислить индекс наибольшего дочернего узла}

if ((ChildInx+1) <= MaxInx) and

(FCompare(PpqexNode(FList.List^[ChildInx])^.peItem, PpqexNode(FList.List^[ChildInx+ 1])^.peItem) < 0) then

inc(ChildInx);

{если элемент больше или равен большему дочернему элементу, задача выполнена}

ChildHandle := PpqexNode(FList.List^[ChildInx]);

if (FCompare (Handle^.peItem, ChildHandle^.peItem) >= 0) then

Break;

{в противном случае больший дочерний элемент нужно переместить вверх по дереву, а сам элемент - вниз}

FList.List^[FromInx] ChildHandle;

ChildHandle^.peInx := FromInx;

FromInx := ChildInx;

ChildInx := succ(FromInx * 2);

end;

{сохранить элемент в правильной позиции}

FList.List^[FromInx] := Handle;

Handle^.peInx := FromInx;

end;

function TtdPriorityQueueEx.Dequeue : pointer;

var

Handle : PpqexNode;

begin

{проверить наличие элементов, которые нужно исключить из очереди}

if (FList.Count = 0) then

pqError(tdeQueueIsEmpty, 'Dequeue');

{вернуть корневой элемент, удалить его из списка дескрипторов}

Handle := FList.List^[0];

Result := Handle^.peItem;

DeleteLinkedListNode(FHandles, Handle);

{если очередь содержала только один элемент, теперь она пуста}

if (FList.Count = 1) then

FList.Count := 0

{если она содержала два элемента, нужно просто заменить корневой элемент одним из оставшихся дочерних элементов. Очевидно, что при этом свойство пирамидальности сохраняется}