Благодарности
Любую книгу готовит далеко не один человек, и, естественно, эта - не исключение. Есть очень много людей, без усилий которых эта книга так и не увидела бы свет. Я хотел бы представить этих людей в, так сказать, исторической последовательности, последовательности, в соответствие с которой они оказывали на меня свое благотворное влияние.
С первыми двумя джентльменами, к сожалению, я никогда не разговаривал лично и не встречался, однако это те люди, которые до сих пор держат мои глаза широко открытыми и постоянно питают мой энтузиазм в безбрежном мире алгоритмов. Если бы не они, кто знает, где бы я был сейчас и чем бы занимался. Я имею в виду Дональда Кнута (Donald Knuth) (www.es.staff.stanford/edu/-knuth/) и Роберта Седжвика (Robert Sedgewick) (www.cs.princeton.edu/-rs/). В действительности, книга Седжвика, посвященная алгоритмам [20], как раз и сподвигла меня на начало моей творческой деятельности. Это была первая книга подобного рода, которую я даже решился приобрести, причем в то время я только-только вникал в программирование на Turbo Pascal. Дональд Кнут вообще не требует какого-либо представления. Его поистине великолепные труды [11, 12, 13] по-прежнему находятся на верхушке всего дерева алгоритмов; впервые я воспользовался этой книгой во время учебы в Королевском колледже Лондонского университета при получении степени бакалавра по математике.
Несколько лет спустя, следующим человеком, кому я хотел бы выразить свою благодарность, стал Ким Кокконен (Kim Kokkonen). Он предоставил мне работу в компании TurboPower Software (www.turbopower.com) и дал мне возможность настолько досконально изучить компьютерные науки, насколько я даже не мог и мечтать. Хочу поблагодарить также и всех сотрудников компании TurboPower Software, а также тех ее клиентов, которых я знал на протяжении многих лет. Благодарю Роберта Делросси (Rober DelRossi), президента TurboPower Software, за поощрение всех моих начинаний.
Следующей идет маленькая компания, к сожалению, ныне не работающая, которая называлась Natural Systems. В 1993 году эта компания выпустила продукт под названием Data Structures for Turbo Pascal (Структуры данных для Turbo Pascal). Я купил этот продукт, и, по моему мнению, это было не особенно удачное приобретение. О да, продукт работал неплохо, однако я не был согласен ни с его дизайном, ни с реализацией, кроме того, скорость функционирования оставляла желать лучшего. Именно этот продукт побудил меня написать собственную бесплатную библиотеку EZSTRUCS для Turbo Pascal 7, от которой, собственно и пошла моя хорошо известная бесплатная библиотека структур данных для 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).
И, в заключение, хочу выразить благодарность и еще раз признаться в любви своей жене, Донне (вот кто был основной движущей силой, постоянно побуждающей меня к работе над книгой). Без ее любви, энтузиазма и поощрения я не смог бы прожить все эти годы. Спасибо тебе, любящее сердце. Ты знаешь, что рядом с тобой бьется второе такое же!
Глава 1. Что такое алгоритм?
Для книги, посвященной алгоритмам, очень важно заранее оговорить, о чем, собственно, пойдет речь. Как мы увидим, одной из самых важных причин для понимания и исследования алгоритмов является ускорение работы приложений. Да, конечно, иногда нужны алгоритмы, для которых более важную роль играет занимаемое ими пространство памяти, а не их быстродействие, но все же в большинстве случаев решающим фактором является именно быстродействие.
Несмотря на то что темой этой книги будут алгоритмы, структуры данных и их реализация в коде, мы рассмотрим и некоторые чисто процедурные моменты: как написать код, который позволит упростить отладку в случае возникновения проблем, как выполнять тестирование кода и как убедиться в том, что изменения, вносимые в одном месте, не вызовут ошибок в другом месте.
Что такое алгоритм?
Может показаться странным, но алгоритмы используются при написании любой программы, просто мы не считаем их алгоритмами: 'Это вовсе не алгоритм, а просто порядок вычислений'.
Алгоритм (algorithm) представляет собой пошаговую инструкцию выполнения вычислений или процесса. Это достаточно вольное определение, но как только читатель поймет, что ему нечего бояться алгоритмов, он легко научиться их идентифицировать.
Вернемся к дням, когда мы учились в начальных классах и рассматривали простое сложение в столбик.
Учитель писал на доске пример сложения:
45
17+
----
а затем просил кого-нибудь из учеников вычислить сумму. Каждый про себя думал, как это сделать: начинаем со столбца единиц, складываем 5 и 7, получаем 12, пишем 2 в столбце единиц, а затем 1 переносим над 4.
1
45
17+
----
62
Затем складываем перенесенную единицу с 4 и еще одну 1, в результате получаем 6, которое и пишем
