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

Бакнелл Джулиан М.

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

Листинг 6.16. Вставка в список с пропусками

procedure TtdSkipList.Add(aItem : pointer);

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 будет применяться для удаления элемента в позиции курсора и т.д.