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

Полная реализация класса связного списка

Полная реализация класса связного списка

Теперь, когда мы рассмотрели три сложных операции класса списка с пропусками, можно привести интерфейс самого класса. В отличие от класса связного списка, класс списка с пропусками не имеет функциональных возможностей, характерных для массивов. Дело не в том, что нельзя, например, организовать доступ к элементу списка по его индексу, а в том, что это первая структура данных в этой книге (в эту группу также можно включить хэш-таблицу и бинарное дерево), для которой такая операция просто не имеет смысла. Указание верного индекса для списка с пропусками требует прохода по самому нижнему уровню указателей. В этом случае нет необходимости организовывать столь сложную структуру узлов и указателей для обеспечения переходов различной длины. Поэтому для списков с пропусками обеспечиваются только функциональные возможности, характерные для баз данных: переход к следующему узлу и переход к предыдущему узлу. Очевидно, что для реализации таких методов необходимо ввести внутренний курсор. Методы MoveNext и MovePrior будут перемещать курсор, а метод Examine - возвращать элемент узла, в котором находится курсор. Метод Delete будет применяться для удаления элемента в позиции курсора и т.д.

Листинг 6.18. Интерфейс класса списка с пропусками

type

TtdSkipList = class private

FCompare : TtdCompareFunc;

FCount : integer;

FCursor : PskNode;

FDispose : TtdDisposeProc;

FHead : PskNode;

FMaxLevel : integer;

FName : TtdNameString;

FPRNG : TtdMinStandardPRNG;

FTail : PskNode;

protected

class function slAllocNode(aLevel : integer): PskNode;

procedure slError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure slFreeNode(aNode : PskNode);

class procedure slGetNodeManagers;

function slSearchPrim(aItem : pointer;

var aBeforeNodes : TskNodeArray): boolean;

public

constructor Create( aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Add(aItem : pointer);

procedure Clear;

procedure Deleter-function Examine : pointer;

function IsAfterLast : boolean;

function IsBeforeFirst : boolean;

function IsEmpty : boolean;

procedure MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

function Search(aItem : pointer): boolean;

property Count : integer read FCount;

property MaxLevel : integer read FMaxLevel;

property Name : TtdNameString read FName write FName;

end;

Назначение большинства методов и свойств станет понятным, если вы вернетесь к описанию методов класса связных списков, которое приводится в главе 3.

Как и для классов связных списков, используется диспетчер узлов, который позволяет эффективно выделять и освобождать узлы. Тем не менее, для списков с пропусками имеется небольшое, однако важное отличие: узлы в списке с пропусками имеют разные размеры. Фактически в списке может быть до 12 видов узлов. Следовательно, для работы с узлами потребуется 12 диспетчеров. Процедура класса slGetNodeManagers выполняет инициализацию 12 диспетчеров узлов. Она вызывается в конструкторе Create класса списка с пропусками. Все объекты списков будут пользоваться одними и теми же диспетчерами. В заключительной части модуля все диспетчеры узлов удаляются.

Листинг 6.19. Конструктор и деструктор класса списка с пропусками

constructor TtdSkipList.Create(aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

var

i : integer;

begin

inherited Create;

{функция сравнения не может быть nil}

if not Assigned(aCompare) then

slError(tdeSkpLstNoCompare, 'Create');

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

slGetNodeManagers;

{выделить начальный узел}

FHead := slAllocNode (pred( tdcMaxSkipLevels));

FHead^.sknData := nil;

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

FTail := slAllocNode (0);

FTail^.sknData := nil;

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

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FHead^.sknPrev := nil;

FTail^.sknNext[0] :=nil;

FTail^.sknPrev := FHead;

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

FCursor := FHead;

{сохранить функцию сравнения и процедуру dispose}

FCompare := aCompare;

FDispose :=aDispose;

{создать генератор случайных чисел}

FPRNG := TtdMinStandardPRNG.Create(0);

end;

destructor TtdSkipList.Destroy;

begin

Clear;

slFreeNode(FHead);

slFreeNode(FTail);

FPRNG.Free;

inherited Destroy;

end;

Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.

Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.

Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.

Листинг 6.20. Очистка содержимого списка с пропусками

procedure TtdSkipList.Clear;

var

i : integer;

Walker, Temp : PskNode;

begin

{пройти по узлам уровня 0, освобождая все узлы}

Walker := FHead^.sknNext[0];

while (Walker <> FTail) do

begin

Temp Walker;

Walker := Walker^.sknNext[0];

slFreeNode(Temp);

end;

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

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FTail^.sknPrev := FHead;

FCount := 0;

end;

Методы выделения и уничтожения узлов достаточно просты. Они пользуются диспетчерами узлов класса и определяют требуемый диспетчер на основе значения уровня. Для метода выделения узла уровень передается в качестве входного параметра, для метода уничтожения оно определяется исходя из значения, полученного из освобождаемого узла.

Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками

class function TtdSkipList.slAllocNode(aLevel : integer): PskNode;

begin

Result := SLNodeManager[aLevel].AllocNode;

Result^.sknLevel := aLevel;

end;

procedure TtdSkipList.siFreeNode(aNode : PskNode);

begin

if (aNode <> nil) then begin

if Assigned(FDispose) then

FDispose(aNode^.sknData);

SLNodeManager[aNode^.sknLevel].FreeNode(aNode);

end;

end;

class procedure TtdSkipList.slGetNodeManagers;

var

i : integer;

begin

{если диспетчеры узлов еще не созданы, создать их}

if (SLNodeManager[0] =nil) then

for i := 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] := TtdNodeManager.Create(NodeSize[i]);

end;

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

Остальные методы класса списка с пропусками еще проще - все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Delete

begin

{начальный и конечный узлы удалять нельзя}

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

slError(tdeListCannotDelete, 'Delete');

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

Remove(FCursor^.sknData);

end;

function TtdSkipList.Examine : pointer;

begin

Result := FCursor^.sknData;

end;

function TtdSkipList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdSkipList.IsBeforeFirst : boolean;

begin

Result := FCursor = FHead;

end;

function TtdSkipList.IsEmpty : boolean;

begin

Result := Count = 0;

end;

procedure TtdSkipList.MoveAf terLast;

begin

FCursor := FTail;

end;

procedure TtdSkipList.MoveBeforeFirst;

begin

FCursor := FHead;

end;

procedure TtdSkipList.MoveNext;

begin

if (FCursor <> FTail) then

FCursor := FCursor^.sknNext[0];

end;

procedure TtdSkipList.Move Prior;

begin

if (FCursor <> FHead) then

FCursor := FCursor^.sknPrev;

end;

С использованием набора диспетчеров узлов для списка с пропусками связана одна проблема, о которой мы еще не говорили. Она не так очевидна для связных списков. А заключается она в пробуксовке. Проблема пробуксовки становится все более заметной при увеличении количества узлов до миллионов. Дело в том, что в списке с пропусками соседние узлы, скорее всего, будут находиться в разных страницах памяти. Поэтому при последовательном прохождении по списку от начала до конца на пути будут попадаться узлы разного размера, находящиеся в разных страницах памяти. Это приводит к подкачке страниц. К сожалению, мы никак не можем устранить свопинг (при использовании списков с несколькими миллионами узлов данные узлов в любом случае могут находиться в разных страницах). Проблему можно немного смягчить за счет использования стандартного диспетчера кучи Delphi. Тем не менее, даже в этом случае не исключается возможность возникновения пробуксовки.

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