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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 8 (всего у книги 36 страниц)

type

PSimpleNode = ^TSimpleNode;

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 ..

NewNode^.Next := GivenNode^.Next;

GivenNode^.Next := NewNode;

NewNode^.Prior := GivenNode;

NewNode^.Next^.Prior := NewNode;

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

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

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

var

GivenNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := GivenNode^.Next;

GivenNode^.Next := NodeToGo^.Next;

NodeToGo^.Next^.Prior := GivenNode;

Dispose(NodeToGo);

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

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

Вставка:

var

FirstNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data..

NewNode^.Next := FirstNode;

NewNode^.Prior := nil;

FirstNode^.Prior := NewNode;

FirstNode := NewNode;

Удаление:

var

FirstNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := FirstNode;

FirstNode := NodeToGo^.Next;

FirstNode^.Prior := nil;

Dispose(NodeToGo);

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

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

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

Как и для односвязного списка, данные в списке удобно хранить в виде указателей. Это позволяет написать общий класс двухсвязного списка. В двухсвязном списке в каждом узле будет находиться прямой указатель, обратный указатель и указатель на данные. Общий размер узла составит 12 байт (т.е. 3*sizeof(pointer)). Все узлы одинаковы, таким образом, можно реализовать диспетчер узлов и для двухсвязного списка.

Класс двухсвязного списка

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

Листинг 3.13. Класс TtdDoubleLinkList

TtdDoubleLinkList = class private

FCount : longint;

FCursor : PdlNode;

FCursorIx: longint;

FDispose : TtdDisposeProc;

FHead : PdlNode;

FName : TtdNameString;

FTail : PdlNode;

protected

function dllGetItem(aIndex : longint): pointer;

procedure dllSetItem(aIndex : longint; aItem : pointer);

procedure dllError(aErrorCode : integer;

const aMethodName : TtdNameString);

class procedure dllGetNodeManager;

