Алгоритмы на C++

Роберт Седжвик

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

В книге представлено много новых алгоритмов, а их объяснения гораздо более подробны, чем в предыдущем издании. Новая структура текста и подробные иллюстрации к нему вместе с сопутствующими комментариями значительно улучшают представление материала. Третье издание также содержит удачное сочетание теории и практики, которые делают работу Седжвика бесценным источником сведений для более чем 250 000 программистов!

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

В этой книге описаны следующие темы

Подробное описание массивов, связных списков, строк, деревьев и других базовых структур данных
Акцентирование внимание на абстрактных типах данных (АТД), модульном программировании, объектно-ориентированном программировании и классах C++
Более 100 алгоритмов сортировки, выбора, реализаций АТД очереди с приоритетами и реализаций АТД таблицы символов (для поиска)
Новые реализации биномиальных очередей, многопутевой поразрядной сортировки, рандомизированных BST-деревьев, скошенных деревьев, слоеных списков, многопутевых trie-деревьев, B-деревьев, расширяемого хеширования и многих других методов
Больший объем численных характеристик алгоритмов, позволяющих сравнивать их
Более 1000 новых упражнений, которые помогают разобраться в свойствах алгоритмов
Полный обзор свойств и типов графов
Орграфы и DAG-графы
Минимальные остовные деревья
Кратчайшие пути
Сетевые потоки
Диаграммы, примеры кода на C++ и подробные описания алгоритмов

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

Издательство: Вильямс, 2011 г.

Рекомендуем обратить внимания на книги Роберта Седжвика:

Фундаментальные алгоритмы на C. Части 1 - 4. Анализ. Структуры данных. Сортировка. Поиск

Фундаментальные алгоритмы на C. Часть 5. Алгоритмы на графах

Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах

ISBN 978-5-8459-1650-1, 978-0-321-60633-4

Количество страниц: 1056.

Содержание книги «Алгоритмы на C++»:

