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

Первая простая реализация

Первая простая реализация

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

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

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

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

Листинг 9.1. Простая очередь по приоритету, построенная на основе структуры TList type

TtdSimplePriQueuel = class private

FCompare : TtdCompareFunc;

FList : TList;

protected

function pqGetCount : integer;

public

constructor Create(aCompare : TtdCompareFunc);

destructor Destroy; override;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

property Count : integer read pqGetCount;

end;

constructor TtdSimplePriQueuel.Create(aCompare : TdCompareFunc);

begin

inherited Create;

FCompare := aCompare;

FList := TList.Create;

end;

destructor TtdSimplePriQueuel.Destroy;

begin

FList.Free;

inherited Destroy;

end;

function TtdSimplePriQueuel.Dequeue : pointer;

var

Inx : integer;

PQCount : integer;

MaxInx : integer;

MaxItem : pointer;

begin

PQCount := Count;

if (PQCount = 0) then

Result := nil else

if (PQCount = 1) then begin

Result := FList.List^[0];

FList.Clear;

end

else begin

MaxItem := FList.List^ [0];

MaxInx := 0;

for Inx := 1 to pred(PQCount) do

if (FCompare (FList.List^ [Inx], MaxItem) > 0) then begin

MaxItem := FList.List^[Inx];

MaxInx := Inx;

end;

Result := MaxItem;

FList.List^[MaxInx] := FList.Last;

FList.Count := FList.Count - 1;

end;

end;

procedure TtdSimplePriQueuel.Enqueue(aItem : pointer);

begin

FList.Add(aItem);

end;

function TtdSimplePriQueuel.pqGetCount : integer;

begin

Result := FList.Count;

end;

Из листинга 9.1 видно, что в действительности этот класс является достаточно простым, и даже добавление в него отсутствовавшей ранее проверки на наличие ошибок не делает его громоздким. Единственный фрагмент кода, который представляет интерес - код удаления элемента: мы не вызываем метод Delete структуры данных TList (операция типа O(n)) а просто заменяем элемент, который нужно удалить, последним элементом и уменьшаем на единицу значение счетчика элементов (операция типа O(1)).

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

После того, как мы убедились в простоте разработки создания этой очереди по приоритету, рассмотрим ее эффективность. Во-первых, добавление элемента в очередь по приоритету будет требовать постоянного времени. Иначе говоря, эта операция является операцией типа O(1). Независимо от того, содержит ли очередь ноль или тысячи элементов, добавление нового элемента будет занимать приблизительно одно и то же время: мы всего лишь дописываем его в конец списка.

Теперь рассмотрим противоположную операцию: удаление элемента. В этом случае для отыскания элемента с наивысшим приоритетом потребуется выполнить считывание всех элементов в структуре TList. Этот поиск является последовательным и, как было показано в главе 4, эта операция является операцией типа O(n). Требуемое для этого время пропорционально количеству элементов в очереди.

Таким образом, мы разработали и создали структуру данных, реализующую очередь по приоритету, в которой добавление элемента является операцией типа O(1), а удаление - операцией типа O(n). При наличии небольшого количества элементов эта структура оказывается вполне приемлемой и достаточно эффективной.

Оглавление книги