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

{уничтожить производный объект}

inherited Destroy;

end;

procedure TtdLCSMatrix.Clear;

var

Row, Col : integer;

ColList : TList;

begin

for Row := 0 to pred(FRows) do

begin

ColList := TList(FMatrix.List^[Row]);

if (ColList <> nil) then

for Col := 0 to pred(FCols) do

begin

if (ColList.List^[Col] <> nil) then

Dispose(PtdLCSData(ColList.List^[Col]));

ColList.List^[Col] :=nil;

end;

end;

end;

function TtdLCSMatrix.mxGetItem(aRow, aCol : integer): PtdLCSData;

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxGetItem: Row or column index out of bounds');

Result := PtdLCSData(TList(FMatrix.List^[aRow]).List^[aCol]);

end;

procedure TtdLCSMatrix.mxSetItem(aRow, aCol : integer;

aValue : PtdLCSData);

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxSetItem: Row or column index out of bounds');

TList(Matrix.List^[aRow]).List^[aCol] := aValue;

end;

Следующий шаг заключается в создании класса, который реализует алгоритм вычисления LCS для строк. Код интерфейса и выполнения служебных функций класса TtdStringLCS приведен в листинге 12.23.

Листинг 12.23. Класс TtdStringLCS

type

TtdStringLCS = class private

FFromStr : string;

FMatrix : TtdLCSMatrix;

FToStr : string;

protected

procedure slFillMatrix;

function slGetCell(aFromInx, aToInx : integer): integer;

procedure slWriteChange(var F : System.Text;

aFromInx, aToInx : integer);

public

constructor Create(const aFromStr, aToStr : string);

destructor Destroy; override;

procedure WriteChanges(const aFileName : string;

end;

constructor TtdStringLCS.Create(const aFromStr, aToStr : string);

begin

{создать производный объект}

inherited Create;

{сохранить строки}

FFromStr := aFromStr;

FToStr :=aToStr;

{создать матрицу}

FMatrix := TtdLCSMatrix.Create(succ(length(aFromStr)), succ(length(aToStr)));

{заполнить матрицу}

slFillMatrix;

end;

destructor TtdStringLCS.Destroy;

begin

{уничтожить матрицу}

FMatrix.Free;

{уничтожить производный объект}

inherited Destroy;

end;

При первой реализации алгоритма вычисления LCS я столкнулся с дилеммой: придерживаться ли ранее описанного рекурсивного алгоритма или же только что описанного процесса вычисления LCS вручную? Чтобы получить ответ на ряд вопросов (какой из методов проще, какой требует использования меньшего объема памяти, какой работает быстрее), я реализовал оба подхода, причем начал с реализации итеративного метода. Это итеративное решение приведено в листинге 12.24.

Листинг 12.24. Итеративное вычисление LCS

procedure TtdStringLCS.slFillMatrix;

var

FromInx : integer;

ToInx : integer;

NorthLen: integer;

WestLen : integer;

LCSData : PtdLCSData;

begin

{создать пустые элементы, располагающиеся вдоль верхней и левой сторон матрицы}

for ToInx := 0 to length (FToStr) do

begin

New(LCSData);

LCSData^.ldLen := 0;

LCSData^.ldPrev := ldWest;

FMatrix[0, ToInx] := LCSData;

end;

for FromInx := 1 to length (FFromStr) do

begin

New(LCSData);

LCSData^.ldLen := 0;

LCSData^.ldPrev := ldNorth;

FMatrix [FromInx, 0] := LCSData;

end;

{построчное, слева направо, заполнение матрицы}

for FromInx := 1 to length (FFromStr) do

begin

for ToInx := 1 to length (FToStr) do

begin {создать новый элемент}

New(LCSData);

{если два текущих символа совпадают, необходимо увеличить значение счетчика элемента, расположенного к северо-западу, т.е. предыдущего элемента}

if (FFromStr[FromInx] = FToStr[ToInx]) then begin

LCSData^.ldPrev := ldNorthWest;

LCSData^.ldLen := succ(FMatrix[FromInx-1, ToInx-1]^.ldLen);

end

{в противном случае текущие символы различны: необходимо использовать максимальный из элементов, расположенных к северу или к западу от текущего (к западу предпочтительнее)}

else begin

NorthLen := FMatrix[FromInx-1, ToInx]^.ldLen;

WestLen := FMatrix[FromInx, ToInx-1]^.ldLen;

if (NorthLen > WestLen) then begin

LCSData^.ldPrev := ldNorth;

LCSData^.ldLen := NorthLen;

end

else begin

LCSData^.ldPrev :=ldWest;

LCSData^.ldLen := WestLen;

end;

end;

{установить элемент в матрице}

FMatrix[FromInx, ToInx] := LCSData;

end;

end;

{на этом этапе длина элемента, расположенного в нижнем правом углу, равна LCS, и вычисление завершено}

end;