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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 16 (всего у книги 36 страниц)

Кроме того, следует отметить, что длина цикла тасующего генератора равна длине цикла внутреннего генератора. Суть тасующего генератора заключается в том, что генерируемые им числа выдаются в другом порядке. Длину цикла можно изменить, если для получения индексов использовать еще один генератор случайных чисел. При этом длина цикла соответственно увеличится. (Та же длина цикла получается при использовании двух внутренних генераторов в комбинированном генераторе.)

Выводы по алгоритмам генерации случайных чисел

В предыдущем разделе были рассмотрены несколько достаточно простых генераторов случайных чисел. Наилучшие последовательности чисел позволяют получить два последних генератора, но, к сожалению, они выдвигают жесткие требования к памяти (так, например, последний алгоритм для хранения внутренней таблицы требует почти 800 байт). Самым плохим из рассмотренных был минимальный стандартный генератор, по крайней мере, что касается наличия регулярности в генерируемых им последовательностях случайных чисел, которую, как было показано, можно устранить с помощью алгоритма тасования. Если говорить о личных предпочтениях, то автору книги наиболее импонирует аддитивный генератор: он прост, использует только оператор сложения и генерирует хорошие последовательности статистически независимых случайных чисел. Единственным его недостатком является то, что при необходимости сохранения состояния генератора, нужно сохранять массив и два индекса, что, по сравнению с одним значением начального числа типа longint для минимального стандартного генератора, может показаться слишком огромным объемом данных.

Другие распределения случайных чисел

Если случайные числа используются для моделирования некоторого процесса, то вы можете обнаружить, что все рассмотренные выше генераторы случайных чисел не позволяют решить поставленную задачу. Это вызвано равномерным распределением генерируемых ими случайных чисел, т.е. вероятность возникновения одного случайного числа равна вероятности возникновения любого другого числа. При проведении моделирования бывают необходимы случайные числа, распределенные не по равномерному закону. Тем не менее, для вычисления последовательностей с другими распределениями можно использовать уже изученные нами генераторы случайных чисел.

Вторым по значимости после равномерного является нормальное или гауссово распределение. Оно также известно под названием распределение колокообразной формы, поскольку все точки данных расположены симметрично относительно среднего значения, причем, чем дальше точка от среднего значения, тем меньше вероятность ее получения. Нормальное распределение играет очень важную роль в статистике, где оно используется практически повсеместно. Например, рост людей 42-летнего возраста распределен в соответствии с нормальным распределением. Если попросить измерить длину стола нескольких человек с помощью линейки, длина которой намного короче, чем длина стола (другими словами, в случае существования элемента ошибки), полученный ответ будет соответствовать закону нормального распределения. И подобных примеров можно привести очень много.

Для нормально распределенного набора случайных чисел необходимо знать среднее значение и среднеквадратическое отклонение. Если эти параметры известны, генерация последовательности случайных чисел не представит особого труда. Для генерации мы будем использовать преобразование Бокса-Мюллера. Сами математические выкладки в этой книге не приводятся. Преобразование на своем входе требует два равномерно распределенных случайных числа, а на выходе генерирует два нормально распределенных случайных числа. Это не совсем удобно, поскольку нам, как правило, нужно только одно число за один раз. Однако второе число можно записать и выдать в качестве выходного значения при следующем вызове функции. Обратите внимание, что для многопоточных приложений предложенное решение приведет к тому, что функция не будет независимой от потоков, поскольку неиспользуемое значение придется хранить в глобальной переменной. Указанного недостатка можно избежать, если инкапсулировать вычисление случайных чисел в классе.

Обратите внимание, что мы исключаем тот редкий случай, когда оба равномерно распределенных случайных числа равны 0, и сумма их квадратов также равна 0, поскольку от этого значения в дальнейшем мы берем логарифм, который для 0 дает бесконечность. Поэтому подобной ситуации следует избегать.

Листинг 6.12. Случайные числа с нормальным распределением

var

NRGNextNumber : double;

NRGNextlsSet : boolean;

function NormalRandomNumber(aPRNG : TtdBasePRNG;

aMean : double;

aStdDev : double): double;

var

Rl, R2 : double;

RadiusSqrd : double;

Factor : double;

begin

if NRGNextlsSet then begin

