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

Например, значением приоритета могло бы быть имя (иначе говоря, строка), а упорядочением мог бы быть стандартный алфавитный порядок. Таким образом, вместо операции извлечения элемента с наибольшим приоритетом можно было бы использовать извлечение элемента, располагающегося раньше в алфавитном порядке (т.е. все А располагаются перед всеми В и т.д.).

Итак, очередь по приоритету должна обеспечивать (1) хранение произвольного количества элементов, (2) добавление в очередь элемента с определенным приоритетом и (3) выявление и удаление элемента с наивысшим приоритетом.

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

При разработке очереди по приоритету первый атрибут (возможность хранения произвольного количества элементов) наталкивает на мысль об использовании какой-либо расширяемой структуры данных типа связного списка или расширяемого массива, такого как 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.