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

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

Еще раз просмотрите код вставки и удаления элемента связного списка. Не кажется ли вам неудобным наличие двух случаев для обеих операций? Отдельные специальные случаи нужны для обработки вставки и удаления первого узла - операция, которая, возможно, будет выполняться не очень часто. Может быть, существует другой способ? Другой способ действительно есть, он предусматривает использование фиктивного начального узла. Фиктивный начальный узел - это узел, который нужен только в качестве заполнителя, в нем не будут храниться данные. Первым реальным узлом будет тот, на который указывает указатель Next фиктивного узла. Связный список, как и раньше, заканчивается узлом, указатель Next которого равен nil. При создании такого списка его нужно правильно инициализировать, выделив память под начальный узел и установив его указатель Next равным nil.

var
HeadNode : PSimpleNode;
begin
• • «
New(HeadNode) ; HeadNodeA.Next : = nil;

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

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

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

Перед написанием класса связного списка нужно рассмотреть еще один вопрос. Мы начали с того, что объявили тип узла как запись (тип TSixnpleNode), в которой хранятся (1) данные и (2) указатель на следующий узел списка. Второе поле записи удалить нельзя - оно требуется для организации связного списка. Но первое зависит от приложения или конкретного использования списка в данный момент. Фактически поле данных может представлять собой не одно, а несколько полей в отдельной записи или даже объект. Очень сложно написать общий класс связного списка, если неизвестен тип данных, который будет в нем содержаться.

Однако решение этой задачи существует, даже целых два. Первое - объявить класс родительского узла, который бы содержал только указатель Next, а пользователь сам в дочернем классе объявит элементы, содержащие данные узла. В таком случае реализация базового класса будет распределять и освобождать память для узла, поскольку все, что нужно для организации связного списка - это выделенные узлы, указателями Next которых можно манипулировать. Такое решение одновременно является как элегантным, так и неэлегантным. Оно соответствует парадигме объектно-ориентированного программирования, но для хранения данных приходится объявлять дочерний класс (а что если элементы, которые необходимо поместить в список, являются экземплярами класса, над которым вы не имеете контроля?).

Второе решение, которое можно считать более удачным, - представить данные в форме нетипизированного указателя. (Для этого имеются все предпосылки - в Delphi подобным образом работает стандартный класс TList.) При добавлении элемента в связный список классу списка передается только значение указателя (скажем, указателя на данные или объект в куче), а все остальное делает сам список: распределяет память под узел, устанавливает значения данных и манипулирует ссылками. Это решение обходит проблему незнания типа данных, поскольку пользователь класса может не беспокоиться об указателях Next, не должен распределять для них память, создавать специальные дочерние классы и т.д.

Но это второе решение имеет свой недостаток. Размер используемых классом узлов всегда будет равен 8 байтам - по 4 байта для указателя и данных.

Обратите внимание, что в приведенных выше рассуждениях считается, что размер указателей составляет 4 байта. Можно предположить, что последующие версии Delphi будут написаны для 64-разрядных операционных систем. В таком случае длина указателей будет составлять 8 байт. Поэтому не основывайтесь на предположении, что длина указателя всегда 4 байта, пользуйтесь функцией sizeof (pointer). В будущем это существенно упростит перенос кода в новые версии Delphi. Тем не менее, в настоящей главе считается, что длина указателя составляет 4 байта, даже несмотря на то, что в коде используется sizeof (pointer). Такое допущение позволяет упростить выкладки, поскольку можно просто сказать "8 байт", а не "удвоенное значение sizeof(pointer)".

Что дает нам постоянный размер узла? При необходимости записи данных в связный список нужно предварительно распределить память под узел. Для этого пришлось бы использовать очень сложный диспетчер кучи Delphi, всего лишь, чтобы распределить 8 байт памяти. Диспетчер кучи содержит код, который может манипулировать кусками памяти, а также распределять и освобождать память любого размера. Все операции выполняются быстро и эффективно. Но мы знаем, что будут использоваться только 8-байтные блоки, и нам нужны только такие блоки. Можно ли, учитывая постоянство размеров блоков, увеличить скорость распределения памяти для новых узлов и освобождения памяти, занимаемой удаляемыми узлами? Конечно же, ответ "да". Мы с помощью диспетчера кучи одновременно распределяем память для нескольких узлов, а затем используем ее по мере необходимости. Таким образом, память распределяется не для одного узла, а, скажем, для 100 узлов. Если потребуется большее количество, будет выделен еще один блок из 100 узлов.

А вот теперь начинается самое интересное. Массивы узлов хранятся во внут-ннем связном списке, а узлы, которые берутся из этих массивов, попадают в вободный список, который также представляет собой связный список. Таким об-*м, для увеличения эффективности работы класс связного списка будет исполь-пъ массивы и собственно связные списки.

Что в предыдущем абзаце понимается под понятием "свободный список"? Это непринятая конструкция в программировании. У нас имеется набор некоторых ентов, которые "распределяются" и "освобождаются". При освобождении эле-а он, скорее всего, в какой-то момент времени будет использоваться повтор-1оэтому вместо возвращения занимаемой элементом памяти поддерживается <ный список, т.е. список свободных элементов. Диспетчер кучи Delphi использует свободный список освобожденных блоков памяти различного размера. Многие базы данных поддерживают скрытый свободный список удаленных записей, которые можно использовать повторно. Массив записей, описанный в главе 2, использует цепочку удаленных записей, которая является ни чем иным, как другим названием свободного списка. При необходимости распределения памяти под элемент приложение обращается к свободному списку и выбирает один из свобод-тх элементов.

Давайте разработаем диспетчер распределения узлов. Он будет содержать свободный список узлов, который вначале устанавливается равным nil, что означает, что список пуст. При распределении узла диспетчер будет просматривать свой свободный список. Если он пуст (равен nil), диспетчер распределяет большой блок памяти, обычно называемый страницей, при помощи диспетчера кучи Delphi. Затем станица разделяется на отдельные куски с размером, равным размеру узла, и куски записываются в свободный список. После этого узел извлекается из списка и передается пользователю. При освобождении узла он записывается в свободный список. Под "записью" здесь понимается вставка узла в начало списка, а под "извлечением" - считывание узла с начала списка.

Листинг 3.1. Класс TtdNodeManager

TtdNodeManager = class private FNodeSize : cardinal;
FFreeList : pointer;
FNodesPerPage : cardinal;
FPageHead : pointer;
FPageSize : cardinal;
protected
procedure nmAllocNewPage;
public
constructor Create(aNodeSize : cardinal);
destructor Destroy;
override;
function AllocNode : pointer;
procedure FreeNode(aNode : pointer);
end;

Как видно из приведенного кода, реализация интерфейса класса достаточно проста. Класс позволяет создавать и уничтожать экземпляры и распределять и освобождать узлы. Конструктор Create в качестве единственного входного параметра принимает размер узла, а затем на его основании вычисляет несколько значений: количество узлов на странице и размер страницы. Класс пытается распределять страницы размером 1024 байта. Но если размер узла настолько велик, что на одной такой странице может поместиться только один узел, размер страницы выбирается равным размеру узла. Для увеличения эффективности размер узла округляется до ближайшей границы 4 байт (фактически округление выполняется до ближайшего значения sizeof (pointer)).

Листинг 3.2. Конструктор TtdNodeManager .Create

constructor TtdNodeManager .Create (aNodeSize : cardinal);
begin inherited Create;
{сохранить размер узла, округленный до ближайших 4 байт) if (aNodeSize <= sizeof (pointer)) then
aNodeSize := sizeof(pointer) else
aNodeSize := ((aNodeSize + 3) shr 2) shl 2; FNodeSize := aNodeSize;
{вычислить размер страницы (no умолчанию используется 1024 байта) и количество узлов на странице; если размер страницы по умолчанию недостаточен для размещения двух или большего количества узлов, выбрать размер страницы равным размеру узла)
FNodesPerPage : = (PageSize - sizeof(pointer)) div aNodeSize;
if (FNodesPerPage > 1) then FPageSize := PageSize
else begin
FNodesPerPage := 1;
FPagesize := aNodeSize + sizeof(pointer);
ends-end;

Код метода AllocNode очень прост. Если свободный список пуст, вызывается метод nmAllocNewPage, который распределяет новую страницу и вносит все ее узлы в свободный список. Если свободный список не пуст, из него выбирается первый узел (фактически с помощью процедуры удаления первого узла).

Листинг 3.3. Распределение памяти для узла в классе TtdNodeManager

function TtdNodeManager.AllocNode : pointers-begin
{если свободный список пуст, распределить память для новой страницы; это приведет к заполнению свободного списка) if (FFreeList = nil) then
nmAllocNewPage; {вернуть первый элемент свободного списка) Result := FFreeList;
FFreeList : = PGenericNode(FFreeList)л.gnNext;
end;

Тип PGenericNode представляет собой запись с одним полем - полем для ссылки gnNext. Этот тип и преобразование типов в коде позволяет работать с узлами в списке свободных узлов на основании общего алгоритма - нечто похожее на тип TSimpleNode, который мы рассматривали ранее. Обратите внимание, конструктор гарантирует, что размер узлов, отслеживаемых диспетчером узлов, составляет, по крайней мере, 4 байта, т.е. размер указателя.

Следующий метод - FreeNode - ничуть не сложнее предыдущего. Он просто вставляет новый узел в начало свободного списка (используется код вставки перед первым узлом).

Листинг 3.4. Освобождение узла в классе TtdNodeManager

procedure TtdNodeManager. FreeNode (aNode : pointer);
begin
{вставить узел (если он не nil) в начало свободного списка) if (aNode о nil) then begin
PGenericNode(aNode)A.gnNext : = FFreeList;
FFreeList := aNode;
end;
end;

Следующий метод, заслуживающий внимания, - nmAllocNewPage. Этот метод предназначен для распределения памяти объемом FpageSize, вычисленным в конструкторе Create, для новой страницы. Каждая страница содержит указатель и узлы FNodesPerPage. Указатель используется для создания связного списка страниц (именно поэтому конструктор учитывает в своих вычислениях значение sizeof (pointer)). Находящиеся на странице узлы вставляются в свободный список с помощью простого вызова FreeNode. Поскольку переменная NewPage объявлена как PAnsiChar, при выполнении простых операций с указателем для идентификации отдельных узлов на странице преобразование указателя в тип integer не требуется.

Листинг 3.5. Распределение новой страницы в классе TtdNodeManager

procedure TtdNodeManager. nmAllocNewPage ; var
NewPage : PAnsiChar;
i : integer;
begin
{распределить новую страницу и вставить ее в начало списка страниц)
GetMem(NewPage, FPageSize);
PGenericNode(NewPage)A.gnNext : - FPageHead;
FPageHead := NewPage;
{разделить новую страницу на узлы и вставить их в началр свободного списка; обратите внимание, что первые 4 байта страницы представляют собой указатель на следующую страницу, поэтому не забудьте их пропустить) inc(NewPage, sizeof(pointer));
for i := pred(FNodesPerPage) downto 0 do begin FreeNode(NewPage);
inc(NewPage, FNodeSize);
end;
end;

И, наконец, деструктор Destroy удаляет все страницы в списке страниц. Он ничего не делает со свободным списком, поскольку все узлы в нем находятся на освобождаемых страницах и будут освобождены в любом случае.

Листинг 3.6. Удаление экземпляра класса TtdNodeManager

destructor TtdNodeManager. Destroy;
var
Temp : pointers-begin
{освободить все имеющиеся страницы} while (FPageHead <>
nil) do begin
Temp : = PGenericNode (FPageHead)74. gnNext;
FreeMem(FPageHead, FPageSize);
FPageHead := Temp;
ends-inherited De s troys-end ;

