Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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 начальным узлом. Затем поиск начинается с высшего
После этого производится сравнение. Если данные равны, искомый узел найден, и после установки нескольких переменных выполнение метода завершается. Если данные узла меньше, чем искомые данные, осуществляется переход по прямому указателю. В противном случае текущий уровень записывается в массив aBeforeNode и значение уровня уменьшается на единицу.
Вставка в список с пропусками
После изучения алгоритма поиска узла в существующем списке с пропусками, давайте рассмотрим алгоритм построения списка с помощью операции вставки нового узла. Вернувшись к рисунку 6.3, можно сказать, что задача сохранения однородной структуры списка после серии выполнения вставок и удалений кажется практически невыполнимой.
Достоинство алгоритма вставки, разработанного Пью, заключается в том, что Пью понимал, что построение абсолютно однородной структуры списка, по сути дела, невозможно или, по крайней мере, является сложной и трудоемкой операцией. Поэтому он предложил список с пропусками, который в среднем приближается к однородной структуре. В однородном списке с пропусками с множителем 4 один из четырех узлов больше трех других, поскольку он содержит дополнительный прямой указатель. В свою очередь, один из четырех этих больших узлов содержит еще один дополнительный указатель и т.д. В конце концов, можно прийти к выводу, что в однородном списке с пропусками три четверти всех узлов находятся на уровне 0, три шестнадцатых - на уровне 1, три шестьдесят четвертых - на уровне 2 и т.д. Другими словами, при случайном выборе узла можно установить следующие вероятности выбора узлов по уровням:
0.75 для уровня 0,
0.1875 для уровня 1,
0.046875 для уровня 2 и т.д.
Алгоритм вставки в список с пропусками учитывает эти вероятности таким образом, чтобы в общем на каждом уровне находилось требуемое количество узлов. Это означает, что в среднем вероятностный список с пропусками будет работать с той же эффективностью, что и "однородный": поиск некоторых узлов будет осуществляться чуть дольше, а других - чуть быстрее, однако, в среднем, поиск в реальном списке с пропусками будет занимать примерно столько же времени, сколько и в идеальном однородном списке.
После такой теоретической подготовки можно перейти к описанию самого алгоритма вставки. Начинаем с пустого списка. Пустой список с пропусками содержит начальный узел уровня 11 и конечный узел уровня 0. Все прямые указатели начального узла указывают на конечный узел. Обратный указатель конечного узла указывает на начальный узел. Алгоритм вставки работает следующим образом:
1. Выполнить в списке поиск вставляемого элемента с одним дополнительным условием. При каждом понижении уровня сохранять значение переменной BeforeNode. В конце концов, мы получим набор значений BeforeNode, по одному для каждого
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 Кто-то может сказать, что узлы с равными значениями должны находиться в списке в том порядке, в котором они вставлялись. Это означает, что при вставке элемента он будет добавляться в конец последовательности узлов с равными значениями, а при поиске нужно будет находить первый из повторяющихся узлов. Для алгоритма вставки при понижении уровней нужно сохранять список "предыдущих узлов". Эту операцию выполнить сложнее. По мнению автора книги, излишняя сложность алгоритмов для обеспечения возможности хранения в списке с пропусками узлов с одинаковыми значениями себя совершенно не оправдывает. Будем считать, что если существует вероятность повторения узлов, то мы знаем, как их различать между собой. В противном случае, они будут трактоваться как действительно один и тот же узел. Если мы можем различать повторяющиеся узлы, то можно предположить, что такая же возможность заложена и в функции сравнения. Следовательно, узлы уже не будут считаться повторениями.