Чтение онлайн

на главную

Жанры

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

Бакнелл Джулиан М.

Шрифт:

procedure WriteChanges(const aFileName : string);

end;

constructor TtdFileLCS.Create(const aFromFile, aToFile : string);

begin

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

inherited Create;

{выполнить считывание файлов}

FFromFile := TStringList.Create;

FFromFile.LoadFromFile(aFromFile);

FToFile := TStringList.Create;

FToFile.LoadFromFile(aToFile);

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

FMatrix := TtdLCSMatrix.Create(FFromFile.Count, FToFile.Count);

{заполнить

матрицу}

slGetCell(pred(FFromFile.Count), pred(FToFile.Count));

end;

destructor TtdFileLCS.Destroy;

begin

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

FMatrix.Free;

{освободить списки строк}

FFromFile.Free;

FToFile.Free;

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

inherited Destroy;

end;

Однако нужно решить одну проблему: при работе со строками отсчет символов начинается с 1, а при работе со списком строк отсчет строк (строк в исходном файле) начинается с 0. Поэтому необходимо внести ряд изменений.

Первое изменение заключается в простом кодировании рекурсивного метода. Если помните, итеративный метод требовал предварительного выделения ячеек, расположенных вдоль верхней и левой сторон матрицы, и установки их значений равными 0, в то время как в рекурсивном методе для выполнения этой задачи использовался оператор If. Потенциально это позволяет сэкономить достаточно большой объем памяти (в общем случае текстовые файлы могут содержать несколько сотен или даже тысяч строк).

Второе изменение, как уже отмечалось, - отсчет строк с 0. Рекурсивная подпрограмма автоматически решает эту задачу.

Код реализации рекурсивного метода генерирования LCS для двух файлов приведен в листинге 12.28.

Листинг 12.28. Генерация LCS для пары файлов

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

var

LCSData : PtdLCSData;

NorthLen: integer;

WestLen : integer;

begin

if (aFromInx = -1) or (aToInx = -1) then

Result := 0

else begin

LCSData := FMatrix[aFromInx, aToInx];

if (LCSData <> nil) then

Result := LCSData^.ldLen

else begin

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

New(LCSData);

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

if (FFromFile[aFromInx] = FToFile [aToInx]) then begin

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;

Поделиться:
Популярные книги

Бастард Императора

Орлов Андрей Юрьевич
1. Бастард Императора
Фантастика:
фэнтези
аниме
5.00
рейтинг книги
Бастард Императора

На границе империй. Том 10. Часть 1

INDIGO
Вселенная EVE Online
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 10. Часть 1

Имя нам Легион. Том 7

Дорничев Дмитрий
7. Меж двух миров
Фантастика:
боевая фантастика
рпг
аниме
5.00
рейтинг книги
Имя нам Легион. Том 7

Измена. Вторая жена мужа

Караева Алсу
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Вторая жена мужа

Буря империи

Сай Ярослав
6. Медорфенов
Фантастика:
аниме
фэнтези
фантастика: прочее
эпическая фантастика
5.00
рейтинг книги
Буря империи

Пенсия для морского дьявола

Чиркунов Игорь
1. Первый в касте бездны
Фантастика:
попаданцы
5.29
рейтинг книги
Пенсия для морского дьявола

На изломе чувств

Юнина Наталья
Любовные романы:
современные любовные романы
6.83
рейтинг книги
На изломе чувств

Тринадцатый II

NikL
2. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Тринадцатый II

Сирота

Шмаков Алексей Семенович
1. Светлая Тьма
Фантастика:
юмористическое фэнтези
городское фэнтези
аниме
5.00
рейтинг книги
Сирота

Законы Рода. Том 9

Flow Ascold
9. Граф Берестьев
Фантастика:
городское фэнтези
попаданцы
аниме
дорама
фэнтези
фантастика: прочее
5.00
рейтинг книги
Законы Рода. Том 9

Красноармеец

Поселягин Владимир Геннадьевич
1. Красноармеец
Фантастика:
боевая фантастика
попаданцы
4.60
рейтинг книги
Красноармеец

Огненный князь 4

Машуков Тимур
4. Багряный восход
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Огненный князь 4

Начальник милиции. Книга 5

Дамиров Рафаэль
5. Начальник милиции
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Начальник милиции. Книга 5

Инкарнатор

Прокофьев Роман Юрьевич
1. Стеллар
Фантастика:
боевая фантастика
рпг
7.30
рейтинг книги
Инкарнатор