Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Листинг 9.11. Исключение из очереди и просачивание в расширенной очереди по приоритету
procedure TtdPriorityQueueEx.pqTrickleDown(aHandle : TtdPQHandle);
var
FromInx : integer;
MaxInx : integer;
ChildInx : integer;
ChildHandle : PpqexNode;
Handle : PpqexNode absolute aHandle;
begin
{если анализируемый элемент меньше одного из своих дочерних элементов, его нужно поменять местами с большим дочерним элементом и продолжить процесс из новой позиции}
FromInx := Handle^.peInx;
MaxInx := pred(FList.Count);
{вычислить индекс левого дочернего узла}
ChildInx := succ(FromInx * 2);
{если имеется по меньшей мере правый дочерний элемент, необходимо вычислить индекс большего дочернего элемента...}
while (ChildInx <= MaxInx) do
begin
{если есть хоть один правый дочерний узел, вычислить индекс наибольшего дочернего узла}
if ((ChildInx+1) <= MaxInx) and
(FCompare(PpqexNode(FList.List^[ChildInx])^.peItem, PpqexNode(FList.List^[ChildInx+ 1])^.peItem) < 0) then
inc(ChildInx);
{если элемент больше или равен большему дочернему элементу, задача выполнена}
ChildHandle := PpqexNode(FList.List^[ChildInx]);
if (FCompare (Handle^.peItem, ChildHandle^.peItem) >= 0) then
Break;
{в противном случае больший дочерний элемент нужно переместить вверх по дереву, а сам элемент - вниз}
FList.List^[FromInx] ChildHandle;
ChildHandle^.peInx := FromInx;
FromInx := ChildInx;
ChildInx := succ(FromInx * 2);
end;
{сохранить элемент в правильной позиции}
FList.List^[FromInx] := Handle;
Handle^.peInx := FromInx;
end;
function TtdPriorityQueueEx.Dequeue : pointer;
var
Handle : PpqexNode;
begin
{проверить наличие элементов, которые нужно исключить из очереди}
if (FList.Count = 0) then
pqError(tdeQueueIsEmpty, 'Dequeue');
{вернуть корневой элемент, удалить его из списка дескрипторов}
Handle := FList.List^[0];
Result := Handle^.peItem;
DeleteLinkedListNode(FHandles, Handle);
{если очередь содержала только один элемент, теперь она пуста}
if (FList.Count = 1) then
FList.Count := 0
{если она содержала два элемента, нужно просто заменить корневой элемент одним из оставшихся дочерних элементов. Очевидно, что при этом свойство пирамидальности сохраняется}
else
if (FList.Count = 2) then begin
Handle := FList.List^[1];
FList.List^[0] := Handle;
FList.Count := 1;
Handle^.peInx := 0;
end
{в противном случае свойство пирамидальности требует восстановления}
else begin
{заменить корневой узел дочерним узлом, расположенным в самой нижней, крайней справа позиции, и уменьшить размер списка; затем за счет применения метода просачивания переместить корневой узел как можно дальше вниз по дереву}
Handle := FList.Last;
FList.List^[0] := Handler-Handle^.peInx := 0;
FList.Count := FList.Count - 1;
pqTrickleDown(Handle);
end;
end;
После ознакомления с операциями постановки в очередь и исключения из нее можно рассмотреть новые операции: удаление и изменение приоритета. Метод ChangePriotity крайне прост. Прежде чем метод будет вызван, класс предполагает, что приоритет элемента был изменен. Вначале метод проверяет, имеет ли элемент родительский элемент, и если да, то больше ли элемент с новым приоритетом своего родительского элемента. Если это так, то элемент перемещается вверх за счет применения метода пузырькового подъема. Если операция пузырькового подъема невозможна или не требуется, метод проверяет возможность выполнения операции просачивания.
Листинг 9.12. Восстановление свойства пирамидальности после изменения приоритета
procedure TtdPriorityQueueEx.ChangePriority(aHandle : TtdPQHandle);
var
Handle : PpqexNode absolute aHandle;
ParentInx : integer;
ParentHandle : PpqexNode;
begin
{проверить возможность выполнения операции пузырькового подъема}
if (Handle^.peInx > 0) then begin
ParentInx := (Handle^.peInx - 1) div 2;
ParentHandle := PpqexNode(FList[ParentInx]);
if (FCompare( Handle^.peItem, Parent Handle^.peItem) > 0) then begin
pqBubbleUp(Handle);
Exit;
end;
end;
{в противном случае выполнить операцию просачивания}
pqTrickleDown(Handle);
end;
Последняя операция реализуется при помощи метода Remove. В данном случае мы возвращаем элемент, определенный дескриптором, а затем заменяем его последним элементом сортирующего дерева. Дескриптор удаляется из связного списка. Эта операция упрощается благодаря использованию двусвязного списка. Затем значение счетчика элементов в сортирующем дереве уменьшается на единицу. С этого момента процесс полностью совпадает с процессом изменения приоритета, поэтому мы просто вызываем соответствующий метод.
Листинг 9.13. Удаление элемента, заданного его дескриптором
function TtdPriorityQueueEx.Remove(aHandle : TtdPQHandle): pointer;
var
Handle : PpqexNode absolute aHandle;
NewHandle : PpqexNode;
HeapInx : integer;
begin
{вернуть элемент, а затем удалить дескриптор}
Result := Handle^.peItem;
HeapInx := Handle^.peInx;
DeleteLinkedListNode(FHandles, Handle);
{выполнить проверку того, что был удален последний элемент. Если это так, нужно просто уменьшить размер сортирующего дерева - при этом свойство пирамидальности будет сохранено}
if (HeapInx = pred(FList.Count)) then
FList.Count := FList.Count - 1
else begin
{заменить элемент сортирующего дерева дочерним элементом, расположенным в самой нижней крайней справа позиции, и уменьшить размер списка}
NewHandle := FList.Last;
FList.List^[HeapInx] := NewHandle;
NewHandle^.peInx := HeapInx;
FList.Count := FList.Count - 1;
{дальнейшие действия совпадают с выполнением операции изменения приоритета}
ChangePriority(NewHandle);
end;
end;
Полный код этого класса можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.
Резюме
В этой главе мы уделили основное внимание очередям по приоритету - очередям, которые возвращают не самый первый помещенный в них элемент, а элемент с наивысшим приоритетом. Исследовав несколько простых реализаций, мы ознакомились с реализацией, предполагающей использование сортирующего дерева. Мы рассмотрели базовые свойства и операции сортирующего дерева и научились применять их в как в качестве алгоритма пирамидальной сортировки, так и для удовлетворения первоначального требования, предъявляемого к очереди по приоритету.
И, наконец, мы расширили определение очереди по приоритету для обеспечения выполнения ряда дополнительных операций: удаления произвольного элемента и изменения приоритета данного элемента. Мы выяснили, какие изменения нужно внести в реализацию с целью поддержки этих операций.
Глава 10. Конечные автоматы и регулярные выражения.
Существует целый класс проблем, которые могут быть решены с помощью авторучки и бумаги. По-моему, это замечательный аспект программирования: иметь возможность графически представить какой-либо процесс, а затем закодировать его. Я имею в виду алгоритмы, в которых используются конечные автоматы.
Конечные автоматы
В отличие от большинства рассмотренных в этой книге алгоритмов, конечные автоматы - это технологии, призванные облегчать разработку других алгоритмов. Они служат средством достижения конечной цели - реализации алгоритма. Тем не менее, как будет показано, они обладают рядом интересных особенностей. В основном мы будем рассматривать конечные автоматы, которые реализуют алгоритмы синтаксического анализа (parsing algorithm). Синтаксический анализ означает считывание строки (или текстового файла) и разбиение последовательностей символов на отдельные лексемы. Конечный автомат, который выполняет синтаксический анализ, обычно называют синтаксическим анализатором (parser).
Использование конечного автомата: синтаксический анализ
Чтобы лучше понять весь процесс, рассмотрим пример. Предположим, что требуется разработать алгоритм, который должен извлекать отдельные слова из строки текста. Извлекаемые слова будут помещаться в список строк. Более того, желательно, чтобы внутри строки текст, заключенный в кавычки, воспринимался как одно слово. Т.е., если имеется строка:
Не said, "State machines?"
процедура должна игнорировать знаки препинания и пробелы и возвращать следующее:
Не
said
"State machines?"
Обратите внимание, что пробел и вопросительный знак внутри заключенного в кавычки текста остались без изменений.
Простейший способ реализации этого конкретного алгоритма - использование конечного автомата. Конечный автомат (state machine) - это система (обычно цифровая), которая переходит из одного состояния в другое в соответствии с принимаемыми ею входными данными (сигналами). Смена состояний называется переходом (trAnsition). Конечный автомат можно представить специальной блок-схемой. Блок схема рассматриваемого алгоритма показана на рис. 10.1.
Показанный на рисунке конечный автомат имеет три состояния: А, В и С. Работа блок-схемы начинается с состояния A. В этом состоянии выполняется считывание символа из входной строки. Если этот символ - двойная кавычка, осуществляется переход в состояние В. Если символ является пробелом или знаком препинания, выполняется переход в состояние С. Если это любой другой символ, конечный автомат остается в состоянии А (это показано петлей).
После перехода в состояние В считывание символов продолжается в нем до тех пор, пока не будет считан символ закрывающей двойной кавычки. В этот момент происходит переход обратно в состояние A.
