Перед тем как приступить к реализации класса TtdSingleLinkList для представления односвязного списка, рассмотрим несколько вводных замечаний.

Начнем с самого начала. Как уже упоминалось, было бы очень удобно использовать связный список, не беспокоясь о его узлах. Хотелось бы, чтобы класс связного списка мог работать с любыми типами указателей, подобно классу TList. Для получения доступа к элементам связного списка было бы желательно использовать индекс (несмотря на то что это может негативно сказаться на быстродействии), но еще лучше было бы использовать терминологию баз данных. Так, в связном списке можно использовать курсор, который указывает на "текущий" элемент списка. Тогда можно было бы написать методы для позиционирования курсора перед любым элементом списка, перемещения курсора на следующий элемент, вставки и удаления элемента в позиции курсора и т.д. Поскольку мы создаем связный список в виде класса, мы можем работать с родительским объектом текущего элемента, что позволит запрограммировать метод Insert так, как он реализован в TList (т.е. за счет перемещения текущего элемента и всех последующих элементов на одну позицию и вставки в освободившееся место нового элемента). Аналогично можно реализовать и метод Delete.

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

Листинг 3.7. Класс TtdSingleLinkList

TtdSingleLinkList = class private FCount : longint;
FCursor : PslNode;
FCursorlx: longint;
FDispose : TtdDisposeProc;
FHead : PslNode;
FNanie : TtdNameString;
FParent : PslNode;
protected
function sllGetItem(aIndex : longint) : pointers-procedure sllSetItem(aIndex : longint;
altem : 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(altem : pointer) : longint;
procedure Clear;
procedure Delete(alndex : longint);
procedure DeleteAtCursor;
function Examine : pointers-function First : pointers-function IndexOf (altem : pointer) : longint;
procedure Insert (alndex : longint;
altem : pointer);
procedure InsertAtCursor(altem : pointer);
function IsAfterLast : boolean;
function IsBeforeFirst : boolean;
function IsEmpty : boolean;
function Last : pointers-procedure MoveBeforeFirst;
procedure MoveNext ; procedure Remove (altem : pointer);
procedure Sort (aCompare : TtdCompareFunc);
property Count : longint read FCount;
property Items [alndex : longint] : pointer read sllGetltem write sllSetltem;
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 Ge tNodeManager ;
{распределить память под начальный узел) FHead : = PslNode (SLNodeManager. AllocNode);
FHeadA.slnNext : = nil;
FHeadA.slnData : = nil; {установить курсор) MoveBeforeFirst;
end;
destructor TtdSingleLinkList. Destroy;
begin
{удалить все узлы, включая начальный фиктивный узел) Clear;
SLNodeManager.FreeNode(FHead);
inherited Destroy;
end;

Особый интерес здесь представляет тот факт, что связный список организован таким образом, что для всех экземпляров класса TtdSingleLinkList создается только один диспетчер узлов. Все экземпляры пользуются одним и тем же диспетчером. Можно было бы запрограммировать, чтобы каждый класс создавал свой диспетчер, но это бы означало использование большого дополнительного объема для экземпляра класса. Таким образом, учитывая то, что в приложении, в котором имеется один связный список, как правило, есть несколько списков, было решено ввести переменную класса. Но во всех этих рассуждениях присутствует один недостаток: Delphi не поддерживает переменные класса. Поэтому в коде мы имитируем такую переменную, объявив ее как глобальную в разделе implementation модуля. Если вы просмотрите содержимое файла TDLnkLst.pas, то найдете следующее объявление:

var
SLNodeManager : TtdNodeManager;

Все методы класса односвязного списка можно разбить на две категории: методы, действующие по последовательной схеме (MoveBef oreFirst, InsertAtCursor и т.д.), и методы, которые работают со списком как с массивом (свойство Items, методы Delete, IndexOf и т.д.). Рассмотрим сначала методы первой группы, поскольку мы уже говорили о принципе их работы в начале главы при описании связных списков. Для упрощения реализации мы не только храним курсор (т.е. указатель на текущий узел) в объекте, но и родительский объект курсора (т.е. указатель на родительский объект текущего курсора). Такая схема позволяет упростить методы вставки и удаления элементов.

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

procedure TtdSingleLinkList.Clear;
var
Temp : PslNode;
begin
{удалить все узлы, за исключением начального; при возможности освободить все данные] Temp : = FHeadA.slnNext;
while (Temp <>
nil) do begin
FHeadA.slnNext : = TempA.slnNext;
if Assigned(FDispose) then FDispose(TempA.slnData);
SLNodeManager.FreeNode(Temp);
Temp : = FHeadA. slnNext;
end;
FCount := 0;
MoveBeforeFirst;
ends-procedure TtdSingleLinkList.DeleteAtCursor;
begin
if (FCursor = nil) or (FCursor = FHead) then sllError(tdeListCannotDelete, 1 Delete');

{удалить все элементы]

if Assigned(FDispose) then FDispose(FCursorA.slnData);

{удалить ссылки на узел и удалить сам узел]

FParentA.slnNext := FCursorA.slnNext;
SLNodeManager.FreeNode(FCursor);
FCursor := FParentA.slnNext;
dec(FCount);
ends-function TtdSingleLinkList .Examine : pointer;
begin
if (FCursor = nil) or (FCursor = FHead) then
sllError(tdeListCannotExamine, 1 Examine1); {вернуть данные с позиции курсора] Result := FCursorА.slnData;
end;
procedure TtdSingleLinkList.InsertAtCursor(altem : pointer);, var
NewNode : PslNode;
begin
{убедиться, что вставка производится не перед первой позицией; если курсор находится перед первой позицией, переместить его на одну позицию вперед}
if (FCursor = FHead) then MoveNext;
{распределить новый узел и вставить его в позицию курсора) NewNode : = PslNode (SLNodeManager. AllocNode) ; NewNodeA. slnData := altem;
NewNodeA.slnNext := FCursor;
FParentA.slnNext := NewNode;
FCursor := NewNode;
inc(FCount);
end;
function TtdSingleLinkList. IsAfterLast : boolean;
begin
Result := FCursor «
nils-end;

function TtdSingleLinkList.IsBeforeFirst : boolean; begin Result : « FCursor = FHead; ends-function TtdSingleLinkList. I sEmpty : boolean; begin Result := (Count = 0) ; ends-procedure TtdSingleLinkList.MoveBeforeFirst; begin {установить курсор на начальный узел]

FCursor : = FHead;
FParent := nil;
FCursorlx := -1; ends-procedure TtdSingleLinkList.MoveNext;
begin
{переместить курсор no его указателю Next, игнорировать попытку выхода за конечный узел списка] if (FCursor о nil) then begin
FParent := FCursor;
FCursor := FCursorA.slnNext;
inc(FCursorlx);
ends-end;

Вы, возможно, обратили внимание, что некоторые из приведенных методов пользуются полем объекта FCursorlx. Именно это поле позволяет обеспечить высокую эффективность методов, основанных на использовании индекса, поскольку в нем хранится индекс курсора (при этом первый узел имеет индекс 0, точно так же как в TList). Значение поля используется методом ellPositionAtNth, который оптимальным образом перемещает курсор в позицию с указанным индексом.

Листинг 3.10. Метод sllPositionAtNth

procedure TtdSingleLinkList.sllPositionAtNth(aIndex : longint); var
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
begin
{проверить, корректно ли задан индекс) if (alndex < 0) or (alndex >= Count) then
sllError(tdeListInvalidIndex/ 'sllPositionAtNth'); {обработать наиболее простой случай) if (alndex = FCursorlx) then
Exit;
{-для повышения быстродействия использовать локальные переменные-} {если заданный индекс меньше индекса курсора, переместить рабочий курсор в позицию перед всеми узлами) if (alndex <
FCursorlx) then begin
WorkCursor := FHead;
WorkParent :=nil;
WorkCursorlx := -1; end
{в противном случае поставить рабочий курсор в позицию текущего курсора) else begin
WorkCursor :=FCursor;
WorkParent : = FParent;
WorkCursorlx := FCursorlx;
end;
{пока индекс рабочего курсора меньше заданного индекса, передвинуть его на одну позицию вперед) while (WorkCursorlx <
alndex) do begin
WorkParent := WorkCursor;
WorkCursor : = WorkCursorA.slnNext;
inc(WorkCursorlx);
end;
{установить реальный курсор равным рабочему курсору) FCursor := WorkCursor;
FParent : = WorkParent;
FCursorlx := WorkCursorIx;
end;

Метод sllPositionAtNth для увеличения быстродействия использует локальные переменные. Вначале метод определяет, больше ли заданный индекс индекса курсора (в этом случае поиск узла начинается с позиции курсора) или же он меньше (поиск узла начинается с начала списка). Без знания позиции курсора мы всегда бы начинали поиск с начала списка.

Реализация остальных методов, основанных на использовании индекса, после написания кода метода sllPositionAtNth не представляет особых трудностей.

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

procedure TtdSingleLinkList .Delete (alndex : longint);
begin
{установить курсор в позицию с заданным индексом)
sllPositionAtNth(alndex);
{удалить элемент в позиции курсора)
DeleteAtCursor;
ends-function TtdSingleLinkList. First : pointers-begin
{установить курсор на первый узел)
SllPositionAtNth(0);
{вернуть данные с позиции курсора)
Result : = FCursorА.slnData;
ends-procedure TtdSingleLinkList. Insert (alndex : longint;
altem : pointer);
begin
{установить курсор в позицию с заданным индексом)
sllPositionAtNth(alndex);
{вставить элемент в позицию курсора)
InsertAtCursor(altem);
ends-function TtdSingleLinkList. Last : pointers-begin
{установить курсор в позицию с заданным индексом) sllPositionAtNth(pred(Count)); {вернуть данные с позиции курсора) Result : = FCursorА.slnData;
end;
function TtdSingleLinkList. sllGet I tern (alndex : longint) : pointers-begin
{установить курсор в позицию с заданным индексом)
sllPositionAtNth(alndex);
{вернуть данные с позиции курсора)
Result : = FCursorА.slnData;
ends-procedure TtdSingleLinkList. sllSet Item (alndex : longint;
altem : pointer);
begin
{установить курсор в позицию с заданным индексом) sllPositionAtNth(alndex);
{если возможно удалить заменяемые данные, удалить их)
if Assigned(FDispose) and (altem о FCursorA.sInData) then
FDispose(FCursorA.slnData); {заменить данные) FCursorA.slnData := altem;
end;

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

Листинг 3.12. Методы Add, IndexOf и Remove

function TtdSingleLinkList. Add (altem : pointer) : longint;
var
WorkCursor : PslNode;
WorkParent : PslNode;
begin
{для увеличения быстродействия используются локальные переменные)
WorkCursor :=FCursor;
WorkParent :=FParent;
{перешли в конец связного списка)
while (WorkCursor о nil) do begin
WorkParent := WorkCursor;
WorkCursor : = WorkCursorA.slnNext;
end;
{перенести реальный курсор) FParent := WorkParent;
FCursor := nil;
FCursorlx := Counts-Result := Count;
{вставить элемент в позицию курсора)
InsertAtCursor(altem);
ends-function TtdSingleLinkList.IndexOf(altem : pointer) : longint;
var
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
begin
{установить рабочий курсор на первый узел (если таковой существует)}
WorkParent := FHead;
WorkCursor := WorkParentA.slnNext;
WorkCursorIx := 0;
{идти по списку в поисках требуемого элемента) while (WorkCursor о nil) do begin if (WorkCursorA. slnData - altem) then begin
{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора) Result := WorkCursorIx;
FCursor := WorkCursor;
FParent := WorkParent;
FCursorlx := WorkCursorIx;
Exits-end;
{перешли к следующему узлу) WorkParent := WorkCursor;
WorkCursor : = WorkCursorА.slnNext;
inc(WorkCursorIx);
end;
{требуемый элемент не найден)
Result := -1; ends-procedure TtdSingleLinkList. Remove (altem : pointer);
begin
if (IndexOf (altem) <> -1) then DeleteAtCursor;
end;

Полный код класса TtdSingleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnlLst.pas.

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

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


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



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

  • Апрель
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс