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