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

Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель Prior позволяет проходить список в обратном направлении. Фактически операцию "вставить перед" можно запрограммировать как "перейти к предыдущему узлу и вставить после". Поэтому в главе мы рассмотрим только операцию "вставить после".

Ссылка Next нового узла устанавливается на узел, расположенный после заданного узла, а ссылка Next заданного узла устанавливается на новый узел. Для установки обратных ссылок ссылка Prior нового узла устанавливается на заданный узел, а ссылка Prior узла, следующего за новым, устанавливается на новый узел. В коде это выглядит следующим образом:

var

GivenNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data ..

NewNode^.Next := GivenNode^.Next;

GivenNode^.Next := NewNode;

NewNode^.Prior := GivenNode;

NewNode^.Next^.Prior := NewNode;

В случае с удалением проще всего удалить узел, находящийся после заданного узла. Необходимо установить ссылку Next заданного узла на узел, находящийся после удаляемого, а ссылку Prior узла, находящегося после удаляемого, на заданный узел.

Рисунок 3.5. Вставка нового узла в двухсвязный список

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

var

GivenNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := GivenNode^.Next;

GivenNode^.Next := NodeToGo^.Next;

NodeToGo^.Next^.Prior := GivenNode;

Dispose(NodeToGo);

Как и для односвязных списков, здесь для обеих операций существуют специальные случаи: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев потребуется написать отдельно.

Рисунок 3.6. Удаление узла в двухсвязном списке

Вставка:

var

FirstNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data..

NewNode^.Next := FirstNode;

NewNode^.Prior := nil;

FirstNode^.Prior := NewNode;

FirstNode := NewNode;

Удаление:

var

FirstNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := FirstNode;

FirstNode := NodeToGo^.Next;

FirstNode^.Prior := nil;

Dispose(NodeToGo);

Использование начального и конечного узлов

Для односвязного списка было показано, что наличие начального узла существенно упрощало операции вставки и удаления. Соответствующий случай для двухсвязного списка - наличие двух фиктивных узлов: начального и конечного. Они позволяют очень легко выполнять прохождение списка от первого узла к последнему, равно как от последнего к первому. Специальные случаи при этом исключаются.

Использование диспетчера узлов

Как и для односвязного списка, данные в списке удобно хранить в виде указателей. Это позволяет написать общий класс двухсвязного списка. В двухсвязном списке в каждом узле будет находиться прямой указатель, обратный указатель и указатель на данные. Общий размер узла составит 12 байт (т.е. 3*sizeof(pointer)). Все узлы одинаковы, таким образом, можно реализовать диспетчер узлов и для двухсвязного списка.

Класс двухсвязного списка

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

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

TtdDoubleLinkList = class private

FCount : longint;

FCursor : PdlNode;

FCursorIx: longint;

FDispose : TtdDisposeProc;

FHead : PdlNode;

FName : TtdNameString;

FTail : PdlNode;

protected

function dllGetItem(aIndex : longint): pointer;

procedure dllSetItem(aIndex : longint; aItem : 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(aItem : pointer): longint;

procedure Clear;

procedure Delete(aIndex : longint);

procedure DeleteAtCursor;

function Examine : pointer;

function First : pointer;

function IndexOf(aItem : pointer): longint;

procedure Insert(aIndex : longint; aItem : pointer);

procedure InsertAtCursor(aItem : pointer);

function IsAfterLast : boolean;

function IsBeforeFirst : boolean;

function IsEmpty : boolean;

function Last : pointer;

procedure MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

procedure Sort(aCompare : TtdCompareFunc);

property Count : longint read FCount;

property Items[aIndex : longint] : pointer

read dllGetItem write dllSetItem; default;

property Name : TtdNameString read FName write FName;

end;