Алгоритмы на 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 Предметный указатель

Инструкция как скачать книгу Роберт Седжвик: Алгоритмы на C++ в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Алгоритмы на C++
Рейтинг книги:
1 голос
1138

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: