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

Бакнелл Джулиан М.
Шрифт:

В листинге 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 класса списка с пропусками. Все объекты списков будут пользоваться одними и теми же диспетчерами. В заключительной части модуля все диспетчеры узлов удаляются.