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

Класс двухсвязного списка

Класс двухсвязного списка

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

Листинг 3.13. Класс TtdDoubleLinkList

TtdDoubleLinkList = class private

FCount : longint;

FCursor : PdlNode;

FCursorIx: longint;

FDispose : TtdDisposeProc;

FHead : PdlNode;

FName : TtdNameString;

FTail : PdlNode;

protected

function dllGetItem(aIndex : longint): pointer;

procedure dllSetItem(aIndex : longint; aItem : pointer);

procedure dllError(aErrorCode : integer;

const aMethodName : TtdNameString);

class procedure dllGetNodeManager;

procedure dllPositionAtNth(aIndex : longint);

public

constructor Create(aDispose : TtdDisposeProc);

destructor Destroy; override;

function Add(aItem : pointer): longint;

procedure Clear;

procedure Delete(aIndex : longint);

procedure DeleteAtCursor;

function Examine : pointer;

function First : pointer;

function IndexOf(aItem : pointer): longint;

procedure Insert(aIndex : longint; aItem : pointer);

procedure InsertAtCursor(aItem : pointer);

function IsAfterLast : boolean;

function IsBeforeFirst : boolean;

function IsEmpty : boolean;

function Last : pointer;

procedure MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

procedure Sort(aCompare : TtdCompareFunc);

property Count : longint read FCount;

property Items[aIndex : longint] : pointer

read dllGetItem write dllSetItem; default;

property Name : TtdNameString read FName write FName;

end;

Как видите, этот интерфейс очень похож на интерфейс класса TtdSingleLinkList. Собственно, так и должно быть. Для пользователя должно быть безразлично, какой класс он выбирает, оба они должны работать одинаково. Сам выбор односвязного или двухсвязного списка должен зависеть от назначения. Если большая часть перемещений курсора направлена вперед и доступ к случайным элементам выполняется редко, эффективнее использовать односвязный список. Если же высока вероятность того, что список будет проходиться как в прямом, так и в обратном направлениях, то, несмотря на большие требования к памяти, лучше выбрать двухсвязный список. Если же ожидается, что доступ к элементам списка будет осуществляться, в основном, в случайном порядке, выберите класс TList, несмотря на то, что он требует несколько большего времени на вставку и удаление элемента.

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

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

Листинг 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;

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

Листинг 3.17. Методы класса TtdDoubleLinkList, основанные на использовании индекса

function TtdDoubleLinkList.Add(aItem : pointer): longint;

begin

{перейти к концу связного списка}

FCursor := FTail.FCursorIx := Count;

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

Result Count;

{вставить элемент в позицию курсора}

InsertAtCursor(aItem);

end;

procedure TtdDoubleLinkList.Delete(aIndex : longint);

begin

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

dllPositionAtNth(aIndex);

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

DeleteAtCursor;

end;

function TtdDoubleLinkList.dllGetItem(aIndex : longint): pointer;

begin

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

dllPositionAtNth(aIndex);

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

Result := FCursor^.dlnData;

end;

procedure TtdDoubleLinkList.dllSetItem(aIndex : longint;

aItem : pointer);

begin

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

dllPositionAtNth(aIndex);

{если возможно удалить заменяемые данные, удалить их}

if Assigned(FDispose) and (aItem <> FCursor^.dlnData) then

FDispose(FCursor^.dlnData);

{заменить данные}

FCursor^.dlnData := aItem;

end;

function TtdDoubleLinkList.First : pointer;

begin

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

dllPositionAtNth(0);

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

Result := FCursor^.dlnData;

end;

function TtdDoubleLinkList.IndexOf(aItem : pointer): longint;

var

WorkCursor : PdlNode;

WorkCursorIx : longint;

begin

{установить рабочий курсор на первый узел (если он существует)}

WorkCursor := FHead^.dlnNext;

WorkCursorIx := 0;

{идти по списку в поисках требуемого элемента}

while (WorkCursor <> FTail) do

begin

if (WorkCursor^.dlnData = aItem) then begin

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

Result := WorkCursorIx;

FCursor := WorkCursor;

FCursorIx := WorkCursorIx;

Exit;

end;

{перейти к следующему узлу}

WorkCursor := WorkCursor^.dlnNext;

inc(WorkCursorIx);

end;

{требуемый элемент не найден}

Result := -1;

end;

procedure TtdDoubleLinkList.Insert(aIndex : longint;

aItem : pointer);

begin

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

dllPositionAtNth(aIndex);

{вставить элемент в позицию курсора}

InsertAtCursor(aItem);

end.-function TtdDoubleLinkList.Last : pointer;

begin

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

dllPositionAtNth(pred(Count));

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

Result := FCursor^.dlnData;

end;

procedure TtdDoubleLinkList.Remove(aItem : pointer);

begin

if (IndexOf (aItem) <> -1) then

DeleteAtCursor;

end;

Полный код класса TtdDoubleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.

Оглавление книги