Интерфейс класса двухсвязного списка выглядит следующим образом:

Листинг 3.13. Класс TtdDoubleLinkList

TtdDoubleLinkList = class private FCount : longint;
FCursor : PdlNode;
FCursorlx: longint;
FDispose : TtdDisposeProc;
FHead : PdlNode;
FName : TtdNameString;
FTail : PdlNode;
protected
function dllGetItem(aIndex : longint) : pointers-procedure dllSet Item (aIndex : longint;
altem : pointer);
procedure dllError(aErrorCode : integer;
const aMethodName : TtdNameString);
class procedure dllGetNodeManager;
procedure dllPositionAtNth(aIndex : longint);
public

constructor Create(aDispose : TtdDisposeProc);
destructor Destroy;
override; function Add (altem : pointer) : longint;
procedure Clear;
procedure Delete(aIndex : longint);
procedure DeleteAtCursor;
function Examine : pointer;
function First : pointer;

function IndexOf(altem : pointer) : longint; procedure Insert (aIndex : longint; altem : pointer); procedure InsertAtCursor(altem : pointer); function IsAfterLast : boolean; function IsBeforeFirst : boolean; function IsEmpty : boolean; function Last : pointers-procedure MoveAfterLast; procedure MoveBef oreFirst; procedure MoveNext; procedure MovePrior; procedure Remove (altem : pointer) ; procedure Sort (aCompare : TtdCompareFunc) ; property Count : longint read FCount ; property Items [aIndex : longint] : pointer

read dllGetltem write dllSetltem;
default; property Name : TtdNameString read FName write FName;
end;

Как видите, этот интерфейс очень похож на интерфейс класса TtdSingleLinkList. Собственно, так и должно быть. Для пользователя должно быть безразлично, какой класс он выбирает, оба они должны работать одинаково. Сам выбор односвязного или двухсвязного списка должен зависеть от назначения. Если большая часть перемещений курсора направлена вперед и доступ к случайным элементам выполняется редко, эффективнее использовать односвязный список. Если же высока вероятность того, что список будет проходиться как в прямом, так и в обратном направлениях, то, несмотря на большие требования к памяти, лучше выбрать двухсвязный список. Если же ожидается, что доступ к элементам списка будет осуществляться, в основном, в случайном порядке, выберите класс TList, несмотря на то, что он требует несколько большего времени на вставку и удаление элемента.

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

Конструктор Create распределяет при помощи диспетчера узлов еще один дополнительный фиктивный узел - FTail. Как упоминалось во введении к двухсвязным спискам, он предназначен для обозначения конца списка. Начальный и конечный фиктивные узлы вначале будут связаны друг с другом, т.е. ссылка Next начального узла указывает на конечный узел, а ссылка Prior конечного узла - на начальный узел. Естественно, деструктор Destroy будет удалять фиктивный конечный узел и возвращать его вместе с начальным узлов в диспетчер узлов.

Листинг 3.14. Конструктор Create и деструктор Destroy класса TtdDoubleLinkList

constructor TtdDoubleLinkList.Create;
begin
inherited Create;

{сохранить процедуру удаления]

FDispose :=aDispose;
{получить диспетчер узлов}
dllGetNodeManager;
{распределить и связать начальный и конечный узлы] FHead : - PdlNode (DLNodeManager. AllocNode) ; FTail : = PdlNode (DLNodeManager. AllocNode) ; FHeadA. dlnNext : = FTail ; FHeadA. dlnPrior :=nil;
FHeadA.dlnData : = nil;
FTailA.dlnNext : = nil;
FTailA.dlnPrior := FHead;
FTailA.dlnData := nil; {установить курсор на начальный узел] FCursor := FHead;
FCursorlx := -1;
end;
destructor TtdDoiibleLinkList. Destroy;
begin if (Count <> 0) then Clear;
DLNodeManager. FreeNode (FHead) ; DLNodeManager.FreeNode(FTail);
inherited Destroy;
end;

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

Листинг 3.15. Стандартные для связного списка операции для класса TtdDoubleLinkList

