Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Листинг 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.