иметь неверную длину (что в итоге может привести к перезаписи памяти) или может принадлежать к другому классу, который, возможно, очистит страницу, содержащую узел, и т.д. При отладке имеет смысл проводить проверку принадлежности к классу всех освобождаемых узлов. Реализация, содержащаяся в рамках сопровождающих книгу материалов, включает специальный код проверки при условии, что модель будет компилироваться с использованием утверждений.
Вторая проблема вызвана тем, что мы легко можем удалить экземпляр диспетчера узлов до удаления объектов, которые эти узлы используют. Это приведет к возникновению неизвестных ошибок. Только достаточная внимательность во время программирования может нас избавить от такого рода ошибок.
(Кстати, в качестве простого доказательства того, что мы не зря потеряли время на реализацию диспетчера узлов, можно сказать, что тесты по распределению и освобождению одного миллиона узлов показали, что диспетчер узлов работает в 3-4 раза быстрее, чем диспетчер кучи Delphi.)
Класс односвязного списка
Перед тем как приступить к реализации класса TtdSingleLinkList для представления односвязного списка, рассмотрим несколько вводных замечаний.
Начнем с самого начала. Как уже упоминалось, было бы очень удобно использовать связный список, не беспокоясь о его узлах. Хотелось бы, чтобы класс связного списка мог работать с любыми типами указателей, подобно классу TList. Для получения доступа к элементам связного списка было бы желательно использовать индекс (несмотря на то что это может негативно сказаться на быстродействии), но еще лучше было бы использовать терминологию баз данных. Так, в связном списке можно использовать курсор, который указывает на 'текущий' элемент списка. Тогда можно было бы написать методы для позиционирования курсора перед любым элементом списка, перемещения курсора на следующий элемент, вставки и удаления элемента в позиции курсора и т.д. Поскольку мы создаем связный список в виде класса, мы можем работать с родительским объектом текущего элемента, что позволит запрограммировать метод Insert так, как он реализован в TList (т.е. за счет перемещения текущего элемента и всех последующих элементов на одну позицию и вставки в освободившееся место нового элемента). Аналогично можно реализовать и метод Delete.
Интерфейс класса 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;
Несмотря на то что названия методов соответствуют стандарту TList, появилось несколько новых методов. Метод MoveBeforeFirst помещает курсор перед всеми элементами связного списка. IsBeforeFirst и IsAfterLast возвращают True, если курсор находится, соответственно, перед всеми элементами или после всех элементов списка. Метод MoveNext перемещает курсор на следующий элемент списка. Свойство Items аналогично соответствующему свойству списка TList: элементы нумеруются от 0 до Count-1.
Конструктор 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;
