Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 354
Джулиан М. Бакнелл
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;
end
{в противном случае текущие строки различны: необходимо использовать максимальный из элементов, расположенных к северу или западу (использование элемента, расположенного к западу, предпочтительнее)} else begin
NorthLen := slGetCell(aFromInx-1, aToInx);
WestLen := slGetCell(aFromInx, aToInx-1);
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev := ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить элемент в матрице}
FMatrix [ aFromInx, aToInx ] := LCSData;
{вернуть длину данного LCS}
Result := LCSData^.ldLen;
end;
end;
end;
Метод записи последовательности редактирования, которая обеспечивает преобразование первого файла во второй, не особенно изменился по сравнению с рассмотренным ранее, за исключением того, что выполняется запись строк, а не символов. Эта подпрограмма приведена в листинге 12.29.
Листинг 12.29. Запись последовательности редактирования для пары файлов
procedure TtdFileLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса меньше нуля, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = -1) and (aToInx = -1) then
Exit;
{если индекс строки From меньше нуля, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = -1) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToFile[aToInx]);
end
{если индекс строки To меньше нуля, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = -1) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth :
begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile [aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, 1 ', FFromFile[aFromInx]);
end;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(Ff FToFile[aToInx]);
end;
end;
end;
end;
procedure TtdFileLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange (F, pred(FFromFile.Count), pred(FToFile.Count)) finally
System.Close(F);
end;
end;
Резюме
В этой главе были рассмотрены три дополнительных алгоритма. Первые два предназначены для работы с многопоточными приложениями. Третий представляет собой весьма значимый, однако малоизвестный алгоритм поиска различий между двумя версиями файла.
Применительно к многопоточным приложениям, мы рассмотрели решение проблемы синхронизации потоков считывания-записи - алгоритма, который играет большую роль во множестве программ подобного рода. Применительно к проблеме использования потоков производителей-потребителей, мы рассмотрели алгоритм, который может применяться во многих ситуациях, когда большие объемы данных должны одновременно обрабатываться, причем различным образом.