procedure TtdDoubleLinkList. Clear;
var
Temp : PdlNode;
begin
{удалить все узлы, за исключением начального и конечного; если возможно их освободить, то сделать это] Temp : = FHeadA. dlnNext;
while (Temp о FTail) do begin
FHeadA.dlnNext : = TempA.dlnNext;
if Assigned(FDispose) then FDispose(TempA.dlnData);
DLNodeManager.FreeNode(Temp);
Temp : = FHeadA. dlnNext ;
end;
{устранить "дыру" в связном списке) FTailA.dlnPrior : = FHead;
FCount := 0;
{установить курсор на начальный узел) FCursor := FHead;
FCursorlx := -1;
end;
procedure TtdDoubleLinkList. DeleteAtCursor;
var
Temp : PdlNode;
begin
{записать в Temp удаляемый узел) Temp := FCursor;
if (Temp = FHead) or (Temp = FTail) then
dllError(tdeListCannotDelete, ' Delete•); {избавиться от его содержимого) if Assigned (FDispose) then
FDispose(TempA.dlnData); {удалить ссылки на узел и освободить его; курсор перемещается на следующий узел)
TempА.dlnPriorА.dlnNext : = TempА.dlnNext;
TempA.dlnNextА.dlnPrior : = TempA.dlnPrior;
FCursor : = TempA.dlnNext;
DLNodeManager.FreeNode(Temp);
dec(FCount);
end;
function TtdDoubleLinkList.Examine : pointer;
begin
if (FCurgor = nil) or (FCursor = FHead) then
dllError(tdeListCannotExamine, 'Examine1); {вернуть данные узла в позиции курсора) Result : = FCursorА.dlnData;
end;
procedure TtdDoubleLinkLi st. InsertAtCursor (altem : pointer); var
NewNode : PdlNode;
begin
(если курсор находится на начальном узле, не генерировать исключение, а перейти на следующий узел) if (FCursor = FHead) then
MoveNext;
{распределить новый узел и вставить его перед позицией курсора) NewNode : = PdlNode (DLNodeManager. AllocNode);
NewNodeA. dlnData := altem;
NewNodeA .dlnNext := FCursor;
NewNodeA.dlnPrior : = FCursorA.dlnPrior;
NewNodeA. dlnPriorA. dlnNext : = NewNode ; FCursorA.dlnPrior : = NewNode;
FCursor := NewNode;
inc(FCount);
end;
function TtdDoubleLinkList. IsAfterLast : boolean;
begin
Result := FCursor = FTail;
end;
function TtdDoubleLinkList.IsBeforeFirst ; boolean;
begin
Result : = FCursor = FHead;
end;
function TtdDoubleLinkList. IsEmptу : boolean;
begin
Result := (Count = 0) ;
end;
procedure TtdDoubleLinkLi st. MoveAf terLast ; begin
{установить курсор на конечный узел) FCursor := FTail;
FCursorIx := Count;
end;
procedure TtdDoubleLinkList .MoveBeforeFirst;
begin
{установить курсор на начальный узел) FCursor : = FHead;
FCursorlx := -1;
end;
procedure TtdDoubleLinkList .MoveNext;
begin
{переместить курсор no его прямому указателю) if (FCursor о FTail) then begin
FCursor := FCursorA.dlnNext;
inc(FCursorlx);
end;
end;
procedure TtdDoubleLinkList .MovePrior;
begin
{переместить курсор no eao обратному указателю) if (FCursor <>
FHead) then begin
FCursor := FCursorA.dlnPrior;
dec(FCursorlx);
end;
end;

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

Методы, основанные на использовании индекса, в случае двухсвязного списка реализуются проще, чем в случае односвязного. Единственную сложность представляет метод dllPositionAtNth, предназначенный для установки курсора в позицию с заданным индексом. Вспомните алгоритм для односвязного списка: если заданный индекс соответствует позиции после курсора, начать с позиции курсора и идти вперед, вычисляя индекс. В двухсвязном списке при необходимости можно двигаться и в обратном направлении. Таким образом, алгоритм поиска можно немного изменить. Как и ранее, мы определяем, где по отношению к курсору находится узел с заданным индексом. После этого выполняется еще одно вычисление -ближе к какому узлу находится узел с заданным индексом: к начальному, конечному или к текущему? Далее мы начинаем прохождение с ближайшего узла, при необходимости двигаясь вперед или назад.

Листинг 3.16. Установка курсора на узел с индексом п для класса TtdDoubleLinkList

procedure TtdDoubleLinkList.dllPositionAtNth(aIndex : longint); var
WorkCursor : PdlNode;
WorkCursorlx : longint;
begin
{проверить, корректно ли задан индекс] if (alndex < 0) or (alndex Count) then
dllError(tdeListInvalidIndex, 1dllPositionAtNth1); {для увеличения быстродействия используются локальные переменные] WorkCursor :=FCursor;
WorkCursorlx :=FCursorIx; {обработать наиболее простой случай] if (alndex = WorkCursorlx) then
Exit;
{заданный индекс либо перед курсором, либо после неао; в любом случае, заданный индекс ближе либо к курсору, либо к соответствующему концу списка; определить самый короткий путь} if (alndex <
WorkCursorlx) then begin if ((alndex - 0) < (WorkCursorlx - alndex)) then begin
{начать с начального узла и двигаться вперед до индекса alndex] WorkCursor r^FHead;
WorkCursorlx :== -1;
end;
end
else {alndex >
FCursorlx} begin if ((alndex - WorkCursorlx) < (Count - alndex)) then begin {начать с конечного узла и двигаться назад до индекса alndex) WorkCursor :=FTail;
WorkCursorlx := Count;
end;
end;
{пока индекс рабочего курсора меньше заданного индекса, перемещать рабочий курсор на одну позицию вперед) while (WorkCursorlx <
alndex) do begin
WorkCursor : = WorkCursor*. dlnNext;
inc(WorkCursorlx);
end;
{пока индекс рабочего курсора больше заданного индекса, перемещать рабочий курсор на одну позицию назад) while (WorkCursorlx >
alndex) do begin
WorkCursor : = WorkCursorA.dlnPrior;
dec(WorkCursorlx);
end;
{установить реальный курсор равным рабочему курсору) FCursor := WorkCursor;
FCursorlx := WorkCursorIx;
end;

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

Листинг 3.17. Методы класса TtdDoubleLinkList, основанные на использовании индекса

function TtdDoubleLinkList .Add (altem : pointer) : longint;
begin
{перейти к концу связного списка) FCursor := FTail;, FCursorlx := Count; {вернуть индекс нового узла) Result Count;
{вставить элемент в позицию курсора) InsertAtCursor(altem);
end;
procedure TtdDoubleLinkList .Delete (alndex : longint);
begin
{установить курсор в позицию с заданным индексом) dllPositionAtNth(alndex); {удалить элемент в позиции курсора) DeleteAtCursor;
end;
function TtdDoubleLinkList.dllGetItem(alndex : longint) : pointer;
begin
{установить курсор в позицию с заданным индексом) dllPositionAtNth(alndex); {вернуть данные из позиции курсора) Result : = FCursorА.dlnData;
end;
procedure TtdDoubleLinkList.dllSetItem(alndex : longint;
altem : pointer);
begin
{установить курсор в позицию с заданным индексом) dllPositionAtNth(alndex);
{если возможно удалить заменяемые данные, удалить их)
if Assigned(FDispose) and (altem <>
FCursorA .dlnData) then FDispose(FCursorA.dlnData);
{заменить данные)
FCursorA.dlnData : = altem;
end^-function TtdDoubleLinkList. First : pointer;
begin
{установить курсор на первый узел) dllPositionAtNth(0); {вернуть данные из позиции курсора) Result := FCursorА.dlnData;
end;
function TtdDoubleLinkList.IndexOf(altem : pointer) : longint;
var
WorkCursor : PdlNode;
WorkCursorlx : longint;
begin
{установить рабочий курсор на первый узел (если он существует)} WorkCursor : = FHeadA.dlnNext;
WorkCursorlx := 0;
{идти no списку в поисках требуемого элемента) while (WorkCursor о FTail) do begin if (WorkCursorA. dlnData = altem) then begin
{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора}
Result := WorkCursorlx;
FCursor := WorkCursor;
FCursorlx := WorkCursorlx;
Expend;
{перейти к следующему узлу) WorkCursor : = WorkCursorА.dlnNext;
inc(WorkCursorlx);
end;
{требуемый элемент не найден) Result := -1;
end;
procedure TtdDoubleLinkList. Insert (alndex : longint;
altem : pointer);

begin {установить курсор в позицию с заданным индексом]

dllPositionAtNth(alndex);
{вставить элемент в позицию курсора)
InsertAtCursor(altem);
end.-function TtdDoubleLinkList. Last : pointer;
begin
{установить курсор на последний узел)
dllPositionAtNth(pred(Count));

{вернуть данные из позиции курсора) Result : = FCursorА.dlnData; ends-procedure TtdDoubleLinkList .Remove (altem : pointer); begin if (IndexOf (altem) о -1) then DeleteAtCursor; ends-Полный код класса TtdDoubleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.

Использование диспетчера узлов || Оглавление || Достоинства и недостатки связных списков


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



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

  • Август
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс