52704.fb2 Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 182

Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 182

FList.List^[FTail] := pointer(aValue);

inc(FTail);

if (FTail = FList.Count) then

FTail := 0;

if (FTail = FHead) then

idGrow;

end;

procedure TtdIntDeque.idGrow;

var

OldCount : integer;

i, j : integer;

begin

{увеличить размер списка на 50%}

OldCount := FList.Count;

FList.Count := (OldCount * 3) div 2;

{распределить данные по увеличенной области, поддерживая при этом очередь с двусторонним доступом}

if (FHead= 0) then

FTail := OldCount else begin

j := FList.Count;

for i := pred(OldCount) downto FHead do

begin

dec(j);

FList.List^[j] := FList.List^[i] end;

FHead := j;

end;

end;

function TtdIntDeque.IsEmpty : boolean;

begin

Result := FHead = FTail;

end;

procedure TtdIntDeque.Push(aValue : integer);

begin

if (FHead = 0) then

FHead := FList.Count;

dec(FHead);

FList.List^[FHead] := pointer(aValue);

if (FTail = FHead) then

idGrow;

end;

function TtdIntDeque.Pop : integer;

begin

if FHead = FTail then

idError(tdeDequeIsEmpty, 'Pop');

Result := integer(FList.List^[FHead]);

inc(FHead);

if (FHead = FList.Count) then

FHead := 0;

end;

Алгоритм работает следующим образом. Поставим значение -1 в очередь с двусторонним доступом. Это специальное значение, которое указывает о необходимости выполнить считывание входной строки по одному элементу. Теперь поставим в очередь с двусторонним доступом номер исходного состояния. Установим целочисленное значение равным 0. Это значение будет индексом текущего символа в строке, сопоставление с которой выполняется.

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