Листинг 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.

С другой стороны, если был выполнен переход в состояние С, считывание символов продолжается в этом состоянии до тех пор, пока не произойдет одно из двух: либо не будет выполнено считывание символа двойной кавычки, в результате чего произойдет переход в состояние В, либо не будет выполнено считывание символа, который не является ни двойной кавычкой, ни пробелом, ни знаком препинания, в результате чего будет осуществлен переход в состояние A.

Рисунок 10.1. Конечный автомат извлечения слов из строки

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