Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Как вы уже знаете, узел уровня n содержит указатель на узел, находящийся впереди него на 4" узлов. Если n равно 16, то указатель уровня n позволяет перейти вперед примерно на 4 миллиарда узлов - абсолютно недостижимое количество. Так, например, в 32-разрядной операционной системе каждый процесс имеет доступ к 4 миллиардам байт, в которых никак не могут разместиться 4 миллиарда узлов разного размера. На практике количество узлов, как правило, не будет превышать одного миллиона, поэтому указателей уровня 11 окажется вполне достаточно (т.е. общее количество уровней составит 12). На высшем уровне переход будет осуществляться на 4 миллиона узлов вперед.
На основе всего
Листинг 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);
{если данные узла равны искомым данным, поиск завершен; выйти из функции}
if (CompareResult = 0) then begin
aBeforeNodes[Level] := Walker;
FCursor :=Temp;
Result := truer-Exit;
end;
{если данные следующего узла меньше, чем искомые данные, перейти в следующий узел}
if (CompareResult < 0) then begin
Walker := Temp;
end
{если данные следующего узла больше, чем искомые данные, понизить уровень}
else begin
aBeforeNodes[Level] := Walker;
dec(Level);
end;
end;
{если мы достигли этой точки, значит, искомый узел не найден}
Result := false;
end;
Реализация метода начинается с заполнения всего массива aBeforeNode начальным узлом. Затем поиск начинается с высшего уровня списка (MaxLevel). Переход по указателям высшего уровня продолжается до тех пор, пока не будет найден
узел, данные которого больше искомых. Обратите внимание, что обрабатывается специальный случай для концевого узла. Предполагается, что данные конечного узла больше любых других данных в списке. К сожалению, для класса, предназначенного для любых типов данных, подобная проверка обязательна, поскольку значение конечного узла установить заранее невозможно. Если же, с другой стороны, разрабатывается список с пропусками специально для строк, значение конечного узла можно выбрать таким, чтобы оно было больше любой строки, которая будет храниться в списке.После этого производится сравнение. Если данные равны, искомый узел найден, и после установки нескольких переменных выполнение метода завершается. Если данные узла меньше, чем искомые данные, осуществляется переход по прямому указателю. В противном случае текущий уровень записывается в массив aBeforeNode и значение уровня уменьшается на единицу.
Вставка в список с пропусками
После изучения алгоритма поиска узла в существующем списке с пропусками, давайте рассмотрим алгоритм построения списка с помощью операции вставки нового узла. Вернувшись к рисунку 6.3, можно сказать, что задача сохранения однородной структуры списка после серии выполнения вставок и удалений кажется практически невыполнимой.
Достоинство алгоритма вставки, разработанного Пью, заключается в том, что Пью понимал, что построение абсолютно однородной структуры списка, по сути дела, невозможно или, по крайней мере, является сложной и трудоемкой операцией. Поэтому он предложил список с пропусками, который в среднем приближается к однородной структуре. В однородном списке с пропусками с множителем 4 один из четырех узлов больше трех других, поскольку он содержит дополнительный прямой указатель. В свою очередь, один из четырех этих больших узлов содержит еще один дополнительный указатель и т.д. В конце концов, можно прийти к выводу, что в однородном списке с пропусками три четверти всех узлов находятся на уровне 0, три шестнадцатых - на уровне 1, три шестьдесят четвертых - на уровне 2 и т.д. Другими словами, при случайном выборе узла можно установить следующие вероятности выбора узлов по уровням:
0.75 для уровня 0,
0.1875 для уровня 1,
0.046875 для уровня 2 и т.д.
Алгоритм вставки в список с пропусками учитывает эти вероятности таким образом, чтобы в общем на каждом уровне находилось требуемое количество узлов. Это означает, что в среднем вероятностный список с пропусками будет работать с той же эффективностью, что и "однородный": поиск некоторых узлов будет осуществляться чуть дольше, а других - чуть быстрее, однако, в среднем, поиск в реальном списке с пропусками будет занимать примерно столько же времени, сколько и в идеальном однородном списке.
После такой теоретической подготовки можно перейти к описанию самого алгоритма вставки. Начинаем с пустого списка. Пустой список с пропусками содержит начальный узел уровня 11 и конечный узел уровня 0. Все прямые указатели начального узла указывают на конечный узел. Обратный указатель конечного узла указывает на начальный узел. Алгоритм вставки работает следующим образом:
1. Выполнить в списке поиск вставляемого элемента с одним дополнительным условием. При каждом понижении уровня сохранять значение переменной BeforeNode. В конце концов, мы получим набор значений BeforeNode, по одному для каждого уровня (поскольку количество уровней ограничено числом 12, для хранения уровней можно организовать простой массив из 12 элементов).