ВУЗ:
Составители:
143
ОГЛАВЛЕНИЕ
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1. Линейные информационные структуры . . . . . . . . . . . . . . . . . . . . . . .
4
2. Последовательное распределение памяти при хранении линей
ных
списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3. Связанное распределение памяти при хранении линейных спи-
сков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4. Массивы и ортогональные списки . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5. Деревья и представление деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6. Прохождение деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7. Представление лесов бинарными деревьями . . . . . . . . . . . . . . . . . . .
45
8. Использование понятия дерева для решения прикладных задач . . .
50
9. Сложность алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
10. Сортировка. Внутренняя сортировка. Сортировка подсчётом . . . . .
59
11. Сортировка вставками . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
12. Обменная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
13. Сортировка посредством выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
14. Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
15. Распределяющая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
16. Внешняя сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
17. Многопутевое слияние и выбор с замещением . . . . . . . . . . . . . . . . .
97
18. Поиск. Последовательный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
19. Поиск в упорядоченной таблице . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
20. Поиск по бинарному дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
21. Сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
22. Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
119
Ответы к упражнениям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
124
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
