Введение 8

Целевая аудитория 9

Глава 1. Основные понятия 14

Что такое алгоритмы? 15

Анализ скорости выполнения алгоритмов 16

Пространство — время 16

Оценка с точностью до порядка 17

Поиск сложных частей алгоритма 18

Сложность рекурсивных алгоритмов 20

Многократная рекурсия 21

Косвенная рекурсия 21

Требования рекурсивных алгоритмов к объему памяти 22

Наихудший и усредненный случай 23

Часто встречающиеся функции оценки порядка сложности 24

Логарифмы 24

Реальные условия — насколько быстро? 25

Обращение к файлу подкачки 26

Псевдоуказатели, ссылки на объекты и коллекции 27

Резюме 29

Глава 2. Списки 30

Знакомство со списками 30

Простые списки 31

Коллекции 31

Список переменного размера 32

Класс SimpleList 35

Неупорядоченные списки 36

Связные списки 40

Добавление элементов к связному списку 43

Удаление элементов из связного списка 43

Уничтожение связного списка 44

Сигнальные метки 45

Инкапсуляция связных списков 46

Доступ к ячейкам 47

Разновидности связных списков 48

Циклические связные списки 49

Проблема циклических ссылок 50

Двусвязные списки 50

Потоки 53

Другие связные структуры 56

Псевдоуказатели 56

Резюме 59

Глава 3. Стеки и очереди 59

Стеки 60

Множественные стеки 62

Очереди 63

Циклические очереди 65

Очереди на основе связных списков 69

Применение коллекций в качестве очередей 69

Приоритетные очереди 70

Многопоточные очереди 72

Резюме 74

Глава 4. Массивы 74

Треугольные массивы 75

Диагональные элементы 77

Нерегулярные массивы 78

Прямая звезда 78

Нерегулярные связные списки 79

Разреженные массивы 80

Индексирование массива 82

Очень разреженные массивы 84

Резюме 86

Глава 5. Рекурсия 86

Что такое рекурсия? 86

Рекурсивное вычисление факториалов 87

Анализ времени выполнения программы 89

Рекурсивное вычисление наибольшего общего делителя 90

Анализ времени выполнения программы 90

Рекурсивное вычисление чисел Фибоначчи 92

Анализ времени выполнения программы 93

Рекурсивное построение кривых Гильберта 94

Анализ времени выполнения программы 96

Рекурсивное построение кривых Серпинского 98

Анализ времени выполнения программы 100

Опасности рекурсии 101

Бесконечная рекурсия 101

Потери памяти 102

Необоснованное применение рекурсии 103

Когда нужно использовать рекурсию 104

Хвостовая рекурсия 105

Нерекурсивное вычисление чисел Фибоначчи 107

Устранение рекурсии в общем случае 110

Нерекурсивное построение кривых Гильберта 114

Нерекурсивное построение кривых Серпинского 117

Резюме 121

Глава 6. Деревья 121

Определения 122

Представления деревьев 123

Полные узлы 123

Списки потомков 124

Представление нумерацией связей 126

Полные деревья 129

Обход дерева 130

Упорядоченные деревья 135

Добавление элементов 135

Удаление элементов 136

Обход упорядоченных деревьев 140

Деревья со ссылками 141

Работа с деревьями со ссылками 144

Квадродеревья 145

Изменение MAX_PER_NODE 151

Использование псевдоуказателей в квадродеревьях 152

Восьмеричные деревья 152

Резюме 153

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

Сбалансированность дерева 153

АВЛ‑деревья 154

Удаление узла из АВЛ‑дерева 161

Б‑деревья 166

Производительность Б‑деревьев 167

Вставка элементов в Б‑дерево 168

Удаление элементов из Б‑дерева 168

Разновидности Б‑деревьев 170

Улучшение производительности Б‑деревьев 172

Балансировка для устранения разбиения блоков 172

Вопросы, связанные с обращением к диску 173

База данных на основе Б+дерева 176

Резюме 179