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

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

procedure TtdSingleLinkList.Clear;

var

Temp : PslNode;

begin

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

Temp := FHead^.slnNext;

while (Temp <> nil) do

begin

FHead^.slnNext := Temp^.slnNext;

if Assigned(FDispose) then

FDispose(Temp^.slnData);

SLNodeManager.FreeNode(Temp);

Temp := FHead^.slnNext;

end;

FCount := 0;

MoveBeforeFirst;

end;

procedure TtdSingleLinkList.DeleteAtCursor;

begin

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

sllError(tdeListCannotDelete, 'Delete');

{удалить все элементы}

if Assigned(FDispose) then

FDispose(FCursor^.slnData);

{удалить ссылки на узел и удалить сам узел}

FParent^.slnNext := FCursor^.slnNext;

SLNodeManager.FreeNode(FCursor);

FCursor := FParent^.slnNext;

dec(FCount);

end;

function TtdSingleLinkList.Examine : pointer;

begin

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

sllError(tdeListCannotExamine, 'Examine');

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

Result := FCursor^.slnData;

end;

procedure TtdSingleLinkList.InsertAtCursor(aItem : pointer);

var

NewNode : PslNode;

begin

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

if (FCursor = FHead) then

MoveNext;

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

NewNode := PslNode (SLNodeManager.AllocNode);

NewNode^.slnData := aItem;

NewNode^.slnNext := FCursor;

FParent^.slnNext := NewNode;

FCursor := NewNode;

inc(FCount);

end;

function TtdSingleLinkList.IsAfterLast : boolean;

begin

Result := FCursor;

nil;

end;

function TtdSingleLinkList.IsBeforeFirst : boolean;

begin

Result := FCursor = FHead;

end;

function TtdSingleLinkList.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

procedure TtdSingleLinkList.MoveBeforeFirst;

begin

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

FCursor := FHead;

FParent := nil;

FCursorIx := -1;

end;

procedure TtdSingleLinkList.MoveNext;

begin

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

if (FCursor <> nil) then begin

FParent := FCursor;

FCursor := FCursor^.slnNext;

inc(FCursorIx);

end;

end;

Вы, возможно, обратили внимание, что некоторые из приведенных методов пользуются полем объекта FCursorIx. Именно это поле позволяет обеспечить высокую эффективность методов, основанных на использовании индекса, поскольку в нем хранится индекс курсора (при этом первый узел имеет индекс 0, точно так же как в TList). Значение поля используется методом ellPositionAtNth, который оптимальным образом перемещает курсор в позицию с указанным индексом.

Листинг 3.10. Метод sllPositionAtNth

procedure TtdSingleLinkList.sllPositionAtNth(aIndex : longint);

var

WorkCursor : PslNode;

WorkParent : PslNode;

WorkCursorIx : longint;

begin

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

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

sllError(tdeListInvalidIndex, 'sllPositionAtNth');

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

if (aIndex = FCursorIx) then

Exit;

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

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

if (aIndex < FCursorIx) then begin

WorkCursor := FHead;

WorkParent :=nil;

WorkCursorIx := -1;

end

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

else begin

WorkCursor :=FCursor;

WorkParent := FParent;

WorkCursorIx := FCursorIx;

end;

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

while (WorkCursorIx < aIndex) do

begin

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

inc(WorkCursorIx);

end;

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

FCursor := WorkCursor;

FParent := WorkParent;

FCursorIx := WorkCursorIx;

end;

Метод sllPositionAtNth для увеличения быстродействия использует локальные переменные. Вначале метод определяет, больше ли заданный индекс индекса курсора (в этом случае поиск узла начинается с позиции курсора) или же он меньше (поиск узла начинается с начала списка). Без знания позиции курсора мы всегда бы начинали поиск с начала списка.

Реализация остальных методов, основанных на использовании индекса, после написания кода метода sllPositionAtNth не представляет особых трудностей.

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

procedure TtdSingleLinkList.Delete(aIndex : longint);

begin

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

sllPositionAtNth(aIndex);

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

DeleteAtCursor;

end;

function TtdSingleLinkList.First : pointer;

begin

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

SllPositionAtNth(0);

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

Result := FCursor^.slnData;

end;

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

begin

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

sllPositionAtNth(aIndex);

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

InsertAtCursor(aItem);

end;

function TtdSingleLinkList.Last : pointer;

begin

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

sllPositionAtNth(pred(Count));

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

Result := FCursor^.slnData;