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

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;

end;

function TtdSingleLinkList.sllGetItem(aIndex : longint): pointer;

begin

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

sllPositionAtNth(aIndex);

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

Result := FCursor^.slnData;

end;

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

begin

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

sllPositionAtNth(aIndex);

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

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

FDispose(FCursor^.slnData);

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

FCursor^.slnData := aItem;

end;

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

Листинг 3.12. Методы Add, IndexOf и Remove

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

var

WorkCursor : PslNode;

WorkParent : PslNode;

begin

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

WorkCursor :=FCursor;

WorkParent :=FParent;

{перешли в конец связного списка}

while (WorkCursor <> nil) do

begin

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

end;

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

FParent := WorkParent;

FCursor := nil;

FCursorIx := Count;

Result := Count;

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

InsertAtCursor(aItem);

end;

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

var

WorkCursor : PslNode;

WorkParent : PslNode;

WorkCursorIx : longint;

begin

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

WorkParent := FHead;

WorkCursor := WorkParent^.slnNext;

WorkCursorIx := 0;

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

while (WorkCursor <> nil) do

begin

if (WorkCursor^.slnData = aItem) then begin

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

Result := WorkCursorIx;

FCursor := WorkCursor;

FParent := WorkParent;

FCursorIx := WorkCursorIx;

Exit;

end;

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

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

inc(WorkCursorIx);

end;

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

Result := -1;

end;

procedure TtdSingleLinkList.Remove(aItem : pointer);

begin

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

DeleteAtCursor;

end;

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

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

Двухсвязные списки

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

type

PSimpleNode = ^TSimpleNode;

TSimpleNode = record

Next : PSimpleNode;

Prior : PSimpleNode;

Data : SomeDataType;

end;

Таким образом, двухсвязный список позволяет двигаться по узлам не только вперед, по ссылкам Next, но и назад, по ссылкам Prior. Схематично двухсвязный список показан на рис. 3.4.

Рисунок 3.4. Двухсвязный список

Вставка и удаление элементов в двухсвязном списке

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

Ссылка Next нового узла устанавливается на узел, расположенный после заданного узла, а ссылка Next заданного узла устанавливается на новый узел. Для установки обратных ссылок ссылка Prior нового узла устанавливается на заданный узел, а ссылка Prior узла, следующего за новым, устанавливается на новый узел. В коде это выглядит следующим образом:

var

GivenNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data ..

NewNode^.Next := GivenNode^.Next;

GivenNode^.Next := NewNode;

NewNode^.Prior := GivenNode;

NewNode^.Next^.Prior := NewNode;

В случае с удалением проще всего удалить узел, находящийся после заданного узла. Необходимо установить ссылку Next заданного узла на узел, находящийся после удаляемого, а ссылку Prior узла, находящегося после удаляемого, на заданный узел.

Рисунок 3.5. Вставка нового узла в двухсвязный список

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

var

GivenNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := GivenNode^.Next;

GivenNode^.Next := NodeToGo^.Next;

NodeToGo^.Next^.Prior := GivenNode;

Dispose(NodeToGo);

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