11 Об авторе
11 Благодарности
12 От издательства
13 Предисловие консультанта по C++
14 Введение
- 15 Круг рассматриваемых вопросов
- 15 Использование в учебных курсах
- 16 Практическое применение алгоритмов
- 17 Язык программирования
- 17 Об упражнениях
19 Часть I. Анализ
20 Глава 1. Введение
- 21 1.1. Алгоритмы
- 22 1.2. Пример задачи: связность
- 26 1.3. Алгоритмы объединения и поиска
- 38 1.4. Перспективы
- 40 1.5. Обзор тем
43 Глава 2. Принципы анализа алгоритмов
- 44 2.1. Реализация и эмпирический анализ
- 47 2.2. Анализ алгоритмов
- 49 2.3. Возрастание функций
- 56 2.4. O-нотация
- 60 2.5. Простейшие рекурсии
- 64 2.6. Примеры анализа алгоритмов
- 68 2.7. Гарантии, предсказания и ограничения
- 71 Ссылки к части I
73 Часть II. Структуры данных
74 Глава 3. Элементарные структуры данных
- 75 3.1. Строительные блоки
- 84 3.2. Массивы
- 91 3.3. Связные списки
- 97 3.4. Простые операции со списками
- 105 3.5. Выделение памяти под списки
- 108 3.6. Строки
- 113 3.7. Составные структуры данных
123 Глава 4. Абстрактные типы данных
- 132 4.1. Абстрактные объекты и коллекции объектов
- 134 4.2. АТД для стека магазинного типа
- 137 4.3. Примеры клиентов, использующих ATД стека
- 143 4.4. Реализации АТД стека
- 147 4.5. Создание нового АТД
- 153 4.6. Очереди FIFO и обобщенные очереди
- 160 4.7. Повторяющиеся и индексные элементы
- 164 4.8. АТД первого класса
- 175 4.9. Пример использования АТД
- 179 4.10. Перспективы
181 Глава 5. Рекурсия и деревья
- 182 5.1. Рекурсивные алгоритмы
- 188 5.2. Разделяй и властвуй
- 202 5.3. Динамическое программирование
- 209 5.4. Деревья
- 217 5.5. Математические свойства бинарных деревьев
- 220 5.6. Обход дерева
- 226 5.7. Рекурсивные алгоритмы для бинарных деревьев
- 230 5.8. Обход графа
- 236 5.9. Перспективы
- 238 Ссылки для части II
239 Часть III. Сортировка
240 Глава 6. Элементарные методы сортировки
- 241 6.1. Правила игры
- 246 6.2. Сортировка выбором
- 248 6.3. Сортировка вставками
- 250 6.4. Пузырьковая сортировка
- 252 6.5. Характеристики производительности элементарных методов сортировки
- 258 6.6. Сортировка Шелла
- 266 6.7. Сортировка других типов данных
- 270 6.8. Сортировка индексов и указателей
- 277 6.9. Сортировка связных списков
- 281 6.10. Метод распределяющего подсчета
285 Глава 7. Быстрая сортировка
- 286 7.1. Базовый алгоритм
- 290 7.2. Характеристики производительности быстрой сортировки
- 293 7.3. Размер стека
- 296 7.4. Подфайлы небольшого размера
- 299 7.5. Разбиение по медиане из трех
- 303 7.6. Повторяющиеся ключи
- 306 7.7. Строки и векторы
- 308 7.8. Выборка
311 Глава 8. Слияние и сортировка слиянием
- 312 8.1. Двухпутевое слияние
- 314 8.2. Абстрактное обменное слияние
- 316 8.3. Нисходящая сортировка слиянием
- 319 8.4. Усовершенствования базового алгоритма
- 321 8.5. Восходящая сортировка слиянием
- 325 8.6. Производительность сортировки слиянием
- 328 8.7. Реализации сортировки слиянием для связных списков
- 331 8.8. Возврат к рекурсии
333 Глава 9. Очереди с приоритетами и пирамидальная сортировка
- 336 9.1. Элементарные реализации
- 340 9.2. Пирамидальная структура данных
- 342 9.3. Алгоритмы на пирамидальных деревьях
- 350 9.4. Пирамидальная сортировка
- 356 9.5. АТД очереди с приоритетами
- 361 9.6. Очереди с приоритетами для индексных элементов
- 365 9.7. Биномиальные очереди
375 Глава 10. Поразрядная сортировка
- 377 10.1. Биты, байты и слова
- 380 10.2. Бинарная быстрая сортировка
- 384 10.3. Поразрядная MSD-сортировка
- 391 10.4. Трехпутевая поразрядная быстрая сортировка
- 395 10.5. Поразрядная LSD-сортировка
- 398 10.6. Характеристики производительности поразрядных сортировок
- 402 10.7. Сортировки с сублинейным временем выполнения
407 Глава 11. Специальные методы сортировки
- 408 11.1. Нечетно-четная сортировка слиянием Бэтчера
- 413 11.2. Сортирующие сети
- 421 11.3. Внешняя сортировка
- 427 11.4. Реализации сортировки-слияния
- 433 11.5. Параллельная сортировка-слияние
- 437 Ссылки для части III
439 Часть IV. Поиск
440 Глава 12. Таблицы символов и деревья бинарного поиска
- 441 12.1. Абстрактный тип данных таблицы символов
- 447 12.2. Распределяющий поиск
- 450 12.3. Последовательный поиск
- 457 12.4. Бинарный поиск
- 462 12.5. Деревья бинарного поиска
- 468 12.6. Характеристики производительности деревьев бинарного поиска
- 472 12.7. Индексные реализации таблиц символов
- 475 12.8. Вставка в корень в деревьях бинарного поиска
- 479 12.9. Реализации других функций АТД с помощью BST-дерева
487 Глава 13. Сбалансированные деревья
- 490 13.1. Рандомизированные BST-деревья
- 496 13.2. Скошенные деревья бинарного поиска
- 503 13.3. Нисходящие 2-3-4-деревья
- 508 13.4. RB-деревья
- 518 13.5. Слоеные списки
- 525 13.6. Характеристики производительности
529 Глава 14. Хеширование
- 530 14.1. Хеш-функции
- 539 14.2. Цепочки переполнения
- 543 14.3. Линейное опробование
- 548 14.4. Двойное хеширование
- 553 14.5. Динамические хеш-таблицы
- 556 14.6. Перспективы
561 Глава 15. Поразрядный поиск
- 562 15.1. Деревья цифрового поиска
- 566 15.2. Trie-деревья
- 574 15.3. Patricia-деревья
- 582 15.4. Многопутевые trie-деревья и TST-деревья
- 597 15.5. Алгоритмы индексирования текстовых строк
601 Глава 16. Внешний поиск
- 602 16.1. Правила игры
- 604 16.2. Индексно-последовательный доступ
- 607 16.3. B-деревья
- 619 16.4. Расширяемое хеширование
- 629 16.5. Перспективы
- 632 Ссылки для части IV
633 Часть V. Алгоритмы на графах
634 Глава 17. Виды графов и их свойства
- 637 17.1. Глоссарий
- 645 17.2. АТД графа
- 652 17.3. Представление графа в виде матрицы смежности
- 657 17.4. Представление графа в виде списков смежности
- 661 17.5. Вариации, расширения и затраты
- 669 17.6. Генераторы графов
- 679 17.7. Простые, эйлеровы и гамильтоновы пути
- 691 17.8. Задачи обработки графов
699 Глава 18. Поиск на графе
- 700 18.1. Исследование лабиринта
- 704 18.2. Поиск в глубину
- 708 18.3. Функции АТД поиска на графе
- 713 18.4. Свойства лесов DFS
- 720 18.5. Алгоритмы DFS
- 726 18.6. Разделимость и двусвязность
- 734 18.7. Поиск в ширину
- 742 18.8. Обобщенный поиск на графах
- 751 18.9. Анализ алгоритмов на графах
757 Глава 19. Орграфы и DAG-графы
- 759 19.1. Глоссарий и правила игры
- 767 19.2. Анатомия DFS в орграфах
- 775 19.3. Достижимость и транзитивное замыкание
- 786 19.4. Отношения эквивалентности и частичные порядки
- 789 19.5. DAG-графы
- 794 19.6. Топологическая сортировка
- 803 19.7. Достижимость в DAG-графах
- 806 19.8. Сильные компоненты в орграфах
- 815 19.9. Еще раз о транзитивном замыкании
- 819 19.10. Перспективы
823 Глава 20. Минимальные остовные деревья
- 825 20.1. Представления
- 833 20.2. Основные принципы алгоритмов построения MST-дерева
- 840 20.3. Алгоритм Прима и поиск по приоритету
- 849 20.4. Алгоритм Крускала
- 855 20.5. Алгоритм Борувки
- 858 20.6. Сравнения и усовершенствования
- 864 20.7. Евклидово MST-дерево
867 Глава 21. Кратчайшие пути
- 874 21.1. Основные принципы
- 881 21.2. Алгоритм Дейкстры
- 890 21.3. Кратчайшие пути между всеми парами вершин
- 897 21.4. Кратчайшие пути в ациклических сетях
- 905 21.5. Евклидовы сети
- 910 21.6. Сведение
- 925 21.7. Отрицательные веса
- 941 21.8. Перспективы
943 Глава 22. Потоки в сетях
- 949 22.1. Транспортные сети
- 958 22.2. Алгоритмы поиска максимального потока расширением пути
- 981 22.3. Алгоритмы определения максимальных потоков проталкиванием напора
- 994 22.4. Сведения к вычислению максимального потока
- 1011 22.5. Потоки минимальной стоимости
- 1020 22.6. Сетевой симплексный алгоритм
- 1037 22.7. Сведения к задаче о потоке минимальной стоимости
- 1046 22.8. Перспективы
1051 Предметный указатель