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

Удаление из списка с пропусками

Удаление из списка с пропусками

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

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;

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