Фундаментальные алгоритмы и структуры данных в Delphi, Бакнелл Джулиан М.

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

на обложку

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

Шрифт:

2. Установить переменную BeforeNode на начальный фиктивный узел.

3. Перейти по прямому указателю уровня LevelNumber от узла BeforeNode. Назвать узел, в который мы попали, NextNode.

4. Сравнить элемент в узле NextNode с искомым. Если NextNode является искомым узлом, поиск завершается.

5. Если элемент в узле NextNode меньше искомого, то искомый узел должен находиться после узла NextNode. Установить переменную BeforeNode на узел NextNode и перейти к шагу 3.

6. Если элемент в узле NextNode больше искомого, то искомый узел, если он присутствует в списке, должен находиться между узлами BeforeNode

и NextNode. Уменьшаем значение переменной LevelNumber на единицу (другими словами, уменьшаем количество пропускаемых за один шаг узлов).

7. Если значение переменной LevelNumber равно 0 или больше, перейти к шагу 3. В противном случае искомый элемент в списке не найден, и если его необходимо вставить, то его позиция должна находиться между узлами BeforeNode и NextNode.

В соответствии с этим алгоритмом, при поиске узла g на рис. 6.3 мы начинаем с уровня 3 и начального узла. Переходим по указателю уровня 3 до узла h. Сравниваем h и g. Поскольку h больше g, уменьшаем уровень на единицу и начинаем сначала. По указателю второго уровня от начального узла переходим к узлу d. d меньше, чем g, следовательно, узел d становится новым начальным узлом. Снова переходим по указателю уровня 2 до узла h. Поскольку h больше, чем g, уменьшаем уровень на единицу. Переходим от узла d по указателю уровня 1 до узла f. Он меньше искомого, поэтому делаем его новым начальным узлом. Переходим по указателю уровня 1, и мы снова попадаем в узел h, который больше искомого. Снова понижаем уровень на единицу, переходим вперед по указателю уровня 0 и находим искомый узел g.

Таким образом, при поиске было пройдено шесть ссылок и выполнено шесть сравнений. Звучит не очень впечатляюще, особенно если учитывать, что в простом двухсвязном списке нам пришлось бы перейти по семи указателям и выполнить семь сравнений. Тем не менее, на рис. 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;