Джулиан М. Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Название: | Фундаментальные алгоритмы и структуры данных в Delphi | |
Автор: | Джулиан М. Бакнелл | |
Жанр: | Современные российские издания, Литература ХXI века (эпоха Глобализации экономики), Алгоритмы и структуры данных, Pascal, Delphi, Lazarus и т.п. | |
Изадано в серии: | неизвестно | |
Издательство: | ДиаСофтЮП | |
Год издания: | 2003 | |
ISBN: | ISBN 5-93772-087-3 | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».
В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.
Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.
Читаем онлайн "Фундаментальные алгоритмы и структуры данных в Delphi". [Страница - 229]
Листинг 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;
Мы начинаем с заполнения верхней строки и левого столбца матрицы нулевыми ячейками. Длина LCS в этих ячейках равна нулю (вспомните, что они описывают LCS пустой и какой-либо другой строки), и мы всего лишь устанавливаем флаг направления, дабы он указывал на предшествующую ячейку, ближайшую к ячейке (0,0). Затем следует вложенный цикл (цикл по столбцам внутри цикла по строкам). Для каждой строки мы вычисляем LCS для каждой из ячеек,.просматривая их слева направо. Эти вычисления выполняются для всех строк сверху вниз. Вначале мы проверяем, совпадают ли два символа, на которые ссылается ячейка. (Ячейка матрицы представляет собой переход от символа строки From (Из) к символу строки То (В).) Если они совпадают, длина LCS в этой ячейке равна длине LCS ячейки, расположенной к северо-западу от данной, плюс единица. Обратите внимание, что способ вычисления ячеек предполагает, что ячейка, на которую осуществляется ссылка, уже вычислена (именно поэтому мы заранее вычислили значения ячеек, расположенных вдоль верхней и левой сторон матрицы). Если два символа не совпадают, необходимо просмотреть ячейки, расположенные к северу и к западу от текущей. Мы выбираем ту, которая содержит наиболее длинную LCS, и используем это значение в качестве значения данной ячейки. Если две длины равны, можно выбрать любую из них. Однако мы будем придерживаться правила, что предпочтительнее выбирать LCS, соответствующую ячейке, которая расположена слева. Этот выбор обусловлен тем, что как только путь через матрицу, обеспечивающий определение LCS обеих строк, вычислен, удаления из первой строки выполняются раньше вставок во вторую строку.
Обратите внимание, что приведенный в листинге 12.24 метод требует постоянного времени для обработки двух строк, независимо от степени их совпадения или несовпадения. Если длина строк равна, соответственно, n и т, то время, требуемое для выполнения основного цикла, будет пропорционально произведению n * m, поскольку таковым является количество ячеек, значения которых нужно вычислить. (помните, что ячейка, для которой действительно нужно получить ответ - последняя, значение которой должно вычисляться;
она расположена в нижнем правом углу матрицы).
Алгоритм, реализованный с применением рекурсивного метода, приведен в листинге 12.25. Рекурсивная подпрограмма кодируется в виде функции, которая возвращает длину LCS для конкретной ячейки, заданной индексом строки и столбца (которые, в конечном счете, представляют собой индексы, указывающие на строки From и То).
Листинг 12.25. Рекурсивное вычисление LCS
function TtdStringLCS.slGetCell(aFromInx, aToInx : integer): integer;
var
LCSData : PtdLCSData;
NorthLen: integer;
WestLen : integer;
begin
if (aFromInx = 0) or (aToInx = 0) then
Result := 0
else begin
LCSData := FMatrix[ aFromInx, aToInx];
if (LCSData <> nil) then
Result := LCSData^.ldLen else begin
{создать новый элемент}
New(LCSData);
{если два символа совпадают, необходимо увеличить значение счетчика относительно элемента, расположенного к северо-западу от данного, т.е. предшествующего элемента}
if (FFromStr[aFromInx] = FToStr [aToInx]) then begin
LCSData^.ldPrev := --">Книги схожие с «Фундаментальные алгоритмы и структуры данных в Delphi» по жанру, серии, автору или названию:
Александр Александрович Зданович - Тайные службы России : структуры, лица, деятельность : учебное пособие Жанр: Учебники и пособия: прочее Год издания: 2021 |
Вячеслав Владимирович Меньшиков - Ржев – Сталинград. Скрытый гамбит маршала Сталина Жанр: История: прочее Год издания: 2012 |
Евгений Николаевич Герасимов, Владимир Григорьевич Шмерлинг - Сталинградцы (Рассказы жителей о героической обороне) Жанр: Биографии и Мемуары Год издания: 2017 |
Олег Пауллер - Псы войны. Дневники Шеннона Жанр: Приключения Год издания: 2018 |