procedure dllPositionAtNth(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 MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

procedure Sort(aCompare : TtdCompareFunc);

property Count : longint read FCount;

property Items[aIndex : longint] : pointer

read dllGetItem write dllSetItem; default;

property Name : TtdNameString read FName write FName;

end;

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

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

Конструктор Create распределяет при помощи диспетчера узлов еще один дополнительный фиктивный узел – FTail. Как упоминалось во введении к двухсвязным спискам, он предназначен для обозначения конца списка. Начальный и конечный фиктивные узлы вначале будут связаны друг с другом, т.е. ссылка Next начального узла указывает на конечный узел, а ссылка Prior конечного узла – на начальный узел. Естественно, деструктор Destroy будет удалять фиктивный конечный узел и возвращать его вместе с начальным узлов в диспетчер узлов.

Листинг 3.14. Конструктор Create и деструктор Destroy класса TtdDoubleLinkList

constructor TtdDoubleLinkList.Create;

begin

inherited Create;

{сохранить процедуру удаления}

FDispose :=aDispose;

{получить диспетчер узлов}

dllGetNodeManager;

{распределить и связать начальный и конечный узлы}

FHead := PdlNode (DLNodeManager.AllocNode);

FTail := PdlNode (DLNodeManager.AllocNode);

FHead^.dlnNext := FTail;

FHead^.dlnPrior :=nil;

FHead^.dlnData := nil;

FTail^.dlnNext := nil;

FTail^.dlnPrior := FHead;

FTail^.dlnData := nil;

{установить курсор на начальный узел}

FCursor := FHead;

FCursorIx := -1;

end;

destructor TtdDoiibleLinkList.Destroy;

begin

if (Count <> 0) then

Clear;

DLNodeManager.FreeNode (FHead);

DLNodeManager.FreeNode(FTail);

inherited Destroy;

end;

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

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

procedure TtdDoubleLinkList.Clear;

var

Temp : PdlNode;

begin

{удалить все узлы, за исключением начального и конечного; если возможно их освободить, то сделать это}

Temp := FHead^.dlnNext;

while (Temp <> FTail) do

begin

FHead^.dlnNext := Temp^.dlnNext;

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

DLNodeManager.FreeNode(Temp);

Temp := FHead^.dlnNext;

end;

{устранить "дыру" в связном списке}

FTail^.dlnPrior := FHead;

FCount := 0;

{установить курсор на начальный узел}

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.DeleteAtCursor;

var

Temp : PdlNode;

begin

{записать в Temp удаляемый узел}

Temp := FCursor;

if (Temp = FHead) or (Temp = FTail) then

dllError(tdeListCannotDelete, 'Delete');

{избавиться от его содержимого}

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

{удалить ссылки на узел и освободить его; курсор перемещается на следующий узел}

Temp^.dlnPrior^.dlnNext := Temp^.dlnNext;

Temp^.dlnNext^.dlnPrior := Temp^.dlnPrior;

FCursor := Temp^.dlnNext;

DLNodeManager.FreeNode(Temp);

dec(FCount);

end;

function TtdDoubleLinkList.Examine : pointer;

begin

if (FCurgor = nil) or (FCursor = FHead) then

dllError(tdeListCannotExamine, 'Examine');

{вернуть данные узла в позиции курсора}

Result := FCursor^.dlnData;

end;

procedure TtdDoubleLinkList.InsertAtCursor(aItem : pointer);

var

NewNode : PdlNode;

begin

{если курсор находится на начальном узле, не генерировать исключение, а перейти на следующий узел}

if (FCursor = FHead) then

MoveNext;

{распределить новый узел и вставить его перед позицией курсора}

NewNode := PdlNode (DLNodeManager.AllocNode);

NewNode^.dlnData := aItem;

NewNode^.dlnNext := FCursor;

NewNode^.dlnPrior := FCursor^.dlnPrior;

NewNode^.dlnPrior^.dlnNext := NewNode;

FCursor^.dlnPrior := NewNode;

FCursor := NewNode;

inc(FCount);

end;

function TtdDoubleLinkList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdDoubleLinkList.IsBeforeFirst;

boolean;

begin

Result := FCursor = FHead;

end;

function TtdDoubleLinkList.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

procedure TtdDoubleLinkList.MoveAfterLast;

begin

{установить курсор на конечный узел}

FCursor := FTail;

FCursorIx := Count;

end;

procedure TtdDoubleLinkList.MoveBeforeFirst;

begin

{установить курсор на начальный узел}

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.MoveNext;

begin

{переместить курсор по его прямому указателю}

if (FCursor <> FTail) then begin

FCursor := FCursor^.dlnNext;

inc(FCursorIx);

end;

end;

procedure TtdDoubleLinkList.MovePrior;

begin

{переместить курсор по его обратному указателю}

if (FCursor <> FHead) then begin

FCursor := FCursor^.dlnPrior;

dec(FCursorIx);

end;

end;

Если сравнить приведенный код с его эквивалентом для односвязных списков (листинг 3.9), можно понять, каким образом дополнительные обратные связи влияют на реализацию методов. С одной стороны, методы стали немного проще. Так, например, в случае двухсвязных списков для метода MoveNext не нужно вводить переменную FParent. С другой стороны, требуется дополнительный код для обработки обратных ссылок. Примером могут служить методы InsertAtCursor и DeleteAtCursor.

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

Листинг 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;

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.

Листинг 3.19. Методы Examine и Is Empty для класса TtdStack

function TtdStack.Examine : pointer;

begin

if (Count = 0) then

sError(tdeStackIsEmpty, 'Examine');

Result := FHead^.slnNext^.slnData;

end;

function TtdStack.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

Конструктор Create работает аналогично конструктору класса односвязного списка. Он проверяет, существует ли диспетчер узлов, а затем с помощью диспетчера распределяет фиктивный начальный узел, который, естественно, ни на что не указывает. Деструктор Destroy очищает стек и освобождает фиктивный начальный узел, FHead, возвращая его диспетчеру узлов.

Листинг 3.20. Конструктор и деструктор класса TtdStack

constructor TtdStack.Create(aDispose : TtdDisposeProc);

begin

inherited Create;

{сохранить процедуру удаления}

FDispose := aDispose;

{получить диспетчер узлов}

sGetNodeManager;

{распределить начальный узел}

FHead := PslNode (SLNodeManager.AllocNode);

FHead^.slnNext := nil;

FHead^.slnData := nil;

end;

destructor TtdStack.Destroy;

begin

{удалить все оставшиеся узлы; очистить начальный фиктивный узел}

if (Count <> 0) then

Clear;

SLNodeManager.FreeNode(FHead);

inherited Destroy;

end;

Заталкивание элемента в стек и выталкивание его из стека представляют собой короткие процедуры. Push распределяет новый узел при помощи диспетчера узлов и вставляет его после фиктивного начального узла. Метод Pop перед удалением связей узла с фиктивным узлом с помощью алгоритма «удалить после» проверяет, существует ли в стеке хотя бы один узел. Затем он возвращает элемент и освобождает узел, возвращая его диспетчеру узлов.

Листинг 3.21. Методы Push и Pop класса TtdStack

procedure TtdStack.Push(aItem : pointer);

var

Temp : PslNode;

begin

{распределить новый узел и поместить его в начало стека}

Temp := PslNode(SLNodeManager.AllocNode);

Temp^.slnData := aItem;

Temp^.slnNext := FHead^.slnNext;

FHead^.slnNext := Temp;

inc(FCount);

end;

function TtdStack.Pop : pointer;

var

Temp : PslNode;

begin

if (Count = 0) then

sError(tdeStackIsEmpty, 'Pop');

{обратите внимание, что даже если это возможно, мы не удаляем данные узла; этот метод должен возвращать данные}

Temp := FHead^.slnNext;

Result := Temp^.slnData;

FHead^.slnNext := Temp^.slnNext;

SLNodeManager.FreeNode(Temp);

dec(FCount);

end;

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

Стеки на основе массивов

После написания класса стека, основанного на связном списке, давайте перейдем к исследованию стеков, реализованных на базе массивов. Причина для организации такого класса заключается в том, что во многих случаях реализация стека на одном из простых типов (например, char или double) гораздо проще в случае применения массивов.

Ради простоты, в качестве базового массива возьмем класс TList. Другими словами, мы создадим класс стека указателей. В предыдущей версии стека операция Push вставляла узел в начало списка, а операция Pop выбирала узел из начала списка. Это не самый эффективный метод работы с массивами. Вставка в начало списка принадлежит к классу операций О(n), а нам желательно разработать операцию класса O(1), как в ситуации со связными списками, Поэтому при заталкивании и выталкивании элемента мы будем вставлять и удалять элемент в конце списка.

Рисунок 3.8.

Использование массива для организации стека

Рассмотрим интерфейс класса TtdArrayStack. Как видите, его раздел public полностью соответствует разделу public класса TtdStack.

Листинг 3.22. Класс TtdArrayStack

TtdArrayStack = class private

FCount : longint;

FDispose : TtdDisposeProc;

FList : TList;

FName : TtdNameString;

protected

procedure asError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure asGrow;

public

constructor Create(aDispose : TtdDisposeProc;

aCapacity : integer);

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;

Конструктор и деструктор, соответственно, создает и удаляет экземпляр класса TList. Конструктор в качестве входного параметра принимает емкость стека. Это только начальное значение для количества элементов в экземпляре массива, предназначенное только для повышения эффективности класса, а не для установки каких-либо ограничений.

Листинг 3.23. Конструктор и деструктор класса TtdArrayStack

constructor TtdArrayStack.Create(aDispose : TtdDisposeProc;

aCapacity : integer);

begin

inherited Create;

{сохранить процедуру удаления}

FDispose := aDispose;

{создать внутренний экземпляр класса TList и установить его емкость равной aCapacity}

FList := TList.Create;

if (aCapacity <= 1) then

aCapacity 16;

FList.Count := aCapacity;

end;

destructor TtdArrayStack.Destroy;

begin

FList.Free;

inherited Destroy;

end;

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

Листинг 3.24. Методы Push и Pop класса TtdArrayStack

procedure TtdArrayStack.asGrow;

begin

FList.Count := (FList.Count * 3) div 2;

end;

function TtdArrayStack.Pop : pointer;

begin

{убедиться, что стек не пуст}

if (Count = 0) then

asError(tdeStackIsEmpty, 'Pop');

{уменьшить значение счетчика на единицу}

dec(FCount);

{выталкиваемый элемент находиться в конце списка}

Result := FList[FCount];

end;

procedure TtdArrayStack.Push(aItem : pointer);

begin

{проверить, полон ли стек; если стек полон, увеличить емкость списка}

if (FCount = FList.Count) then

asGrow;

{добавить элемент в конец стека}

FList[FCount] := aItem;

{увеличить значение счетчика на единицу}

inc(FCount);

end;

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

Пример использования стека

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

Интересной вариацией этой темы является преобразование целого значения в строку. В языке Object Pascal имеются функции str и intToStr, которые позволяют решать поставленную задачу далеко не с нуля, но, тем не менее, задача остается достаточно интересной.

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

Внутри функции нужно будет вычислять цифры, соответствующие целочисленному значению. Простейший метод таких вычислений – вычислить остаток от деления значения на 10 (это будут числа от 0 до 9 включительно), сохранить его где-нибудь, поделить значение на 10 (чтобы избавиться от только что вычисленного нами значения) и повторить процесс. Цикл вычислений продолжается до тех пор, пока не будет получено значение 0.

Давайте применим описанный алгоритм (да-да, это алгоритм!) к числу 123. Остаток от деления 123 на 10 равен 3. Записываем остаток. Делим 123 на 10. Получаем 12. Остаток от деления 12 на 10 равен 2. Записываем остаток. Делим 12 на 10. Получаем 1. Остаток от деления 1 на 10 равен 1. Записываем остаток. Делим 1 на 10. Получаем 0. Завершаем вычисления. Цифры были вычислены в следующем порядке: 3, 2, 1. Однако в строке они должны находиться в обратном порядке. Мы не можем записывать цифры в строку по мере их вычисления (какой длины должна быть строка?).

Можно предложить заталкивать цифры в стек по мере их вычисления, а после выполнения вычислений определить количество элементов в стеке (т.е. длину строки) и постепенно выталкивать их в строку. Соответствующий код приведен в листинге 3.25.