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

Бакнелл Джулиан М.

dllError(tdeListCannotExamine, 'Examine');

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

Result := FCursor^.dlnData;

end;

procedure TtdDoubleLinkList.InsertAtCursor(aItem : pointer);

var

NewNode : PdlNode;

begin

{если курсор находится на начальном узле, не генерировать исключение, а перейти на следующий узел}

if (FCursor = FHead) then

MoveNext;

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

NewNode := PdlNode (DLNodeManager.AllocNode);

NewNode^.dlnData := aItem;

NewNode^.dlnNext := FCursor;

NewNode^.dlnPrior := FCursor^.dlnPrior;

NewNode^.dlnPrior^.dlnNext := NewNode;

FCursor^.dlnPrior := NewNode;

FCursor := NewNode;

inc(FCount);

end;

function TtdDoubleLinkList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdDoubleLinkList.IsBeforeFirst;

boolean;

begin

Result := FCursor = FHead;

end;

function TtdDoubleLinkList.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

procedure TtdDoubleLinkList.MoveAfterLast;

begin

{установить

курсор на конечный узел}

FCursor := FTail;

FCursorIx := Count;

end;

procedure TtdDoubleLinkList.MoveBeforeFirst;

begin

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

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.MoveNext;

begin

{переместить курсор по его прямому указателю}

if (FCursor <> FTail) then begin

FCursor := FCursor^.dlnNext;

inc(FCursorIx);

end;

end;

procedure TtdDoubleLinkList.MovePrior;

begin

{переместить курсор по его обратному указателю}

if (FCursor <> FHead) then begin

FCursor := FCursor^.dlnPrior;

dec(FCursorIx);

end;

end;

Если сравнить приведенный код с его эквивалентом для односвязных списков (листинг 3.9), можно понять, каким образом дополнительные обратные связи влияют на реализацию методов. С одной стороны, методы стали немного проще. Так, например, в случае двухсвязных списков для метода MoveNext не нужно вводить переменную FParent. С другой стороны, требуется дополнительный код для обработки обратных ссылок. Примером могут служить методы InsertAtCursor и DeleteAtCursor.

Методы, основанные на использовании индекса, в случае двухсвязного списка реализуются проще, чем в случае односвязного. Единственную сложность представляет метод dllPositionAtNth, предназначенный для установки курсора в позицию с заданным индексом. Вспомните алгоритм для односвязного списка: если

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

Листинг 3.16. Установка курсора на узел с индексом n для класса TtdDoubleLinkList

procedure TtdDoubleLinkList.dllPositionAtNth(aIndex : longint);

var

WorkCursor : PdlNode;

WorkCursorIx : longint;

begin

{проверить, корректно ли задан индекс}

if (aIndex < 0) or (aIndex >= Count) then

dllError(tdeListInvalidIndex, 'dllPositionAtNth');

{для увеличения быстродействия используются локальные переменные}

WorkCursor := FCursor;

WorkCursorIx := FCursorIx;

{обработать наиболее простой случай}

if (aIndex = WorkCursorIx) then

Exit;

{заданный индекс либо перед курсором, либо после него; в любом случае, заданный индекс ближе либо к курсору, либо к соответствующему концу списка; определить самый короткий путь}

if (aIndex < WorkCursorIx) then begin

if ((aIndex - 0) < (WorkCursorIx - aIndex)) then begin

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

WorkCursor := FHead;

WorkCursorIx := -1;

end;

end

else {aIndex > FCursorIx}

begin

if ((aIndex - WorkCursorIx) < (Count - aIndex)) then begin

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

WorkCursor :=FTail;

WorkCursorIx := Count;

end;

end;

{пока индекс рабочего курсора меньше заданного индекса, перемещать рабочий курсор на одну позицию вперед}

while (WorkCursorIx < aIndex) do

begin

WorkCursor := WorkCursor^.dlnNext;

inc(WorkCursorIx);

end;

{пока индекс рабочего курсора больше заданного индекса, перемещать рабочий курсор на одну позицию назад}

while (WorkCursorIx > aIndex) do

begin

WorkCursor := WorkCursor^.dlnPrior;

dec(WorkCursorIx);

end;

{установить реальный курсор равным рабочему курсору}

FCursor := WorkCursor;

FCursorIx := WorkCursorIx;

end;

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