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

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

Конструктор Create распределяет при помощи диспетчера узлов еще один дополнительный фиктивный узел - FTail. Как упоминалось во введении к двухсвязным спискам, он предназначен для обозначения конца списка. Начальный и конечный фиктивные узлы вначале будут связаны друг с другом, т.е. ссылка Next начального узла указывает на конечный узел, а ссылка Prior конечного узла - на начальный узел. Естественно, деструктор Destroy будет удалять фиктивный конечный узел и возвращать его вместе с начальным узлов в диспетчер узлов.

Листинг 3.14. Конструктор Create и деструктор Destroy класса TtdDoubleLinkList

constructor TtdDoubleLinkList.Create;

begin

inherited Create;

{сохранить процедуру удаления}

FDispose :=aDispose;

{получить диспетчер узлов}

dllGetNodeManager;

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

FHead := PdlNode (DLNodeManager.AllocNode);

FTail := PdlNode (DLNodeManager.AllocNode);

FHead^.dlnNext := FTail;

FHead^.dlnPrior :=nil;

FHead^.dlnData := nil;

FTail^.dlnNext := nil;

FTail^.dlnPrior := FHead;

FTail^.dlnData := nil;

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

FCursor := FHead;

FCursorIx := -1;

end;

destructor TtdDoiibleLinkList.Destroy;

begin

if (Count <> 0) then

Clear;

DLNodeManager.FreeNode (FHead);

DLNodeManager.FreeNode(FTail);

inherited Destroy;

end;

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

Листинг 3.15. Стандартные для связного списка операции для класса TtdDoubleLinkList

procedure TtdDoubleLinkList.Clear;

var

Temp : PdlNode;

begin

{удалить все узлы, за исключением начального и конечного; если возможно их освободить, то сделать это}

Temp := FHead^.dlnNext;

while (Temp <> FTail) do

begin

FHead^.dlnNext := Temp^.dlnNext;

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

DLNodeManager.FreeNode(Temp);

Temp := FHead^.dlnNext;

end;

{устранить "дыру" в связном списке}

FTail^.dlnPrior := FHead;

FCount := 0;

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

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.DeleteAtCursor;

var

Temp : PdlNode;

begin

{записать в Temp удаляемый узел}

Temp := FCursor;

if (Temp = FHead) or (Temp = FTail) then

dllError(tdeListCannotDelete, 'Delete');

{избавиться от его содержимого}

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

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

Temp^.dlnPrior^.dlnNext := Temp^.dlnNext;

Temp^.dlnNext^.dlnPrior := Temp^.dlnPrior;

FCursor := Temp^.dlnNext;

DLNodeManager.FreeNode(Temp);

dec(FCount);

end;

function TtdDoubleLinkList.Examine : pointer;

begin

if (FCurgor = nil) or (FCursor = FHead) then

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