Result := NRGNextNumber;

NRGNextlsSet := false;

end

else begin

{получить два числа, которые определяют точку внутри окружности единичного радиуса}

repeat

Rl := (2.0 * aPRNG.AsDouble) -1.0;

R2 := (2.0 * aPRNG.AsDouble) – 1.0;

RadiusSqrd := sqr(Rl) + sqr(R2);

until (RadiusSqrd < 1.0) and (RadiusSqrd > 0.0);

{применить преобразование Бокса-Мюллера}

Factor := sqrt(-2.0 * In(RadiusSqrd) / RadiusSqrd);

Result := Rl * Factor;

NRGNextNumber :=R2 * Factor;

NRGNextlsSet :=true;

end;

Result := (Result * aStdDev) + aMean;

end;

Еще одним важным распределением является экспоненциальное. Случайные числа, распределенные по этому закону, используются для моделирования ситуаций «времени прибытия», например, времени прибытия покупателей к кассе в супермаркете. Если в среднем покупатели подходят к кассе каждые x секунд, то время прибытия будет распределено по экспоненциальному закону со средним значением х.

Генерировать случайные числа, распределенные по экспоненциальному закону, достаточно просто. Не вдаваясь в математические подробности можно сказать, что если u – случайное число, распределенное по равномерному закону в диапазоне от 0.0 до 1.0, то e, которое равно

e = -x ln(u)

будет случайном числом, распределенным по экспоненциальному закону со средним значением х.

Листинг 6.13. Случайные числа, распределенные по экспоненциальному закону

function ExponentialRandomNumber( aPRNG : TtdBasePRNG;

aMeart : double): double;

var

R : double;

begin

repeat

R := aPRNG.AsDouble;

until (R <> );

Result := -aMean * ln(R);

end;

И снова обратите внимание, что исключается редкий случай, когда значение равномерно распределенного случайного числа равно 0, поскольку от него будет браться натуральный логарифм.

Списки с пропусками

После подробного описания нескольких генераторов случайных чисел, давайте рассмотрим структуру данных, которая для обеспечения высоких вероятностных характеристик быстродействия использует случайные числа.

Код класса для списков с пропусками можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSkpLst.pas.

Помните, в главе 4 мы говорили о том, что при необходимости поиска определенного значения в связном списке нужно начать с его начала и проходить по узлам с помощью указателей Next до тех пор, пока не будет найдено искомое значение. Если список был отсортирован, можно было воспользоваться алгоритмом бинарного поиска, который позволяет минимизировать количество выполняемых сравнений, тем не менее, при этом для прохода по списку также применялись указатели Next.

Вильям Пью (William Pugh) в 1990 году в своей статье "Списки с пропусками: вероятностная альтернатива сбалансированным деревьям" ("Skip Lists: Probabilistic AItemative to Balanced Trees") [18] показал, что существует более удобная альтернатива связным спискам, если мы готовы использовать узлы большего размера с большим количеством указателей.

Вильям Пью разработал вариант не совсем обычного связного списка. На своем самом низком уровне это двухсвязный список с прямым указателем на следующий узел и обратным указателем на предыдущий узел. Однако в некоторых узлах списка с пропусками имеется еще один прямой указатель, направленный на узел, расположенный на несколько позиций вперед. Такой указатель позволяет "перепрыгнуть" через целый ряд других, обычных узлов. Кроме того, в некоторых из этих расширенных узлов имеется еще один дополнительный указатель, который позволяет перешагнуть еще дальше. Таким образом, список с пропусками выглядит примерно так, как показано на рис. 6.3. Обратите внимание, что, в конце концов, все указатели приходят к конечному элементу списка, а начальный узел является началом для прямых указателей всех уровней.

Из рисунка видно, что при поиске значения с использованием новых указателей, мы переходим сначала большими шагами, постепенно уменьшая размер "прыжков", пока искомое значение не будет найдено. Буквально через несколько параграфов процесс поиска будет описан более подробно.

Рисунок 6.3. Схематичное представление списка с пропусками

Поиск в списке с пропусками

