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

Однако следует отметить, что используемое в качестве "приоритета" значение не обязательно должно быть классическим номером приоритета. Оно может иметь любой тип или значение - главное, чтобы значения были связаны отношением упорядочения, и чтобы очередь могла определить элемент с наибольшим значением. {Отношение упорядочения набора объектов - это правило, которое позволяет упорядочить объекты так, чтобы объект X был "меньше" объекта Y. Если X меньше Y, то Y не может быть меньше х. Кроме того, если X меньше Y, и Y меньше Z, то X меньше Z. Обычное упорядочение целых чисел, когда 2 меньше 3 и т.д., представляет собой пример отношения упорядочения.}

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

Итак, очередь по приоритету должна обеспечивать (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);