图解Java数据结构与算法（微课视频版）

的顺序存储 22
2.2.2顺序表的基本运算 23
2.2.3基本操作性能分析 26
2.2.4顺序表应用举例 27
2.3线性表的链式表示与实现 30
2.3.1单链表的存储结构 30
2.3.2单链表上的基本运算 32
2.3.3单链表应用举例 36
2.3.4循环单链表 38
2.3.5双向链表 41
2.4一元多项式的表示与相乘 44
2.4.1一元多项式的表示 44
2.4.2一元多项式相乘 45
2.5小结 49
第3章栈与队列 50
3.1栈的表示与实现 50
3.1.1栈的定义 50
3.1.2栈的抽象数据类型 51
3.1.3顺序栈 52
3.1.4链栈 56
3.2栈的应用 59
3.2.1数制转换 59
3.2.2行编辑程序 60
3.2.3算术表达式求值 61
3.3栈与递归 67
3.3.1递归 68
3.3.2消除递归 71
3.4队列的表示与实现 73
3.4.1队列的定义 73
3.4.2队列的抽象数据类型 73
3.4.3顺序队列 74
3.4.4顺序循环队列 76
3.4.5双端队列 79
3.4.6链式队列 79
3.4.7链式队列的实现 81
3.5队列在杨辉三角中的应用 82
3.5.1什么是杨辉三角 82
3.5.2构造队列 83
3.5.3杨辉三角队列的实现 83
3.6小结 85
第4章串、数组与广义表 86
4.1串的定义及抽象数据类型 86
4.1.1什么是串 86
4.1.2串的抽象数据类型 87
4.2串的存储表示 88
4.2.1串的顺序存储结构 88
4.2.2串的链式存储结构 89
4.3串的模式匹配 90
4.3.1朴素模式匹配算法——Brute-Force 90
4.3.2改进算法—KMP算法 92
4.3.3模式匹配应用举例 98
4.4数组的定义及抽象数据类型 99
4.4.1数组的基本概念 99
4.4.2数组的抽象数据类型 100
4.4.3数组的顺序存储结构 100
4.4.4特殊矩阵的压缩存储 101
4.4.5稀疏矩阵的压缩存储及典型应用 104
4.5广义表 111
4.5.1什么是广义表 111
4.5.2广义表的抽象数据类型 112
4.5.3广义表的头尾链表表示 113
4.5.4广义表的扩展线性链表表示 113
4.6小结 115
第5章树和二叉树 116
5.1树的定义和抽象数据类型 116
5.1.1树的定义 116
5.1.2树的逻辑表示 118
5.2二叉树的定义、性质和抽象数据类型 118
5.2.1二叉树的定义 119
5.2.2二叉树的性质 120
5.2.3二叉树的抽象数据类型 122
5.2.4二叉树的存储表示 123
5.3二叉树的遍历 125
5.3.1二叉树遍历的定义 126
5.3.2二叉树的先序遍历 126
5.3.3二叉树的中序遍历 128
5.3.4二叉树的后序遍历 130
5.4二叉树的线索化 132
5.4.1二叉树的线索化定义 132
5.4.2二叉树的线索化算法实现 133
5.4.3线索二叉树的遍历 135
5.4.4线索二叉树的应用举例 137
5.5树、森林与二叉树 139
5.5.1树的存储结构 139
5.5.2树转换为二叉树 142
5.5.3森林转换为二叉树 143
5.5.4二叉树转换为树和森林 143
5.5.5树和森林的遍历 144
5.6并查集 145
5.6.1并查集的定义 145
5.6.2并查集的实现 146
5.6.3并查集的应用 149
5.7哈夫曼树 151
5.7.1哈夫曼树的定义 151
5.7.2哈夫曼编码 152
5.7.3哈夫曼编码算法的实现 153
5.8小结 158
第6章图 159
6.1图的定义与相关概念 159
6.1.1图的定义 159
6.1.2图的相关概念 160
6.1.3图的抽象数据类型 162
6.2图的存储结构 163
6.2.1邻接矩阵表示法 163
6.2.2邻接表表示法 168
6.2.3十字链表 172
6.2.4邻接多重表 173
6.3图的遍历 174
6.3.1图的深度优先遍历 174
6.3.2图的广度优先遍历 178
6.4图的连通性问题 179
6.4.1无向图的连通分量与生成树 180
6.4.2最小生成树 181
6.5有向无环图 187
6.5.1AOV网与拓扑排序 187
6.5.2AOE网与关键路径 190
6.6最短路径 196
6.6.1从某个顶点到其他顶点的最短路径 196
6.6.2每一对顶点之间的最短路径 202
6.7小结 206
第7章查找 208
7.1查找的基本概念 208
7.2静态查找 209
7.2.1顺序表的查找 209
7.2.2有序顺序表的查找 211
7.2.3索引顺序表的查找 213
7.3动态查找 215
7.3.1二叉排序树 215
7.3.2平衡二叉树 221
7.4B-树与B+树 227
7.4.1B-树 227
7.4.2B+树 233
7.5哈希表 233
7.5.1哈希表的定义 234
7.5.2哈希函数的构造方法 234
7.5.3处理冲突的方法 235
7.5.4哈希表的查找与分析 237
7.5.5哈希表应用举例 238
7.6小结 242
第8章排序 243
8.1排序的基本概念 243
8.2插入排序 244
8.2.1直接插入排序 244
8.2.2折半插入排序 246
8.2.3希尔排序 246
8.2.4插入排序应用举例 247
8.3选择排序 248
8.3.1简单选择排序 248
8.3.2堆排序 249
8.4交换排序 254
8.4.1冒泡排序 254
8.4.2快速排序 256
8.4.3交换排序应用举例 258
8.5归并排序 261
8.6基数排序 263
8.6.1基数排序算法 263
8.6.2基数排序应用举例 266
8.7小结 269
第9章分治算法 271
9.1分治算法的基本思想 271
9.2求最大子序列的和 274
9.3求x的n次幂 277
9.4众数问题 278
9.5求n个数中的最大者和最小者 280
9.6整数划分问题 283
9.7大整数乘法 285
9.8小结 290
第10章贪心算法 291
10.1贪心算法的思想 291
10.2找零钱问题 293
10.3背包问题 295
10.4删数问题 299
10.5加油站问题 301
10.6小结 302
第11章回溯算法 303
11.1回溯算法的基本思想 303
11.1.1问题的解空间 304
11.1.2回溯算法的基本思想 305
11.2装载问题 307
11.3旅行商问题 310
11.4和式分解问题 314
11.5小结 317
参考文献 318
课后习题（电子版见下载） 319