Рекомендации на будущее. Уже в недалеком будущем мы получим новую версию Windows, использующую 64-битные указатели и написанную для 64-разрядных процессоров Intel. Понятно, что подобная же участь ждет и операционную систему Linux. Вскоре после выхода в свет 64-разрядных систем на рынке появятся версии Delphi и Kylix, поддерживающие длинные указатели. Весь код в настоящей книге основан на предположении, что длина указателей может составлять и не 4 байта, или 32 бита. Для определения длины указателей используется функция sizeof (pointer). Нигде в коде мы не считаем значения sizeof (pointer) и sizeof (longint) равными - простая хитрость, которая может оказаться полезной при работе с будущими версиями Delphi. Примером описанного принципа программирования может служить диспетчер узлов.

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

Перед тем как вернуться к дальнейшим исследованиям односвязных списков, с которых мы начали наши рассуждения, отметим несколько недостатков класса TtdNodeManager. Первое, что следует отметить - это то, что метод FreeNode не проверяет, принадлежит ли освобождаемый узел к требуемому классу, т.е. находится ли он на странице, контролируемой классом. Это основной вопрос правильного функционирования класса. Если у класса есть узел, который не принадлежит к данному классу, он может иметь неверную длину (что в итоге может привести к перезаписи памяти) или может принадлежать к другому классу, который, возможно, очистит страницу, содержащую узел, и т.д. При отладке имеет смысл проводить проверку принадлежности к классу всех освобождаемых узлов. Реализация, содержащаяся в рамках сопровождающих книгу материалов, включает специальный код проверки при условии, что модель будет компилироваться с использованием утверждений.

Вторая проблема вызвана тем, что мы легко можем удалить экземпляр диспетчера узлов до удаления объектов, которые эти узлы используют. Это приведет к возникновению неизвестных ошибок. Только достаточная внимательность во время программирования может нас избавить от такого рода ошибок.

(Кстати, в качестве простого доказательства того, что мы не зря потеряли время на реализацию диспетчера узлов, можно сказать, что тесты по распределению и освобождению одного миллиона узлов показали, что диспетчер узлов работает в 3-4 раза быстрее, чем диспетчер кучи Delphi.) Класс односвязного списка

Перед тем как приступить к реализации класса 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, данные, на которые указывают ссылки каждого узла, будут находиться в разных участках памяти. Но здесь, к сожалению, мы ничего поделать не можем.

Двухсвязные списки

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

type PSimpleNode = ATSimpleNode;
TSimpleNode = record
Next : PSimpleNode;
Prior : PSimpleNode;
Data : SomeDataType;
end;

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

Двухсвязный список

Рисунок 3.4. Двухсвязный список

Вставка и удаление элементов в двухсвязном списке

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

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

var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data.. NewNodeA. Next : = GivenNode A. Next;
GivenNode A. Next : = NewNode ; NewNodeA.Prior := GivenNode;
NewNodeA.NextA.Prior : = NewNode;

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

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

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

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

var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo : = GivenNodeA. Next ; GivenNodeA.Next : = NodeToGoA.Next;
NodeToGoA.NextA.Prior : = GivenNode;
Dispose(NodeToGo);

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

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

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

Вставка: var FirstNode, NewNode : PSimpleNode; begin • • 9

New(NewNode) ;
.. задать значение поля Data.. NewNodeA. Next : = FirstNode;
NewNodeA.Prior : - nil;
FirstNodeA.Prior : = NewNode;
FirstNode := NewNode;

Удаление: var FirstNode, NodeToGo : PSimpleNode; begin • • •

NodeToGo := FirstNode;
FirstNode : = NodeToGoA.Next;
FirstNodeA.Prior : - nil;
Dispose(NodeToGo);

Соображения по поводу эффективности

Как и для односвязных списков, предварительно приведем некоторые соображения, касающиеся проблемы эффективности.

Вставка и удаление элементов в двухсвязном списке || Оглавление || Использование начального и конечного узлов


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



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

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс