Книги по классическим алгоритмам и структурам данных и сборники задач с решениями. Сборники задач по самому языку C++ будут в части с обзорами профессиональной литературы.

Мариус Бансила. Решение задач на современном C++

302 страницы. ДМК, 2019

Marius Bancila. The Modern C++ Challenge. Packt, 2018

Задачи и решения на C++17.

Вот темы и некоторые задачи:

• математические задачи (код Грея, преобразование чисел в римскую запись, вычисление \(\pi\), проверка ISBN...),
• особенности языка (перечисление адресов в IPv4, двумерный массив с базовыми операциями, функция min() с переменным числом аргументов, литералы разных температурных шкал...),
• строки и регулярные выражения, потоки данных и файловые системы (треугольник Паскаля, удаление пустых строк из файла, удаление файлов старше заданной даты...),
• дата и время (время выполнения программы, число дней между датами, календарь на месяц...),
• алгоритмы и структуры данных (очередь с приоритетом, циклический буфер, двойной буфер, самый часто встречающийся элемент в диапазоне, текстовая гистограмма, фильтрация списка телефонных номеров, преобразование списка телефонных номеров, генерация всех перестановок символов в строке, средний рейтинг фильмов, алгоритм объединения в пары, алгоритм «сшивания», алгоритм выбора, алгоритм сортировки, кратчайший путь между узлами, программа Weasel, игра «Жизнь»),
• конкурентность, шаблоны проектирования (проверка пароля, генерация паролей...),
• сериализация данных (XML, JSON, создание PDF из коллекции изображений),
• архивы, изображения и базы данных (поиск в ZIP-архиве, создание PNG-файла, работа с SQLite),
• криптография (шифры, Base64, хеш-сумма файла...), сети и службы.

Фрэнк М. Каррано, Джанет Дж. Причард. Абстракция данных и решение задач на C++. Стены и зеркала

848 страниц. Вильямс, 2003

Franks M. Carrano, Janet J. Prichard. Data Abstraction and Problem Solving with C++. Addison-Wesley, 2002

Обложка гласит: «По мотивам книги „Стены и зеркала“ Пола Хелмана и Роберта Верроффа». Авторы признаются, что их труд полностью повторяет техническое и литературное содержание, примеры, рисунки и упражнения оригинала. Хотя что-то они добавили.

В книге две части: методы решения задач (рекурсия, абстракция, связные списки), решение задач с помощью абстрактных типов данных (стеки, очереди, эффективность алгоритмов, сортировка, деревья, таблиц, очереди с приоритетом, графы). Принципы программирования и разработки программного обеспечения.

Приложения: основы языка C++, ASCII-коды, заголовочные файлы и стандартные функции, метод математической индукции, стандартные шаблонные классы, операторы языка C++.

Александр Александрович Кубенский. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на C++

464 страницы. БХВ, 2004

Автор также написал и другие книги, например, «Создание и обработка структур данных в примерах на Java». На обратной стороне обложке написано про опыт работы в компаниях Motorola, Borland и других.

Содержание:

• Способы представления структур данных (массивы, списки, деревья, множества, графы)
• Базовые алгоритмы
• Обработка текстов
• Символьные преобразования
• Алгоритмы распределения памяти
• Алгоритмы обработки графов
• Обмен сообщениями и обработка сообщений
• Функции как носитель информации

Из введения:

В первой главе, где излагаются способы представления структур данных, тоже демонстрируется «авторский подход к организации структур данных».

Cписками инициализации автор не пользуется, именование иногда сбивает с толку (tail() — почему-то доступ к последнему элементу, а не «хвосту» списка, то есть части, которая следует после «головы»; заказ памяти вместо выделения или аллокации). Стилю кодирования и приёмам вряд ли стоит учиться.

graph = new bool*[vertexNumber = n];

Вызывает вопросы методология. Сначала — шаблонный класс массива (аналог std::vector), затем — нешаблонный класс IntList, а потом — снова шаблонный класс дерева.

Автор вводит представления графов (некоторые из них экзотические) и их необычные названия: S-граф (массив, в котором каждому номеру вершины сопоставляется множество номеров вершин, в которые входят дуги, исходящие из неё), M-граф (матрица смежности), L-граф (списки смежности), A-граф (arc — дуга; список дуг).

У «базовых алгоритмов» вводится понятие итератора, только он почему-то в конструкторе принимает ссылку на список и указывает на начальный элемент. Создать итератор на другой элемент почему-то нельзя.

В главе о символьных вычислениях ожидаемо появляется шаблон проектирования «посетитель», только он реализовывается не так, как пишет «банда четырёх».

void Simplifier::visit(Operator * opNode) {

  if (opNode->what() != BINARY) {

    // Упрощаем только бинарные операторы

    result = opNode;

  } else {

    Binary * binOperator = (Binary *)opNode;

    ...

  }

  ...

}

Глава про алгоритмы распределения памяти, конечно, устарела по форме, но не по содержанию. Хотя бывают и более интересные сборники алгоритмов.

