Таким образом, при поиске было пройдено шесть ссылок и выполнено шесть сравнений. Звучит не очень впечатляюще, особенно если учитывать, что в простом двухсвязном списке нам пришлось бы перейти по семи указателям и выполнить семь сравнений. Тем не менее, на рис. 6.3 принято допущение, что указатель уровня n+1 переходит на расстояние, в два раза превышающее расстояние перехода для указателя уровня n. Но обязательно ли соблюдать это условие? Почему в два раза, а не в три или пять? В списке с пропусками, который будет создан в этой главе, указатели первого уровня будут переходить через четыре узла, указатели второго уровня - через 16 узлов (т.е. 4 * 4), указатели третьего уровня - через 64 узла (т.е. 4(^3^)) и указатели уровня n - через 4(^n^) узлов.

Подобный выбор расстояний переходов объясняется необходимостью балансировки степени возникновения переходов на большие расстояния на высоких уровнях и скорости поиска на уровне 0 при подходе к искомому узлу. Множитель 4 является хорошим компромиссом.

Насколько большими в таком случае будут узлы? Если предположить, что элемент, хранящийся в списке с пропусками, представляет собой указатель (как это было в главе 3), тогда размер узлов на уровне 0 будет равен, по крайней мере, размеру трех указателей (один указатель на данные, один - прямой указатель и один - обратный). Размер узлов на уровне 1 будет составлять четыре указателя

(поскольку в узле будет находиться два прямых указателя). Для уровня 2 размер узлов будет составлять пять указателей и т.д. Таким образом, на уровне n размер узлов будет равен не менее n + 3 указателям. (Если предположить, что размер указателя равен 4 байта, то мы получим узлы 12, 16, 20 и 4n + 12 байт для узлов уровней 0, 1, 2 и n соответственно.) В действительности, для организации списка с пропусками требуется увеличить полученные размеры узлов, по крайней мере, на 1 байт, поскольку в каждом узле необходимо хранить уровень, к которому принадлежит данный узел.

Как вы уже знаете, узел уровня n содержит указатель на узел, находящийся впереди него на 4" узлов. Если n равно 16, то указатель уровня n позволяет перейти вперед примерно на 4 миллиарда узлов - абсолютно недостижимое количество. Так, например, в 32-разрядной операционной системе каждый процесс имеет доступ к 4 миллиардам байт, в которых никак не могут разместиться 4 миллиарда узлов разного размера. На практике количество узлов, как правило, не будет превышать одного миллиона, поэтому указателей уровня 11 окажется вполне достаточно (т.е. общее количество уровней составит 12). На высшем уровне переход будет осуществляться на 4 миллиона узлов вперед.

На основе всего вышесказанного можно легко разработать структуру узла списка с пропусками. Это будет структура переменой длины, что несколько усложняет выделение памяти под узлы и ее освобождение. Структура узла приведена в листинге 6.14.

Листинг 6.14. Структура узла списка с пропусками

const

tdcMaxSkipLevels = 12;

type

PskNode = ^TskNode;

TskNodeArray = array [0..pred(tdcMaxSkipLevels) ] of PskNode;

TskNode = packed record

sknData : pointer;

sknLevel : longint;

sknPrev : PskNode;

sknNext : TskNodeArray;

end;

Мы не собираемся объявлять переменные типа TskNode. Фактически мы будем иметь дело исключительно с переменными типа PskNode, память под которые выделяется из кучи. Размер переменной будет вычисляться как

(3+sknLevel)*sizeof(pointer) + sizeof(longint)

Определившись со структурой узла списка с пропусками, можно перейти к рассмотрению реализации алгоритма поиска, которая приведена в листинге 6.15. Поиск представляет собой внутренний метод класса TtdSklpList. Он будет использоваться методами Add и Remove класса. И как мы сейчас увидим, еще одна его задач заключается в создании списка "предыдущих узлов" для каждого уровня.

Листинг 6.15. Поиск в списке с пропусками

function TtdSkipList.slSearchPrim(aItem : pointer;

var aBeforeNodes : TskNodeArray): boolean;

var

Level : integer;

Walker : PskNode;

Temp : PskNode;

CompareResult : integer;

begin

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

for Level := 0 to pred(tdcMaxSkipLevels) do

aBeforeNodes[Level] := FHead;

{инициализировать}

Walker := FHead;

Level := MaxLevel;

{начать поиск искомого узла}

while (Level >= 0) do

begin

{найти следующий узел на этом уровне}

Temp := Walker^.sknNext [Level];

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

if (Temp = FTail) then

CompareResult := 1 {в противном случае сравнить данные следующего узла с искомыми данными}

else

CompareResult := FCompare(Temp^.sknData, aItem);

{если данные узла равны искомым данным, поиск завершен; выйти из функции}