Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 38

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;