Книгу "Алгоритмы на С++" 3-е издание Роберт Седжвик тщательно переписал, значительно расширил и обновил собственную популярную книгу, чтоб получилось современное и исчерпывающее описание важных алгоритмов и структур данных. Книга содержит части 1-5 Разбор, структуры данных, сортировка, поиск, алгоритмы на графах. Вместе с Кристофером Ван Виком он разработал новые реализации на C++, которые выражают эти методы в сжатом, однако наглядном виде, и предоставляют программистам практические средства для их проверки в настоящих приложениях. В книжке представлено немало новых алгоритмов, а их объяснения намного более подробны, чем в предыдущем издании. Новая структура текста и подробные иллюстрации к нему вместе с сопутствующими комментариями существенно улучшают представление материала. III-е издание к тому же содержит удачное сочетание теории и практики, которые делают работу Седжвика бесценным источником сведений для более чем 250 000 программистов! В частях 1-4 книжки рассматриваются фундаментальные алгоритмы, структуры данных, сортировка и поиск. В ней приведено подробное описание фундаментальных структур данных и алгоритмов для сортировки, поиска и сопутствующих приложений. Впрочем, по сути, материал книжки применим к программированию на любом языке, реализации Ван Вика и Седжвика применяют естественную связь м/у классами C++ и реализациями абстрактных типов данных (АТД). В части 5 книжки рассматриваются алгоритмы на графах, которые играют все более важную роль во множестве приложений, таких как сетевая связность, конструирование электронных схем, составление графиков, обработка транзакций и выделение ресурсов.

 

Каждая часть содержит новые алгоритмы и реализации, усовершенствованные описания и диаграммы, и большое количество новых упражнений для наилучшего усвоения материала. Акцент на АТД расширяет диапазон использования программ и лучше соотносится с современными средами объектно-ориентированного программирования. В этой книжке описаны следующие тематики · Подробное описание массивов, связных списков, строк, деревьев и иных основных структур данных · Акцентирование внимание на абстрактных типах данных (АТД), модульном программировании, объектно-ориентированном программировании и классах C++ · Более 100 алгоритмов сортировки, выбора, реализаций АТД очереди с приоритетами и реализаций АТД таблицы знаков (для поиска) · Новые реализации биномиальных очередей, многопутевой поразрядной сортировки, рандомизированных BST-деревьев, скошенных деревьев, слоеных списков, многопутевых trie-деревьев, B-деревьев, расширяемого хеширования и прочих методов · Больший объем численных параметров алгоритмов, позволяющих сравнивать их · Более 1000 новых упражнений, которые помогают разобраться в свойствах алгоритмов · Полный обзор свойств и типов графов · Орграфы и DAG-графы · Минимальные остовные деревья · Кратчайшие пути · Сетевые потоки · Диаграммы, примеры кода на C++ и подробные описания алгоритмов Реальное издание предоставляет программистам полный инструментальный набор для реализации, отладки и эксплуатации алгоритмов в широком диапазоне компьютерных приложений. Об авторах Роберт Седжвик - проф. компьютерных наук в Принстонском университете. Занимает должность директора в компании Adobe Systems, работал в исследовательских коллективах в Xerox PARC, Институте оборонного анализа и INRIA. Вместе с Филиппом Флажоле (Philippe Flajolet) написал книгу An Introduction to the Analysis of Algorithms. Кристофер Дж. Ван Вик - проф. математики и компьютерных наук и заодно зам. декана в Университете Дрю. Работал в исследовательском коллективе в Bell Laboratories. И Седжвик, и Ван Вик получили свои степени доктора философии в Университете Стэнфорда под руководством Дональда Э. Кнута.

Оглавление книги

 

Часть I. Анализ 19

Глава 1. Введение 20

Глава 2. Принципы анализа алгоритмов 43

Часть II. Структуры данных 73

Глава 3. Элементарные структуры данных 74

Глава 4. Абстрактные типы данных 123

Глава 5. Рекурсия и деревья 181

Часть III. Сортировка 239

Глава 6. Элементарные методы сортировки 240

Глава 7. Быстрая сортировка 285

Глава 8. Слияние и сортировка слиянием 311

Глава 9. Очереди с приоритетами и пирамидальная сортировка 333

Глава 10. Поразрядная сортировка 375

Глава 11. Специальные методы сортировки 407

Часть IV. Поиск 439

Глава 12. Таблицы символов и деревья бинарного поиска 440

Глава 13. Сбалансированные деревья 487

Глава 14. Хеширование 529

Глава 15. Поразрядный поиск 561

Глава 16. Внешний поиск 601

Часть V. Алгоритмы на графах 633

Глава 17. Виды графов и их свойства 634

Глава 18. Поиск на графе 699

Глава 19. Орграфы и DAG-графы 757

Глава 20. Минимальные остовные деревья 823

Глава 21. Кратчайшие пути 867

Глава 22. Потоки в сетях 943

Предметный указатель 1051