От главы про обмен сообщениями и обработку сообщений ожидаешь чего-то большего, чем просто вычисление конечных сумм и чисел Фибоначчи. Что это было — загадка.

В главе «Функции как носитель информации» речь идёт о множествах, о реализации умных указателей (здесь автор уже стал использовать списки инициализации), о решете Эратосфена (проверка чисел на простоту) и ещё каких-то вещах, смысл которых (как и названия главы) куда-то ускользает.

Анализу сложности по времени и по памяти в книге внимания почти не уделяется. Получился сборник «серединка на половинку».

Максим Владимирович Мозговой. C++. Мастер-класс. 85 нетривиальных проектов, решений и задач

272 страницы. Наука и Техника, 2007

Много интересных тем, но код иногда завязан на C++ Builder.

• Структуры данных (вычисление формул без грамматического разбора, разреженные матрицы, бинарные деревья — игра «животные», генератор формул, расчёт цепи),
• математические задачи (интерполяция по Лагранжу, сведение химических уравнений к алгебраическим, преобразования фигур, расчёт траекторий),
• графы (анализ проблемы останова, разрешение взаимных блокировок...),
• рекурсия (фракталы, головоломки, эвристический поиск),
• визуализация (планетарная система, простой трёхмерный мир, простой музыкальный редактор, скринсейвер...), обучающиеся программы (KNN, классификация и кластеризация документов, крестики-нолики...),
• моделирование вероятностных процессов (генерация заголовков, текстов, вычисление \(\pi\), моделирование распределений — прокси-сервер, биологические модели...),
• текстовые данные (расстояние Левенштейна, поиск по шаблону, красивое форматирование...),
• различные алгоритмы (эндшпиль, «Сапёр», обрезка и поворот изображения, сжатие монохромных изображений, стеганография, расписание игр, исследование структуры опроса),
• архитектура программного обеспечения (паззл, ball game, логические схемы, анализ шахматных партий...).

Роберт Седжвик. Фундаментальные алгоритмы на C++

1056 страниц. Вильямс, 2016/2019

Robert Sedgewick. Algorithms in C++. Addison-Wesley, 2009

Предыдущее издание (оригинал 1999 года) было двухтомником, в первом томе шли части с первой по четвёртую, отдельным томом издавалась пятая часть. В предисловии консультант по C++ пишет, что они с автором старались сосредоточиться на алгоритмах, а не деталях языка, потому использовали не все возможности, например, инициализацию в конструкторах, std::string, большинство контейнеров и «умные» указатели.

У того же автора есть книги по алгоритмам на языках C и Java (в соавторстве).

Часть 1. Анализ. Введение, принципы анализа алгоритмов.

Часть 2. Структуры данных. Элементарные структуры данных, абстрактные типы данных, рекурсия и деревья.

Часть 3. Сортировка. Элементарные методы сортировки, быстрая сортировка, слияние и сортировка слиянием, очереди по приоритетам и пирамидальная сортировка, поразрядная сортировка, методы сортировки специального назначения (чётно-нечётная сортировка слиянием Бэтчера, сети сортировки, внешняя сортировка, различные реализации сортировки-слияния, параллельная процедура сортировки-слияния).

Часть 4. Поиск. Таблицы символов и деревья бинарного поиска, сбалансированные деревья, хеширование, поразрядный поиск, внешний поиск.

Часть 5. Алгоритмы на графах. Виды графов и их свойства, поиск на графе, орграфы и ориентированные ациклические графы, минимальные остовные деревья, кратчайшие пути, потоки в сетях.

Уильям Топп, Уильям Форд. Структуры данных в C++

816 страниц. Бином, 1999

William Topp, William Ford. Data Structures with C++. Prentice-Hall, 1996

Базовые типы данных, абстрактные типы данных (классы, примеры, массивы, пример — треугольная матрица), классы коллекций, стеки и очереди, абстрактные операторы (на примере рациональных чисел), параметризованные типы данных (вычисление инфиксного выражения), динамическая память (массивы, строки, множества, решето Эратосфена), связные списки, рекурсия (бинарный поиск, комбинаторика, лабиринт), деревья, наследование и абстрактные классы, более сложные нелинейные структуры (пирамид, AVL-деревья, графы), сортировка и поиск.

Приложение: ответы на некоторые упражнения.

Арт Фридман, Ларс Кландер, Марк Михаэлис, Герберт Шилдт (Херб Шильдт). C/C++. Алгоритмы и приёмы программирования

560 страниц. Бином, 2003

Art Friedman, Lars Klander, Mark Michaelis, Herb Schildt. C/C++ Annotated Archives. McGraw-Hill Osborne Media, 1999

Репринт книги «C/C++. Архив программ» (2001).

Сортировка, связные списки, двоичные деревья, смешанные таблиц и разреженные массивы, управление памятью (аллокаторы), файлы и каталоги, шифрование, «управление исходным кодом» (сканирование кода, вывод его в другом формате, то есть программа выполняет синтаксический разбор кода и другие вещи), работа с сетью (WinSock API, сокеты), финансовые, статистические расчёты, фракталы, реализация интерпретаторов (Small Basic), STL, CGI.