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

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

Интерфейс класса TtdArrayQueue выглядит точно так же, как и интерфейс класса TtdQueue.

Листинг 3.31. Класс TtdArrayQueue

TtdArrayQueue = class private

FCount : integer;

FDispose : TtdDisposeProc;

FHead : integer;

FList : TList;

FName : TtdNameString;

FTail : integer;

protected

procedure aqError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure aqGrow;

public

constructor Create(aDispose : TtdDisposeProc;

aCapacity : integer);

destructor Destroy; override;

procedure Clear;

function Dequeue : pointer;

procedure Enqueue(altem : pointer);

function Examine : pointer;

function IsEmpty : boolean;

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

Конструктор и деструктор мало чем отличаются от соответствующих методов класса TtdArrayStack.

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

constructor TtdArrayQueue.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 TtdArrayQueue.Destroy;

begin

FList.Free;

inherited Destroy;

end;

Самое интересное происходит в методах Enqueue и Dequeue.

Листинг 3.33. Методы Enqueue и Dequeue класса TtdArrayQueue

function TtdArrayQueue.Dequeue : pointer;

begin

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

if (Count = 0) then

aqError(tdeQueueIsEmpty, 'Dequeue');

{элемент, снимаемый с очереди, находится в ее начале}

Result := FList[FHead];

{переместить индекс начала очереди и убедиться, что он все еще действителен; уменьшить количество элементов на 1}

FHead := (FHead + 1) mod FList.Count;

dec(FCount);

end;

procedure TtdArrayQueue.Enqueue(aItem : pointer);

begin

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

FList[FTail] := aItem;

{переместить индекс конца очереди и убедиться, что он все еще действителен; увеличить количество элементов на 1}

FTail := (FTail + 1) mod FList.Count;

inc(FCount);

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

if (FTail = FHead) then

aqGrow;

end;

Как видите, снятие элемента с очереди включает возврат элемента, находящегося в позиции с индексом начала очереди, а затем увеличение индекса на 1. Постановка в очередь включает запись элемента в позицию с индексом конца очереди и увеличение индекса на 1. Если конец очереди достигает ее начала, размер массива увеличивается с помощью метода aqGrow:

Листинг 3.34. Расширение размера экземпляра класса TtdArrayQueue

procedure TtdArrayQueue.aqGrow;

var

i : integer;

ToInx : integer;

begin

{увеличить размер списка}

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

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

if (FHead = 0) then

FTail := FCount else begin

ToInx := FList.Count;

for i := pred(Count) downto FHead do begin

dec(ToInx);

FList[ToInx] := FList[i];

end;

FHead := ToInx;

end;

end;

Приведенный метод является наиболее сложным методом во всем классе. При его вызове очередь заполнена, индекс конца очереди временно равен индексу начала (не забывайте, что это также означает, что очередь пуста), причем необходимо увеличить размер массива TList. Первое, что мы делаем, - увеличиваем размер массива на 50%. После этого нужно исправить кольцевую очередь таким образом, чтобы она правильно учитывала свободное место. Если значение индекса начала очереди равно 0, кольцевая очередь была не круговой, и все что требуется сделать - изменить значение индекса конца очереди. Если же значение индекса начала не равно 0, очередь была "закольцована" внутри массива. Чтобы переходить по элементам в правильном порядке, мы начинаем с индекса начала очереди, доходим до старого конца массива, переходим к началу массива и идем до индекса конца очереди (который равен индексу начала очереди). Теперь у нас имеются дополнительные элементы, которые находятся между старым и новым концом массива. Следовательно, мы должны поместить элементы, находящиеся между началом очереди и старым концом массива таким образом, чтобы они занимали место до нового конца массива. После этого мы получим правильный порядок элементов в кольцевой очереди.

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

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

После изучения стеков и очередей, основанных на связных списках и массивах, вы, наверное, задали себе вопрос: "Какой тип лучше использовать?" Тесты на контроль времени в различных версиях Delphi (16- и 32-разрядных) показали, что в большинстве случаев быстрее оказывается версия, основанная на массиве. Ее и лучше использовать. Исключением является случай, когда в Delphi1 количество элементов в стеке или очереди превышает 16000 - это максимальное значение для Delphi1. Поэтому, если в вашем стеке или очереди будет больше 16000 элементов, в Delphi1 потребуется работать со связными списками.

Поиск - это действие, заключающееся в просмотре набора элементов и выделении из этого набора интересующего элемента. Наверное, все вы знакомы с одной из функций поиска - Pos из модуля SysUtils, которая предназначена для поиска подстроки в строке.

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

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