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

Шаг 2 также заслуживает отдельного рассмотрения. Фактически, в нем утверждается, что в списке с пропусками не могут храниться повторяющиеся элементы или, если выражаться более строго, элементы, в результате сравнения которых получается равенство. Почему? Представьте себе, что имеется список с пропусками, содержащий 42 узла, все значения которых равны а. В таком случае, что будет означать фраза: "Поиск узла а"? Учитывая саму природу списка с пропусками, на первом шаге поиска при переходе, скажем, на узел 35 будет найдено искомое значение а. Очевидно, что оно не будет ни первым в списке, ни последним - просто одним из 42 имеющихся в списке. Нужно ли в алгоритм вводить прохождение списка в обратном направлении, пока не будет найден первый узел со значением al Кто-то может сказать, что узлы с равными значениями должны находиться в списке в том порядке, в котором они вставлялись. Это означает, что при вставке элемента он будет добавляться в конец последовательности узлов с равными значениями, а при поиске нужно будет находить первый из повторяющихся узлов. Для алгоритма вставки при понижении уровней нужно сохранять список "предыдущих узлов". Эту операцию выполнить сложнее. По мнению автора книги, излишняя сложность алгоритмов для обеспечения возможности хранения в списке с пропусками узлов с одинаковыми значениями себя совершенно не оправдывает. Будем считать, что если существует вероятность повторения узлов, то мы знаем, как их различать между собой. В противном случае, они будут трактоваться как действительно один и тот же узел. Если мы можем различать повторяющиеся узлы, то можно предположить, что такая же возможность заложена и в функции сравнения. Следовательно, узлы уже не будут считаться повторениями.

В листинге 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