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

Хочу выразить благодарность Крису Фризелду (Chris Frizell), редактору и владельцу журнала The Delphi Magazine (www.thedelphimagazine.com). Он как в воду глядел, предоставив мне возможность обсудить множество алгоритмов на страницах его поистине бесценного журнала, в конечном итоге отдав мне отдельную ежемесячную колонку Algorithms Affresco. Без его содействия и поддержки эта книга могла бы и не появиться, во всяком случае, даже если бы она и появилась, она бы уж точно была намного хуже. Я настоятельно рекомендую всем разработчикам подписаться на журнал The Delphi Magazine, поскольку, по моему мнению, он был, есть и будет наиболее глубоким, фундаментальным и серьезным периодическим изданием для широчайшего круга программистов на Delphi. Спасибо всем читателям моей колонки за их суждения и комментарии.

Под занавес, я хотел бы поблагодарить всех сотрудников издательства Wordware (www.wordware.com), в том числе моих редакторов, издателя Джима Хилла (Jim Hill) и выпускающего редактора Вес Беквис (Wes Beckwith). Джим поначалу был несколько обескуражен моим предложением издать книгу, посвященную алгоритмам, однако он очень быстро проникся моими идеями и оказывал всемерную поддержку на протяжении всего времени подготовки книги. Кроме того, я хочу выразить самые теплые благодарности научным редакторам: Стиву Тексейра (Steve Teixeira), одному их авторов Delphi X Developer's Guide, и моему другу Энтону Паррису (Anton Parris).

И, в заключение, хочу выразить благодарность и еще раз признаться в любви своей жене, Донне (вот кто был основной движущей силой, постоянно побуждающей меня к работе над книгой). Без ее любви, энтузиазма и поощрения я не смог бы прожить все эти годы. Спасибо тебе, любящее сердце. Ты знаешь, что рядом с тобой бьется второе такое же!

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

Колорадо Спрингс,

апрель, 1999 года - февраль 2001 года

Глава 1. Что такое алгоритм?

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

Несмотря на то что темой этой книги будут алгоритмы, структуры данных и их реализация в коде, мы рассмотрим и некоторые чисто процедурные моменты: как написать код, который позволит упростить отладку в случае возникновения проблем, как выполнять тестирование кода и как убедиться в том, что изменения, вносимые в одном месте, не вызовут ошибок в другом месте.

Что такое алгоритм?

Может показаться странным, но алгоритмы используются при написании любой программы, просто мы не считаем их алгоритмами: "Это вовсе не алгоритм, а просто порядок вычислений".

Алгоритм (algorithm) представляет собой пошаговую инструкцию выполнения вычислений или процесса. Это достаточно вольное определение, но как только читатель поймет, что ему нечего бояться алгоритмов, он легко научиться их идентифицировать.

Вернемся к дням, когда мы учились в начальных классах и рассматривали простое сложение в столбик.

Учитель писал на доске пример сложения:

45

17+

----

а затем просил кого-нибудь из учеников вычислить сумму. Каждый про себя думал, как это сделать: начинаем со столбца единиц, складываем 5 и 7, получаем 12, пишем 2 в столбце единиц, а затем 1 переносим над 4.

1

45

17+

----

62

Затем складываем перенесенную единицу с 4 и еще одну 1, в результате получаем 6, которое и пишем под столбцом десятков. Вот и получился ответ 62.

Обратите внимание, что описанный выше ход мыслей представлял собой алгоритм сложения. Учитель не говорил, как складывать числа 45 и 17, он просто объяснил общий принцип сложения двух чисел. Вскоре любой ученик, применяя тот же алгоритм, мог складывать одновременно несколько чисел, содержащих много цифр. Конечно, в те дни вы не знали, что это был алгоритм, вы просто складывали числа.