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

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

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

Перед тем как приступить к реализации класса TtdSingleLinkList для представления односвязного списка, рассмотрим несколько вводных замечаний.

Начнем с самого начала. Как уже упоминалось, было бы очень удобно использовать связный список, не беспокоясь о его узлах. Хотелось бы, чтобы класс связного списка мог работать с любыми типами указателей, подобно классу TList. Для получения доступа к элементам связного списка было бы желательно использовать индекс (несмотря на то что это может негативно сказаться на быстродействии), но еще лучше было бы использовать терминологию баз данных. Так, в связном списке можно использовать курсор, который указывает на "текущий" элемент списка. Тогда можно было бы написать методы для позиционирования курсора перед любым элементом списка, перемещения курсора на следующий элемент, вставки и удаления элемента в позиции курсора и т.д. Поскольку мы создаем связный список в виде класса, мы можем работать с родительским объектом текущего элемента, что позволит запрограммировать метод Insert так, как он реализован в TList (т.е. за счет перемещения текущего элемента и всех последующих элементов на одну позицию и вставки в освободившееся место нового элемента). Аналогично можно реализовать и метод Delete.

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

Листинг 3.7. Класс TtdSingleLinkList

TtdSingleLinkList = class private

FCount : longint;

FCursor : PslNode;

FCursorIx: longint;

FDispose : TtdDisposeProc;

FHead : PslNode;

FNanie : TtdNameString;

FParent : PslNode;

protected

function sllGetItem(aIndex : longint): pointer;

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

procedure sllError(aErrorCode : integer;

const aMethodName : TtdNameString);

class procedure sllGetNodeManager;

procedure sllPositionAtNth(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 MoveBeforeFirst;

procedure MoveNext;

procedure Remove(aItem : pointer);

procedure Sort(aCompare : TtdCompareFunc);

property Count : longint read FCount;

property Items[aIndex : longint] : pointer read sllGetItem write sllSetItem; default;

property Name : TtdNameString read FName write FName;

end;

Несмотря на то что названия методов соответствуют стандарту TList, появилось несколько новых методов. Метод MoveBeforeFirst помещает курсор перед всеми элементами связного списка. IsBeforeFirst и IsAfterLast возвращают True, если курсор находится, соответственно, перед всеми элементами или после всех элементов списка. Метод MoveNext перемещает курсор на следующий элемент списка. Свойство Items аналогично соответствующему свойству списка TList: элементы нумеруются от 0 до Count-1.

Конструктор Create проверяет, создан ли экземпляр диспетчера узлов, а затем распределяет память для узла, который будет фиктивным начальным узлом. Затем курсор помещается перед всеми узлами (поскольку в списке еще нет узлов, это совсем несложно). Деструктор Destroy очищает связный список и освобождает фиктивный начальный узел, выделенный конструктором Create.

Листинг 3.8. Конструктор и деструктор класса TtdSingleLinkList

constructor TtdSingleLinkList.Create(aDispose : TtdDisposeProc);

begin

inherited Create;

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

FDispose :=aDispose;

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

s 11 GetNodeManager;

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

FHead := PslNode (SLNodeManager.AllocNode);

FHead^.slnNext := nil;

FHead^.slnData := nil;

{установить курсор}

MoveBeforeFirst;

end;

destructor TtdSingleLinkList.Destroy;

begin

{удалить все узлы, включая начальный фиктивный узел}

Clear;

SLNodeManager.FreeNode(FHead);

inherited Destroy;

end;

Особый интерес здесь представляет тот факт, что связный список организован таким образом, что для всех экземпляров класса TtdSingleLinkList создается только один диспетчер узлов. Все экземпляры пользуются одним и тем же диспетчером. Можно было бы запрограммировать, чтобы каждый класс создавал свой диспетчер, но это бы означало использование большого дополнительного объема для экземпляра класса. Таким образом, учитывая то, что в приложении, в котором имеется один связный список, как правило, есть несколько списков, было решено ввести переменную класса. Но во всех этих рассуждениях присутствует один недостаток: Delphi не поддерживает переменные класса. Поэтому в коде мы имитируем такую переменную, объявив ее как глобальную в разделе implementation модуля. Если вы просмотрите содержимое файла TDLnkLst.pas, то найдете следующее объявление:

var

SLNodeManager : TtdNodeManager;

Все методы класса односвязного списка можно разбить на две категории: методы, действующие по последовательной схеме (MoveBeforeFirst, InsertAtCursor и т.д.), и методы, которые работают со списком как с массивом (свойство Items, методы Delete, IndexOf и т.д.). Рассмотрим сначала методы первой группы, поскольку мы уже говорили о принципе их работы в начале главы при описании связных списков. Для упрощения реализации мы не только храним курсор (т.е. указатель на текущий узел) в объекте, но и родительский объект курсора (т.е. указатель на родительский объект текущего курсора). Такая схема позволяет упростить методы вставки и удаления элементов.

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

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, данные, на которые указывают ссылки каждого узла, будут находиться в разных участках памяти. Но здесь, к сожалению, мы ничего поделать не можем.

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