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

var

i, Level : integer;

NewNode : PskNode;

BeforeNodes : TskNodeArray;

begin

{выполнить поиск узла и заполнить значениями массив BeforeNodes}

if slSearchPrim(aItem, BeforeNodes) then

slError(tdeSkpLstDupItem, 'Add');

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

Level := 0;

while (Level <= MaxLevel) and (FPRNG.AsDouble < 0.25) do inc(Level);

{если мы вышли за границы максимального уровня, сохранить новое значение в качестве максимального уровня}

if (Level > MaxLevel) then

inc(FMaxLevel);

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

NewNode := slAllocNode(Level);

NewNode^.sknData := aItem;

{восстановить указатели для уровня 0 - двухсвязный список}

NewNode^.sknPrev := BeforeNodes[0];

NewNode^.sknNext[0] := BeforeNodes[0]^.sknNext[0];

BeforeNodes[0]^.sknNext[0] := NewNode;

NewNode^.sknNext[0]^.sknPrev := NewNode;

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

for i := 1 to Level do

begin

NewNode^.sknNext[i] := BeforeNodes[i]^.sknNext[i];

BeforeNodes[i]^.sknNext[i] := NewNode;

end;

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

inc(FCount);

end;

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

Алгоритм удаления узла из списка с пропусками достаточно прост, несмотря на его длину. Он выглядит следующим образом:

1. Найти удаляемый узел с помощью обычного алгоритма поиска.

2. Предположим, что узел находится на уровне i. Сохранить узел, расположенный перед удаляемым и находящийся на том же уровне, что и i-тый элемент в массиве. Установить значение переменной LevelNumber равным i, а предыдущий узел записать в переменную BeforeNode.

3. Уменьшить значение переменной LevelNumber на единицу.

4. Если переменная LevelNumber содержит отрицательное значение, перейти к шагу 7.

5. Начиная с узла BeforeNode, переходить по указателям уровня LevelNumber вплоть до достижения удаляемого узла. При переходе по указателям уровня LevelNumber отслеживать родительские узлы всех проходимых узлов, что позволит идентифицировать узел, предшествующий удаляемому на уровне LevelNumber.

6. Записать узел, предшествующий удаляемому, в массив в элемент LevelNumber. Установить переменную BeforeNode равной этому узлу. Перейти к шагу 3.

7. Если мы достигли этого шага, у нас имеется массив предшествующих узлов для удаляемого узла для уровней от i до 0. Выполнить стандартную операцию "удалить после" для связного списка на каждом уровне.

Шаг 5 гарантированно будет работать (т.е. мы всегда найдем удаляемый узел), поскольку узел уровня n содержит указатели на всех уровнях до уровня n включительно.

В листинге 6.17 приведен код метода Remove для класса списка с пропусками. Он основан на описанном выше алгоритме.

Листинг 6.17. Удаление в списке с пропусками

procedure TtdSkipList.Remove(aItem : pointer);

var

i, Level : integer;

Temp : PskNode;

BeforeNodes : TskNodeArray;

begin

{выполнить поиск узла и заполнить значениями массив BeforeNodes}

if not slSearchPrim(aItem, BeforeNodes) then

slError(tdeSkpLstItemMissing, 'Remove');

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

Level := FCursor^.sknLevel;

if (Level > 0) then begin

for i := pred(Level) downto 0 do

begin

BeforeNodes[i] := BeforeNodes[i+1];

while (BeforeNodes[i]^.sknNext[i] <> FCursor) do

BeforeNodes[i] := BeforeNodes[i]^.sknNext[i];

end;

end;

{восстановить указатели для уровня 0 - двухсвязный список}

BeforeNodes[0]^.sknNext[0] := FCursor^.sknNext[0];

FCursor^.sknNext[0]^.sknPrev := BeforeNodes[0];

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

for i := 1 to Level do

BeforeNodes[i]^.sknNext[i] := FCursor^.sknNext[i];

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

Temp := FCursor;

FCursor := FCursor^.sknNext[0];

slFreeNode(Temp);

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

dec(FCount);

end;

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