Если еще раз внимательно посмотреть на рис. 6.3, можно обратить внимание, что полученный список можно охарактеризовать как несколько объединенных односвязных и двухсвязных списков. На уровне 0 находится двухсвязный список, далее, на уровне 1 – односвязный список, который соединяет каждый второй узел, после него на уровне 2 находится еще один односвязный список, который объединяет каждый четвертый узел и, наконец, на уровне 3 односвязный список соединяет каждый восьмой узел. Таким образом, чтобы, например, найти узел с именем g, нужно перейти по указателю уровня 2 от начального узла к узлу d, затем по указателю первого уровня до узла f и, наконец, по указателю уровня 0 до узла g. Следовательно, теоретически говоря, чтобы найти седьмой узел, нужно будет перейти всего по трем указателям.

Теперь, когда мы в общих чертах рассмотрели алгоритм, давайте опишем его более подробно. Пусть у нас уже имеется список с пропусками. (Скоро мы изучим принцип создания списка с пропусками, однако часть алгоритма создания представляет собой алгоритм поиска, который мы сейчас и рассматриваем.) Алгоритм поиска работает следующим образом:

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

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;

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

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 элементов).

2. Если искомый элемент найден, вызвать ошибку (мы скоро скажем, по какой причине) и остановиться.

3. Узел не найден. Как уже упоминалось, нам известно, между каким узлами необходимо вставить новый элемент. Кроме того, при поиске мы достигли уровня 0.

4. Установить значение переменной NewNode равным нулю.

5. С помощью генератора случайных чисел вычислить случайное число в диапазоне от 0 до 1.

6. Если случайное число меньше 0.25, увеличить значение переменной NewNode на единицу.

7. Если значение переменной NewNode меньше или равно текущему максимальному уровню списка (т.е. 11), вернуться к шагу 5.

8. Если значение переменной NewNode больше текущего максимального уровня списка, присвоить ей значение максимального уровня плюс один.

9. Создать узел уровня NewNode и установить его указатель данных на вставляемый элемент.

10. Теперь новый узел нужно учесть во всех указателях вплоть до уровня NewNode (именно поэтому мы записывали все значения переменной BeforeNode при поиске на шаге 1). Для этого выполняется алгоритм "вставить после" для двухсвязного списка на уровне 0 и для всех односвязных списков для уровней от 1 до NewNode.

В приведенном алгоритме существуют несколько "странных" шагов, которые требуют дополнительных объяснений. Так, например, шаги 5, 6, 7 и 8, на которых вычисляется значение переменной NewNode, – для чего они нужны? Прежде всего, здесь вычисляется размер нового узла. Как вы, наверное, помните, мы пытаемся создать список с требуемым количеством узлов каждого уровня. Узел уровня 0 должен создаваться в трех четвертях всех случаев, узел уровня 1 – в трех шестнадцатых всех случаев и т.д. Эти вычисления выполняются в цикле на шагах 5, 6 и 7. Во-вторых, на шаге 8 выполняется проверка того, что мы не вышли за границы максимального уровня списка. Не имеет смысла создавать узел, который находится на намного более высоком уровне, нежели текущий максимальный уровень. Поэтому максимальное значение уровня ограничивается увеличением уровня на единицу.

Шаг 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

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;

Полная реализация класса связного списка

Теперь, когда мы рассмотрели три сложных операции класса списка с пропусками, можно привести интерфейс самого класса. В отличие от класса связного списка, класс списка с пропусками не имеет функциональных возможностей, характерных для массивов. Дело не в том, что нельзя, например, организовать доступ к элементу списка по его индексу, а в том, что это первая структура данных в этой книге (в эту группу также можно включить хэш-таблицу и бинарное дерево), для которой такая операция просто не имеет смысла. Указание верного индекса для списка с пропусками требует прохода по самому нижнему уровню указателей. В этом случае нет необходимости организовывать столь сложную структуру узлов и указателей для обеспечения переходов различной длины. Поэтому для списков с пропусками обеспечиваются только функциональные возможности, характерные для баз данных: переход к следующему узлу и переход к предыдущему узлу. Очевидно, что для реализации таких методов необходимо ввести внутренний курсор. Методы MoveNext и MovePrior будут перемещать курсор, а метод Examine – возвращать элемент узла, в котором находится курсор. Метод Delete будет применяться для удаления элемента в позиции курсора и т.д.

Листинг 6.18. Интерфейс класса списка с пропусками