Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Интерфейс класса TtdSingleLinkList выглядит следующим образом:
Листинг 3.7. Класс TtdSingleLinkList
TtdSingleLinkList = class private
FCount : longint;
FCursor : PslNode;
FCursorIx: longint;
FDispose : TtdDisposeProc;
FHead : PslNode;
FNanie : TtdNameString;
FParent : PslNode;
protected
function sllGetItem(aIndex : longint): pointer;
procedure sllSetItem(aIndex : longint; aItem : pointer);
procedure sllError(aErrorCode : integer;
const aMethodName : TtdNameString);
class procedure sllGetNodeManager;
procedure sllPositionAtNth(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 MoveBeforeFirst;
procedure MoveNext;
procedure Remove(aItem : pointer);
procedure Sort(aCompare : TtdCompareFunc);
property Count : longint read FCount;
property Items[aIndex : longint] : pointer read sllGetItem write sllSetItem; default;
property Name : TtdNameString read FName write FName;
end;
Несмотря
Конструктор Create проверяет, создан ли экземпляр диспетчера узлов, а затем распределяет память для узла, который будет фиктивным начальным узлом. Затем курсор помещается перед всеми узлами (поскольку в списке еще нет узлов, это совсем несложно). Деструктор Destroy очищает связный список и освобождает фиктивный начальный узел, выделенный конструктором Create.
Листинг 3.8. Конструктор и деструктор класса TtdSingleLinkList
constructor TtdSingleLinkList.Create(aDispose : TtdDisposeProc);
begin
inherited Create;
{сохранить процедуру удаления}
FDispose :=aDispose;
{получить диспетчер узлов}
s 11 GetNodeManager;
{распределить память под начальный узел}
FHead := PslNode (SLNodeManager.AllocNode);
FHead^.slnNext := nil;
FHead^.slnData := nil;
{установить курсор}
MoveBeforeFirst;
end;
destructor TtdSingleLinkList.Destroy;
begin
{удалить все узлы, включая начальный фиктивный узел}
Clear;
SLNodeManager.FreeNode(FHead);
inherited Destroy;
end;
Особый интерес здесь представляет тот факт, что связный список организован таким
образом, что для всех экземпляров класса TtdSingleLinkList создается только один диспетчер узлов. Все экземпляры пользуются одним и тем же диспетчером. Можно было бы запрограммировать, чтобы каждый класс создавал свой диспетчер, но это бы означало использование большого дополнительного объема для экземпляра класса. Таким образом, учитывая то, что в приложении, в котором имеется один связный список, как правило, есть несколько списков, было решено ввести переменную класса. Но во всех этих рассуждениях присутствует один недостаток: Delphi не поддерживает переменные класса. Поэтому в коде мы имитируем такую переменную, объявив ее как глобальную в разделе implementation модуля. Если вы просмотрите содержимое файла TDLnkLst.pas, то найдете следующее объявление:var
SLNodeManager : TtdNodeManager;
Все методы класса односвязного списка можно разбить на две категории: методы, действующие по последовательной схеме (MoveBeforeFirst, InsertAtCursor и т.д.), и методы, которые работают со списком как с массивом (свойство Items, методы Delete, IndexOf и т.д.). Рассмотрим сначала методы первой группы, поскольку мы уже говорили о принципе их работы в начале главы при описании связных списков. Для упрощения реализации мы не только храним курсор (т.е. указатель на текущий узел) в объекте, но и родительский объект курсора (т.е. указатель на родительский объект текущего курсора). Такая схема позволяет упростить методы вставки и удаления элементов.
Листинг 3.9. Стандартные операции со связным списком для класса TtdSingleLinkList
procedure TtdSingleLinkList.Clear;
var
Temp : PslNode;
begin
{удалить все узлы, за исключением начального; при возможности освободить все данные}
Temp := FHead^.slnNext;
while (Temp <> nil) do
begin
FHead^.slnNext := Temp^.slnNext;
if Assigned(FDispose) then
FDispose(Temp^.slnData);
SLNodeManager.FreeNode(Temp);
Temp := FHead^.slnNext;
end;
FCount := 0;
MoveBeforeFirst;
end;
procedure TtdSingleLinkList.DeleteAtCursor;
begin
if (FCursor = nil) or (FCursor = FHead) then
sllError(tdeListCannotDelete, 'Delete');
{удалить все элементы}
if Assigned(FDispose) then
FDispose(FCursor^.slnData);
{удалить ссылки на узел и удалить сам узел}
FParent^.slnNext := FCursor^.slnNext;
SLNodeManager.FreeNode(FCursor);
FCursor := FParent^.slnNext;
dec(FCount);
end;
function TtdSingleLinkList.Examine : pointer;
begin
if (FCursor = nil) or (FCursor = FHead) then
sllError(tdeListCannotExamine, 'Examine');
{вернуть данные с позиции курсора}
Result := FCursor^.slnData;
end;
procedure TtdSingleLinkList.InsertAtCursor(aItem : pointer);
var
NewNode : PslNode;
begin
{убедиться, что вставка производится не перед первой позицией; если курсор находится перед первой позицией, переместить его на одну позицию вперед}
- Telegram
- Viber
- Skype
- ВКонтакте