Теперь, когда мы рассмотрели три сложных операции класса списка с пропусками, можно привести интерфейс самого класса. В отличие от класса связного списка, класс списка с пропусками не имеет функциональных возможностей, характерных для массивов. Дело не в том, что нельзя, например, организовать доступ к элементу списка по его индексу, а в том, что это первая структура данных в этой книге (в эту группу также можно включить хэш-таблицу и бинарное дерево), для которой такая операция просто не имеет смысла. Указание верного индекса для списка с пропусками требует прохода по самому нижнему уровню указателей. В этом случае нет необходимости организовывать столь сложную структуру узлов и указателей для обеспечения переходов различной длины. Поэтому для списков с пропусками обеспечиваются только функциональные возможности, характерные для баз данных: переход к следующему узлу и переход к предыдущему узлу. Очевидно, что для реализации таких методов необходимо ввести внутренний курсор. Методы 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 (altem : 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 (altem : pointer) ; function Search (altem : 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)) ; FHeadA.sknData : = nil; {выделить конечный узел) FTail := slAllocNode (0);
FTailA.sknData := nil;
{задать прямые и обратные указатели для начального и конечного узлов) for i : = 0 to pred(tdcMaxSkipLevels) do
FHeadA.sknNext[i] : = FTail;
FHeadA.sknPrev : = nil;
FTailA.sknNext[0] :=nil;
FTailA.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 предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.

Листинг 6.20. Очистка содержимого списка с пропусками

procedure TtdSkipList.Clear;
var
i : integer;
Walker, Temp : PskNode;
begin
{пройти no узлам уровня 0, освобождая все узлы] Walker : = FHeadA.sknNext[0]; while (WalkeroFTail) do begin Temp Walker ;
Walker : = WalkerA.sknNext[0]; slFreeNode(Temp);
end;
{восстановить начальный и конечный узлы) for i : = 0 to pred(tdcMaxSkipLevels) do
FHeadA.sknNext[i] : = FTail;
FTailA.sknPrev : = FHead;
FCount := 0;
end;

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

Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками

class function TtdSkipList.slAllocNode(aLevel : integer) : PskNode;
begin
Result := SLNodeManager[aLevel].AllocNode;
ResultA.sknLevel : = aLevel;
end;
procedure TtdSkipList.siFreeNode(aNode : PskNode);
begin
if (aNodeonil) then begin if Assigned(FDispose) then
FDispose(aNodeA.sknData);
SLNodeManager[aNodeA.sknLevel].FreeNode(aNode);
end;
end;
class procedure TtdSkipList. slGetNodeManagers;
var
i : integer;
begin
{если диспетчеры узлов еще не созданы, создать их) If (SLNodeManager[0] =nil) then for i : = 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] : = TtdNodeManager.Create(NodeSize[i]);
end;

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

Остальные методы класса списка с пропусками еще проще - все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Deleter-begin
{начальный и конечный узлы удалять нельзя] if (FCursor = FHead) or (FCursor = FTail) then
slError(tdeListCannotDelete, 'Deletef); {удалить узел в позиции курсора] Remove(FCursorА.sknData);
end;
function TtdSkipList.Examine : pointer;
begin
Result := FCursorA.sknData;
end;
function TtdSkipList. IsAfterLast : boolean;
begin
Result := FCursor = FTail;
end;
function TtdSkipList. IsBeforeFirst : boolean;
begin
Result := FCursor = FHead;
end;
function TtdSkipList.IsEmptу : boolean;
begin
Result := Count = 0;
end;
procedure TtdSkipList .MoveAf terLast ; begin
FCursor := FTail;
end;
procedure TtdSkipList. MoveBef oreFirst;
begin
FCursor := FHead;
end;
procedure TtdSkipList .MoveNext;
begin
if (FCursorOFTail) then
FCursor : = FCursorA.sknNext[0];
end;
procedure TtdSkipList. Move Prior ; begin
if (FCursorOFHead) then
FCursor := FCursor74. sknPrev;
end;

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

Удаление из списка с пропусками || Оглавление || Резюме6


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



Новости за месяц

  • Июнь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс