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;