Для всех реализаций использовался язык программирования С++. В программах применяется широкое множество стандартных идиом С++, а в текст включены краткие описания каждой из конструкций.

Автор совместно с Крисом Ван Виком разработали основанный на классах, шаблонах и перегруженных операциях стиль программирования на С++, который по нашему мнению позволяет эффективно представлять алгоритмы и структуры данных в виде реальных программ. Мы стремились к изящным, компактным, эффективным и переносимым реализациям. Везде, где это возможно, мы стремились сохранить единство стиля, дабы сходные по действию программы выглядели похожими.

Для множества приведенных в этой книге алгоритмов схожесть сохраняется независимо от языка: быстрая сортировка остается быстрой сортировкой (это лишь один яркий пример) независимо от того, выражена ли она на языке Ada, Algol-60, Basic, С, С++, Fortran, Java, Mesa, Modula-3, Pascal, PostScript, Smalltalk или на одном из других бесчисленных языков программирования или в другой среде, где она зарекомендовала себя как эффективный метод сортировки. С одной стороны, представленный нами код продиктован опытом реализации алгоритмов на этих и множестве других языков (С-версия этой книги также доступна, а Java-версия будет вскоре издана). С другой стороны, отдельные особенности некоторых из этих языков продиктованы опытом их применения разработчиками по отношению к некоторым алгоритмам и структурам данных, которые рассматриваются в книге.

Глава 1 является характерным примером подобного подхода к разработке эффективных реализаций рассматриваемых алсоритмов на С++, а в главе 2 описывается используемый нами подход к их анализу. Главы 3 и 4 посвящены описанию и обоснованию основных механизмов, используемых для реализаций типов данных и абстрактных типов данных. Эти четыре главы закладывают фундамент для понимания остальной части книги.

Благодарности

Многие читатели прислали мне исключительно полезные отзывы о предыдущих изданиях этой книги. В частности, в течение ряда лет предварительные наброски книги апробировались на сотнях студентов в Принстоне и Брауне. Особую благодарность хотелось бы выразить Трине Авери (Trina Avery) и Тому Фримену (Тот Freeman) за оказанную помощь в выпуске первого издания; Джанет Инсерпи (Janet 1псеф1) за проявленные ею творческий подход и изобретательность, чтобы заставить аппаратное и программное обеспечение нашей первой примитивной компьютеризованной издательской системы создать первое издание; Марку Брауну (Маге Brown) за его участие в исследованиях по визуализации алгоритмов, которые явились источником множества рисунков, приведенных в книге, а также Дэйву Хэнсону (Dave Hanson) и Эндрю Эппелю (Andrew Appel) за их готовность ответить на все мои вопросы, связанные с языками программирования. Я хотел бы также поблагодарить очень многих читателей, приславших отзывы о многих изданиях, в том числе Гаю Олмсу (Guy Almes), Джону Бентли (Jon Bentley), Марку Брауну (Marc Brown), Джею Гишеру (Jay Gischer), Аллану Хейдону (Allan Heydon), Кеннеди Лемке (Kennedy Lemke), Юди Манбер (Udi Manber), Дане Ричарде (Dana Richards), Джону Рейфу (John Reif), М. Розенфельду (М. Rosenfeld), Стивену Сейдману (Stephen Seidman), Майку Квину (Michael Quinn) и Вильяму Варду (William Ward).

При подготовке нового издания я имел удовольствие работать с Питером Гордоном (Peter Gordon), Дебби Лафферти (Debbie Lafferty) и Хелен Гольдштейн (Helen Goldstein) из издательства Addison-Wesley, которые терпеливо опекали этот проект с момента его зарождения. Большое удовольствие доставила мне совместная работа с другими штатными сотрудниками этого издательства. Характер проекта сделал подготовку издания данной книги несколько непривычной задачей для многих из них, и я высоко ценю проявленную ими снисходительность.

В процессе написания этой книги я приобрел трех новых наставников и хочу особо выразить им свою признательность. Во-первых, Стиву Саммиту (Steve Summit), который внимательно проверил на техническом уровне первые варианты рукописи и предоставил буквально тысячи подробных комментариев, особенно в отношении программ. Стив хорошо понял мое стремление представить изящные и эффективные реализации, и его комментарии помогли мне не только обеспечить определенное единообразие реализаций, но и существенно улучшить многие из них. Во-вторых, хочу поблагодарить Лин Дюпре (Lyn Dupre) за тысячи подробных комментариев в отношении рукописи, которые помогли не только избежать и исправить грамматические ошибки, но и (что значительно важнее) выработать последовательный и связный стиль написания, что позволило собрать воедино устрашающую массу технического материла. В-третьих, я признателен Крису Ван Вику (Chris Van Wyk), который реализовал и отладил все мои алгоритмы на С++, помог выработать подходящий стиль программирования на С++ и дважды внимательно прочел рукопись. Кроме того, Крис сохранял терпение, когда я препарировал многие из его программ, а затем, по мере того как все больше узнавал от него о языке С++, вынужден был снова собирать их воедино, причем в большинстве случаев так, как первоначально на-

писал их он. Я исключительно благодарен полученной возможности поучиться у Стива, Лин и Криса - они оказали решающее влияние на разработку этой книги.

Многое из написанного здесь я узнал из лекций и трудов Дона Кнута (Don Knuth) - моего наставника в Стэнфорде. Хотя непосредственно Дон и не участвовал в создании этой работы, его влияние должно ощущаться по всей книге, поскольку именно он поставил изучение алгоритмов на научную основу, что делает возможным вообще появление подобного рода книг. Мой друг и коллега Филипп Флажоле (Philippe Flajolet), благодаря которому анализ алгоритмов стал вполне сформировавшейся научной областью, оказал такое же влияние.

Я глубоко признателен за оказанную мне поддержку Принстонскому университету, Брауновскому университету и Национальному институту исследований в области информатики и автоматики (INRIA), где я проделал большую часть работы над книгой, а также Институту исследований защиты и Исследовательскому центру компании Xerox в Пало-Альто, где была проделана часть работы во время моих визитов. Многие главы книги основываются на исследованиях, которые щедро финансировались Национальным научным фондом и Отделом военно-морских исследований. И в заключение, я благодарю Билла Боуэна (Bill Bowen), Аарона Лемоника (Aaron Lemonick) и Нейла Руденштайна (Neil Rudenstine) за то, что они способствовали созданию в Принстоне академической обстановки, в которой я получил возможность подготовить эту книгу, несмотря на множество других возложенных на меня обязанностей.

Роберт Седжвик Марли-ле-Руа, Франция, 1983 г. Принстон, Нью-Джерси, 1990, 1992 гг. Джеймстаун, Род-Айленд, 1997 г. Принстон, Нью-Джерси, 1998 г.