Смекни!
smekni.com

VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования (стр. 1 из 72)

Введение.................................................................................................. 8

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

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

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

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

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

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

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

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

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

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

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

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

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

Логарифмы........................................................................................ 25

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

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

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

Резюме................................................................................................... 29

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

Знакомство со списками.................................................................... 31

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

Коллекции.......................................................................................... 32

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

Класс SimpleList................................................................................ 36

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

Связные списки................................................................................... 41

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

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

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

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

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

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

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

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

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

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

Потоки............................................................................................... 53

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

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

Резюме................................................................................................... 59

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

Стеки..................................................................................................... 60

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

Очереди................................................................................................. 63

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

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

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

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

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

Резюме................................................................................................... 74

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

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

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

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

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

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

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

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

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

Резюме................................................................................................... 86

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

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

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

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

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

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

Рекурсивное вычисление чисел Фибоначчи................................... 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

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

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

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

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

Изменение MAX_PER_NODE......................................................... 151

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

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

Резюме................................................................................................. 152

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

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

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

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

Б‑деревья............................................................................................ 166

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

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

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

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

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

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

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

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

Резюме................................................................................................. 179

Глава 8. Деревья решений.................................................................. 179

Поиск в деревьях игры..................................................................... 180

Минимаксный поиск........................................................................ 181

Улучшение поиска в дереве игры.................................................. 185

Поиск в других деревьях решений................................................. 187

Метод ветвей и границ.................................................................... 187

Эвристики........................................................................................ 191

Другие сложные задачи.................................................................... 207

Задача о выполнимости.................................................................. 207

Задача о разбиении......................................................................... 208

Задача поиска Гамильтонова пути................................................. 209

Задача коммивояжера..................................................................... 210

Задача о пожарных депо................................................................. 211

Краткая характеристика сложных задач........................................ 212

Резюме................................................................................................. 212

Глава 9. Сортировка........................................................................... 213

Общие соображения......................................................................... 213

Таблицы указателей........................................................................ 213

Объединение и сжатие ключей....................................................... 215

Примеры программ........................................................................... 217

Сортировка выбором........................................................................ 219

Рандомизация.................................................................................... 220

Сортировка вставкой....................................................................... 221

Вставка в связных списках.............................................................. 222

Пузырьковая сортировка................................................................. 224

Быстрая сортировка......................................................................... 227

Сортировка слиянием....................................................................... 232

Пирамидальная сортировка............................................................ 234

Пирамиды........................................................................................ 235

Приоритетные очереди................................................................... 237

Алгоритм пирамидальной сортировки.......................................... 240

Сортировка подсчетом..................................................................... 241

Блочная сортировка.......................................................................... 242