Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
В листинге 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. Интерфейс класса списка с пропусками
type
TtdSkipList = class private
FCompare : TtdCompareFunc;
FCount : integer;
FCursor : PskNode;
FDispose : TtdDisposeProc;
FHead : PskNode;
FMaxLevel : integer;
FName : TtdNameString;
FPRNG : TtdMinStandardPRNG;
FTail : PskNode;
protected
class function slAllocNode(aLevel : integer): PskNode;
procedure slError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure slFreeNode(aNode : PskNode);
class procedure slGetNodeManagers;
function slSearchPrim(aItem : pointer;
var aBeforeNodes : TskNodeArray): boolean;
public
constructor Create( aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
destructor Destroy; override;
procedure Add(aItem : pointer);
procedure Clear;
procedure Deleter-function Examine : pointer;
function IsAfterLast : boolean;
function IsBeforeFirst : boolean;
function IsEmpty : boolean;
procedure MoveAfterLast;
procedure MoveBeforeFirst;
procedure MoveNext;
procedure MovePrior;
procedure Remove(aItem : pointer);
function Search(aItem : pointer): boolean;
property Count : integer read FCount;
property MaxLevel : integer read FMaxLevel;
property Name : TtdNameString read FName write FName;
end;
Назначение большинства методов и свойств станет понятным, если вы вернетесь к описанию методов класса связных списков, которое приводится в главе 3.
Как и для классов связных списков, используется диспетчер узлов, который позволяет эффективно выделять и освобождать узлы. Тем не менее, для списков с пропусками имеется небольшое, однако важное отличие: узлы в списке с пропусками имеют разные размеры. Фактически в списке может быть до 12 видов узлов. Следовательно, для работы с узлами потребуется 12 диспетчеров. Процедура класса slGetNodeManagers выполняет инициализацию 12 диспетчеров узлов. Она вызывается в конструкторе Create класса списка с пропусками. Все объекты списков будут пользоваться одними и теми же диспетчерами. В заключительной части модуля все диспетчеры узлов удаляются.
Листинг 6.19. Конструктор и деструктор класса списка с пропусками
constructor TtdSkipList.Create(aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
var
i : integer;
begin
inherited Create;
{функция сравнения не может быть nil}
if not Assigned(aCompare) then
slError(tdeSkpLstNoCompare, 'Create');
{создать диспетчеры узлов}
slGetNodeManagers;
{выделить начальный узел}
FHead := slAllocNode (pred( tdcMaxSkipLevels));
FHead^.sknData := nil;
{выделить конечный узел}
FTail := slAllocNode (0);
FTail^.sknData := nil;
{задать прямые и обратные указатели для начального и конечного узлов}
for i := 0 to pred(tdcMaxSkipLevels) do
FHead^.sknNext[i] := FTail;
FHead^.sknPrev := nil;
FTail^.sknNext[0] :=nil;
FTail^.sknPrev := FHead;
{установить курсор на начальный узел}
FCursor := FHead;
{сохранить функцию сравнения и процедуру dispose}
FCompare := aCompare;
FDispose :=aDispose;
{создать генератор случайных чисел}
FPRNG := TtdMinStandardPRNG.Create(0);
end;
destructor TtdSkipList.Destroy;
begin
Clear;
slFreeNode(FHead);
slFreeNode(FTail);
FPRNG.Free;
inherited Destroy;
end;
Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.
Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.
Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.
