动手学数据结构与算法

第 1章　绪论 1
11　问题引入 1
12　什么是数据结构 3
121　数据的逻辑结构 3
122　数据的存储结构 4
123　数据的操作 5
13　算法分析 5
131　算法的基本概念 5
132　时间复杂度 6
133　空间复杂度 11
14　算法优化 11
141　时间复杂度为O(n3)的算法11
142　时间复杂度为O(n2)的算法 12
143　时间复杂度为O(nlogn)的算法 13
144　时间复杂度为O(n)的算法 15
15　大型应用实现：火车票管理系统总览 16
16　小结 17
17　习题 18
第 2章　线性表 19
21　问题引入 19
22　线性表的定义 20
23　线性表的实现 20
231　线性表的顺序实现 20
232　线性表的链接实现 23
24　线性表的简单应用 27
241　大整数处理 27
242　多项式求和 32
25　大型应用实现：列车运行计划管理类 34
26　小结 36
27　习题 37
第3章　队列与栈 38
31　问题引入 38
32　队列 38
321　队列的定义 39
322　队列的顺序实现 39
323　队列的链接实现 44
324　队列的简单应用：排队洗衣 45
33　栈 47
331　栈的定义 47
332　栈的顺序实现 48
333　栈的链接实现 50
334　栈的简单应用：括号匹配 52
34　大型应用实现：排队交易类 53
35　小结 55
36　习题 55
第4章　树与优先级队列 57
41　问题引入 57
42　树的定义 57
43　二叉树 59
431　二叉树的定义 59
432　二叉树的顺序实现 63
433　二叉树的链接实现 63
434　 二叉树的简单应用：哈夫曼编码
和哈夫曼树 69
44　优先级队列 74
441　优先级队列的定义 74
442　优先级队列的实现 74
443　 优先级队列的简单应用：
任务调度 81
45　大型应用实现：带优先级的排队
交易类 82
46　小结 83
47　习题 83
第5章　集合与静态查找表 85
51　问题引入 85
52　集合的定义 85
53　静态查找表 86
531　无序查找的实现 86
532　有序查找的实现 87
54　集合的简单应用：并查集 89
55　大型应用实现：列车运行图类（1） 92
56　小结 94
57　习题 94
第6章　动态查找表 96
61　问题引入 96
62　动态查找表的定义 96
63　二叉查找树 97
631　二叉查找树的定义 97
632　二叉查找树的实现 97
64　AVL树102
641　AVL树的定义 102
642　AVL树的实现 104
65　红黑树 112
651　红黑树的定义 112
652　红黑树的实现 114
66　哈希表 123
661　哈希表的定义 124
662　哈希表的实现 124
67　大型应用实现：旅客管理类129
68　小结 131
69　习题 132
第7章　排序 134
71　问题引入 134
72　排序的定义 134
73　插入排序 135
731　直接插入排序 135
732　二分插入排序 136
733　希尔排序 136
74　选择排序 138
741　直接选择排序 138
742　堆排序 139
75　交换排序 141
751　冒泡排序 141
752　快速排序 142
76　归并排序 144
77　基数排序 145
78　小结 147
79　习题 148
第8章　外部查找与排序 150
81　问题引入 150
82　外部查找表的定义 150
83　B树 151
831　B树的定义 151
832　B树的实现 152
84　B 树 155
841　B 树的定义 155
842　B 树的实现 158
85　外排序 174
851　外排序的定义 174
852　外排序的实现 174
86　大型应用实现：余票管理类与行程
管理类 177
87　小结 183
88　习题 183
第9章　图 185
91　问题引入 185
92　图的定义 185
93　图的实现 188
931　邻接矩阵 188
932　邻接表 191
94　图的遍历 194
941　深度优先搜索（DFS） 194
942　广度优先搜索（BFS） 196
95　图的遍历的简单应用 197
951　图的连通性 197
952　欧拉回路 198
953　拓扑排序 202
954　关键路径 204
96　大型应用实现：列车运行图类（2） 206
97　小结 209
98　习题 209
第 10章　最小生成树与最短路径 211
101　问题引入 211
102　最小生成树 211
1021　最小生成树的定义 211
1022　克鲁斯卡尔算法 212
1023　普里姆算法 214
103　单源最短路径 217
1031　非加权图的单源最短路径 217
1032　加权图的单源最短路径 219
1033　 带有负权值图的单源最短
路径 221
1034　无环图的单源最短路径 222
104　所有顶点对的最短路径 223
105　大型应用实现：列车运行图类（3） 224
106　小结 226
107　习题 226
第 11章　算法设计思想 228
111　枚举法 228
112　贪婪算法 229
113　分治法 230
114　回溯法 233
115　动态规划 235
116　随机算法 237
117　算法综合分析：外卖配送任务 238
118　小结 240
119　习题 240
附录A　书中部分命题的证明 242
A1　证明二叉树的性质 242
A2　 证明两种遍历方法是否能够唯一确定
一棵二叉树 244
A3　证明AVL树的高度是对数级别的 245
A4　 证明AVL树插入后至多只需要调整一个
结点即可恢复平衡 246
A5　 证明快速排序的平均时间复杂度为
O(nlogn) 246
A6　 证明归并排序的时间复杂度为
O(nlogn) 247
附录B　电子资源与运行环境配置 248
B1　动手练平台 248
B2　电子资料仓库 248
B3　本地环境搭建和仓库代码运行 249
B31　Linux环境 249
B32　Windows环境 255
B33　macOS环境 260