Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Листинг 3.16. Установка курсора на узел с индексом n для класса TtdDoubleLinkList
procedure TtdDoubleLinkList.dllPositionAtNth(aIndex : longint);
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{проверить, корректно ли задан индекс}
if (aIndex < 0) or (aIndex >= Count) then
dllError(tdeListInvalidIndex, 'dllPositionAtNth');
{для увеличения быстродействия используются локальные переменные}
WorkCursor := FCursor;
WorkCursorIx := FCursorIx;
{обработать наиболее простой случай}
if (aIndex = WorkCursorIx) then
Exit;
{заданный индекс либо перед курсором, либо после него; в любом случае, заданный индекс ближе либо к курсору, либо к соответствующему концу списка; определить самый короткий путь}
if (aIndex < WorkCursorIx) then begin
if ((aIndex - 0) < (WorkCursorIx - aIndex)) then begin
{начать с начального узла и двигаться вперед до индекса aIndex}
WorkCursor := FHead;
WorkCursorIx := -1;
end;
end
else {aIndex > FCursorIx}
begin
if ((aIndex - WorkCursorIx) < (Count - aIndex)) then begin
{начать с конечного узла и двигаться назад до индекса aIndex}
WorkCursor :=FTail;
WorkCursorIx := Count;
end;
end;
{пока индекс рабочего курсора меньше заданного индекса, перемещать рабочий курсор на одну позицию вперед}
while (WorkCursorIx < aIndex) do
begin
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{пока индекс рабочего курсора больше заданного индекса, перемещать рабочий курсор на одну позицию назад}
while (WorkCursorIx > aIndex) do
begin
WorkCursor := WorkCursor^.dlnPrior;
dec(WorkCursorIx);
end;
{установить реальный курсор равным рабочему курсору}
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
end;
Теперь, когда мы умеем находить узел по заданному индексу, можно перейти к реализации остальных методов: все они очень похожи на соответствующие методы для односвязных списков.
Листинг 3.17. Методы класса TtdDoubleLinkList, основанные на использовании индекса
function TtdDoubleLinkList.Add(aItem : pointer): longint;
begin
{перейти к концу связного списка}
FCursor := FTail.FCursorIx := Count;
{вернуть индекс нового узла}
Result Count;
{вставить элемент в позицию курсора}
InsertAtCursor(aItem);
end;
procedure TtdDoubleLinkList.Delete(aIndex : longint);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{удалить элемент в позиции курсора}
DeleteAtCursor;
end;
function TtdDoubleLinkList.dllGetItem(aIndex : longint): pointer;
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
procedure TtdDoubleLinkList.dllSetItem(aIndex : longint;
aItem : pointer);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{если возможно удалить заменяемые данные, удалить их}
if Assigned(FDispose) and (aItem <> FCursor^.dlnData) then
FDispose(FCursor^.dlnData);
{заменить данные}
FCursor^.dlnData := aItem;
end;
function TtdDoubleLinkList.First : pointer;
begin
{установить курсор на первый узел}
dllPositionAtNth(0);
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
function TtdDoubleLinkList.IndexOf(aItem : pointer): longint;
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{установить рабочий курсор на первый узел (если он существует)}
WorkCursor := FHead^.dlnNext;
WorkCursorIx := 0;
{идти по списку в поисках требуемого элемента}
while (WorkCursor <> FTail) do
begin
if (WorkCursor^.dlnData = aItem) then begin
{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора}
Result := WorkCursorIx;
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
Exit;
end;
{перейти к следующему узлу}
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{требуемый элемент не найден}
Result := -1;
end;
procedure TtdDoubleLinkList.Insert(aIndex : longint;
aItem : pointer);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{вставить элемент в позицию курсора}
InsertAtCursor(aItem);
end.-function TtdDoubleLinkList.Last : pointer;
begin
{установить курсор на последний узел}
dllPositionAtNth(pred(Count));
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
procedure TtdDoubleLinkList.Remove(aItem : pointer);
begin
if (IndexOf (aItem) <> -1) then
DeleteAtCursor;
end;
Полный код класса TtdDoubleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.
Достоинства и недостатки связных списков
Связные списки обладают одним очень важным преимуществом: для них операции вставки и удаления принадлежат к классу O(1). Независимо от текущего элемента спуска и его емкости, для вставки или удаления элемента всегда требуется одно и то же время.
Основным недостатком связных списков является то, что получение доступа к их элементам принадлежит к классу О(n). В этом случае важно количество элементов в списке: при поиске n-ного элемента мы начинаем с некоторой позиции в списке и переходим по ссылкам вплоть до искомого элемента. Чем больше элементов в списке, тем больше переходов придется совершить. Для увеличения быстродействия в реализации классов списков мы воспользовались небольшими хитростями, но, тем не менее, операция все равно принадлежит к классу O(n).
По сравнению с классом TList связные списки требуют большего объема памяти. В качестве ссылки на элемент в TList используется один указатель, т.е. в массиве TList для каждого элемента требуется, по крайней мере, sizeof(pointer) байт. С другой стороны, односвязный список содержит два указателя: указатель на данные и указатель на следующий элемент. Таким образом, для каждого элемента в односвязном списке нужно, по меньшей мере, 2*sizeof(pointer) байт.
Очевидно, что для каждого элемента в двухсвязном списке требуется не менее 3*sizeof(pointer) байт.
Но это еще не все. Если неэффективно использовать массив TList (другими словами, не использовать свойство Capacity для установки размера массива), будут распределяться несколько блоков памяти, каждый из которых больше предыдущего, и потребуется больший объем работ, связанный с копированием данных массива. Если элементы вставляются только в начало, быстродействие массива TList существенно уменьшается. В настоящей книге будут приведены несколько реализаций алгоритмов и структур данных, которые позволяют достичь для связных списков гораздо большей эффективности, нежели это показывает TList, однако в общем случае массив TList лучше, быстрее и эффективнее связных списков.
Стеки
Еще одной известной и широко используемой структурой данных является стек. Стек представляет собой структуру, которая позволяет выполнять две основных операции: заталкивание для вставки элемента в стек и выталкивание с целью считывания данных из стека. Структура устроена таким образом, что операция выталкивания всегда возвращает элемент, вставленный в стек последним (самый "новый" элемент в стеке). Другими словами, элементы в стеке считываются в порядке, обратном порядку их записи в стек. Благодаря такому устройству стек известен как контейнер магазинного типа.
Рисунок 3.7. Операции заталкивания и выталкивания для стека
Написание кода стека не представляет никаких трудностей. Причем существуют два варианта реализации: первый - на основе односвязного списка, второй -на основе массива. Как и в случае со списками, будем считать, что записываться и считываться из стека будут указатели на элементы. Сначала рассмотрим организацию стека на базе связного списка.
Стеки на основе односвязных списков
В реализации стеков на основе односвязных списков операция заталкивания представляет собой вставку элемента в начало списка, а операция выталкивания - удаление элемента из начала списка и считывание его данных. Обе операции не зависят от количества элементов в списке, следовательно, их можно отнести к классу O(1). Вот и все, что касается организации стека.
Конечно, реализация описанной организации требует большего объема в плане принятия решений. Класс стека можно реализовать как дочерний класса односвязного списка или делегировать операции заталкивания и выталкивания внутреннему экземпляру класса связного списка. Первый вариант не особенно эффективен: мы придем к реализации класса с методами Push и Pop, но при этом у нас останутся и другие методы связного списка (Insert, Delete и т.д.). Понятно, что это не самое лучшее решение.
Второй вариант реализации, делегирование, - чисто в духе Delphi. Класс стека можно организовать именно таким образом. Конструктор Create будет создавать новый экземпляр класса TtdSingleLinkList и устанавливать курсор после начального узла, деструктор Destroy будет уничтожать созданный конструктором экземпляр. Метод Push будет пользоваться экземпляром класса для вставки элемента в позицию курсора, а метод Pop будет удалять элемент в позиции курсора, предварительно сохранив его значение. Вполне реализуемое решение.
Тем не менее, мы будем писать класс TtdStack, исходя из первых принципов. TtdStack - простой класс, и за счет этого мы попытаемся увеличить его быстродействие и эффективность.
Листинг 3.18. Класс TtdStack
TtdStack = class private
FCount : longint;
FDispose : TtdDisposeProc;
