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

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;

FHead : PslNode;

FName : TtdNameString;

protected

procedure sError(aErrorCode : integer;

const aMethodName : TtdNameString);

class procedure sGetNodeManager;

public

constructor Create(aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Clear;

function Examine : pointer;

function IsEmpty : boolean;

function Pop : pointer;

procedure Push(aItem : pointer);

property Count : longint read FCount;

property Name : TtdNameString read FName write FName;

end;

Метод Examine возвращает первый элемент стека, не выталкивая его из стека. Он бывает очень удобным в использовании, поскольку не требует выталкивания элемента с последующим заталкиванием. Метод IsEmpty возвращает значение true, если стек пуст, что эквивалентно проверке равенства нулю свойства Count.