Введение

Глава 1. Основные понятия
Что такое алгоритм
Анализ скорости выполнения алгоритмов
Ресурсы и время
Оценка с точностью до порядка
Поиск проблемных частей алгоритма
Сложность рекурсивных алгоритмов
Наихудший и усредненный случай
Функции оценки порядка сложности
Логарифмы
Скорость работы алгоритма в реальных условиях
Обращение к файлу подкачки
Псевдоуказатели, ссылки на объекты и коллекции
Резюме

Глава 2. Списки
Основные вопросы главы
Простые списки
Коллекции
Список переменного размера
Класс SimpleList
Неупорядоченные списки
Связанные списки
Добавление элементов
Удаление элементов
Уничтожение связанного списка
Сигнальные метки
Инкапсуляция связанных списков
Доступ к ячейкам
Разновидности связанных списков
Циклические связанные списки
Проблема циклических ссылок
Двусвязанные списки
Потоки
Другие связанные структуры
Псевдоуказатели
Резюме

Глава 3. Стеки и очереди
Стеки
Множественные стеки
Очереди
Циклические очереди
Очереди на основе связанных списков
Применение коллекций в качестве очередей
Очереди с приоритетами
Многопоточные очереди
Резюме

Глава 4. Массивы
Треугольные массивы
Диагональные элементы
Нерегулярные массивы
Линейное представление с указателями
Нерегулярные связанные списки
Разреженные массивы
Индексирование массива
Очень разреженные массивы
Резюме

Глава 5. Рекурсия
Что такое рекурсия
Рекурсивное вычисление факториалов
Анализ времени выполнения программы
Рекурсивное вычисление наибольшего общего делителя
Анализ времени выполнения программы
Рекурсивное вычисление чисел Фибоначчи
Анализ времени выполнения программы
Рекурсивное построение кривых Гильберта
Анализ времени выполнения программы
Рекурсивное построение кривых Серпинского
Анализ времени выполнения программы
Недостатки рекурсии
Бесконечная рекурсия
Потери памяти
Необоснованное применение рекурсии
Когда нужно использовать рекурсию
Хвостовая рекурсия
Нерекурсивное вычисление чисел Фибоначчи
Устранение рекурсии в общем случае
Нерекурсивное построение кривых Гильберта
Нерекурсивное построение кривых Серпинского
Резюме

Глава 6. Деревья
Основные термины
Представления деревьев
Полные узлы
Списки потомков
Представление нумерацией связей
Полные деревья
Обход дерева
Упорядоченные деревья
Добавление элементов
Удаление элементов
Обход упорядоченных деревьев
Деревья со ссылками
Особенности работы
Q-деревья
Изменение количества элементов в узле
Использование псевдоуказателей
Восьмеричные деревья
Резюме

Глава 7. Сбалансированные деревья
Сбалансированность дерева
АВЛ-деревья
Добавление узла
Удаление узла
Б-деревья
Производительность Б-деревьев
Вставка элементов
Удаление элементов
Разновидности Б-деревьев
Увеличение производительности Б-деревьев
Балансировка
Вопросы, связанные с обращением к диску
База данных на основе Б+дерева
Резюме

Глава 8. Деревья решений
Поиск в деревьях игры
Минимаксный поиск
Оптимизация поиска
Поиск нестандартных решений
Метод ветвей и границ
Эвристики
Сложные задачи
Задача о выполнимости
Задача о разбиении
Задача поиска Гамильтонова пути
Задача коммивояжера
Задача о пожарных депо
Краткая характеристика сложных задач
Резюме

Глава 9. Сортировка
Общие принципы
Таблицы указателей
Объединение и сжатие ключей
Примеры программ
Сортировка выбором
Перемешивание
Сортировка вставкой
Вставка в связанных списках
Пузырьковая сортировка
Быстрая сортировка
Сортировка слиянием
Пирамидальная сортировка
Пирамиды
Очереди с приоритетами
Алгоритм пирамидальной сортировки
Сортировка подсчетом
Блочная сортировка
Блочная сортировка с применением связанного списка
Блочная сортировка на основе массива
Резюме

Глава 10. Поиск
Примеры программ
Поиск методом полного перебора
Поиск в упорядоченных списках
Поиск в связанных списках
Двоичный поиск
Интерполяционный поиск
Строковые данные
Следящий поиск
Интерполяционный следящий поиск
Резюме

Глава 11. Хеширование
Связывание
Преимущества и недостатки связывания
Блоки
Хранение хеш-таблиц на диске
Связывание блоков
Удаление элементов
Преимущества и недостатки применения блоков
Открытая адресация
Линейная проверка
Квадратичная проверка
Псевдослучайная проверка
Удаление элементов
Резюме

Глава 12. Сетевые алгоритмы
Основные термины
Представления сети
Оперирование узлами и связями
Обходы сети
Наименьший каркас дерева
Кратчайший маршрут
Расстановка меток
Коррекция меток
Варианты поиска кратчайшего маршрута
Приложения, использующие метод поиска кратчайшего маршрута
Максимальный поток
Сферы применения
Резюме

Глава 13. Объектно-ориентированные методы
Преимущества ООП
Инкапсуляция
Полиморфизм
Наследование и повторное использование
Парадигмы ООП
Управляющие объекты
Контролирующий объект
Итератор
Дружественный класс
Интерфейс
Фасад
Порождающий объект
Единственный объект
Преобразование в последовательную форму
Парадигма Модель/Вид/Контроллер
Резюме

Приложение 1. Архив с примерами

Приложение 2. Список примеров программ

Алфавитный указатель