第1章 绪论 1
1.1数据结构的概念及分类 1
1.1.1为什么要学习数据结构 1
1.1.2与数据结构相关的基本术语 2
1.1.3数据结构的分类 5
1.1.4数据结构的存储结构 6
1.1.5定义在数据结构上的操作 7
1.1.6“好”数据结构 7
1.2使用C语言描述数据结构 7
1.2.1 C语言的数据类型 8
1.2.2算法的控制结构 9
1.2.3算法的函数结构 10
1.2.4动态存储分配 12
1.2.5逻辑和关系运算的约定 12
1.2.6输入与输出 13
1.3算法和算法设计 13
1.3.1算法的定义和特性 13
1.3.2算法的设计步骤 14
1.3.3算法设计的基本方法 15
1.4算法分析与度量 18
1.4.1算法的评价标准 18
1.4.2算法的时间和空间复杂度度量 18
1.4.3算法的渐近分析 21
小结 24
习题 24
第2章 线性表 27
2.1线性表 27
2.1.1线性表的定义和特点 27
2.1.2线性表的主要操作 28
2.2顺序表 29
2.2.1顺序表的定义和特点 29
2.2.2顺序表的结构定义 30
2.2.3顺序表查找操作的实现 31
2.2.4顺序表插入和删除操作的实现 32
2.2.5顺序表的应用：集合运算 34
2.3单链表 35
2.3.1单链表的定义和特点 35
2.3.2单链表的结构定义 36
2.3.3单链表中的插入与删除 36
2.3.4带头结点的单链表 40
2.3.5单链表的遍历与创建 42
2.3.6单链表的应用：集合运算 44
2.3.7循环链表 46
2.3.8双向链表 50
2.3.9静态链表 53
2.4顺序表与线性链表的比较 54
2.5线性表的应用：一元多项式及其运算 56
2.5.1一元多项式的表示 56
2.5.2多项式的结构定义 57
2.5.3多项式的加法 59
2.5.4扩展阅读：多项式的乘法 60
小结 62
习题 63
第3章 栈和队列 66
3.1栈 66
3.1.1栈的概念 66
3.1.2顺序栈 67
3.1.3扩展阅读：多栈处理 70
3.1.4链式栈 73
3.1.5扩展阅读：栈的混洗 74
3.2队列 76
3.2.1队列的概念 76
3.2.2循环队列 76
3.2.3链式队列 80
3.3栈的应用 82
3.3.1数制转换 82
3.3.2括号匹配 83
3.3.3表达式的计算与优先级处理 84
3.3.4栈与递归的实现 88
3.4队列的应用 91
3.5在算法设计中使用递归 92
3.5.1汉诺塔问题与分治法 92
3.5.2直接把递归过程改为非递归过程 94
3.5.3扩展阅读：递归过程的非递归模拟算法 95
3.5.4迷宫问题与回溯法 98
3.5.5计算组合数与动态规划 101
3.6扩展阅读：双端队列 102
3.6.1双端队列的概念 102
3.6.2输入受限的双端队列 103
3.6.3输出受限的双端队列 104
3.6.4双端队列的存储表示 104
3.7扩展阅读：优先队列 106
3.7.1优先队列的概念 106
3.7.2优先队列的实现 107
小结 108
习题 108
第4章 数组、串和广义表 112
4.1数组 112
4.1.1一维数组 112
4.1.2多维数组 114
4.2特殊矩阵的压缩存储 116
4.2.1对称矩阵的压缩存储 117
4.2.2三对角矩阵的压缩存储 118
4.2.3扩展阅读：w对角矩阵的压缩存储 119
4.3稀疏矩阵 120
4.3.1稀疏矩阵的概念 120
4.3.2稀疏矩阵的顺序存储表示 121
4.3.3稀疏矩阵的链表表示 124
4.4字符串 125
4.4.1字符串的概念 126
4.4.2字符串的初始化和赋值 126
4.4.3自定义字符串的存储表示 128
4.4.4串的模式匹配 132
4.5广义表 140
4.5.1广义表的概念 140
4.5.2广义表的性质 141
4.5.3广义表的链接表示 141
4.5.4扩展阅读：三元多项式的表示 147
小结 148
习题 149
第5章 树与二叉树 152
5.1树的基本概念 152
5.1.1树的定义和术语 152
5.1.2树的基本操作 154
5.2二叉树及其存储表示 155
5.2.1二叉树的概念 155
5.2.2二叉树的性质 156
5.2.3二叉树的主要操作 158
5.2.4二叉树的顺序存储表示 159
5.2.5二叉树的链表存储表示 160
5.3二叉树的遍历 161
5.3.1二叉树遍历的递归算法 162
5.3.2递归遍历算法的应用举例 163
5.3.3二叉树遍历的非递归算法 166
5.3.4利用队列实现二叉树的层次序遍历 169
5.3.5非递归遍历算法的应用举例 170
5.3.6二叉树的计数 171
5.4线索二叉树 174
5.4.1线索二叉树的概念 174
5.4.2线索二叉树的种类 175
5.4.3中序线索二叉树的建立和遍历 176
5.4.4先序与后序线索二叉树 178
5.5树与森林 180
5.5.1树的存储表示 180
5.5.2森林与二叉树的转换 184
5.5.3树与森林的深度优先遍历 185
5.5.4树与森林的广度优先遍历 187
5.5.5树遍历算法的应用举例 188
5.6 Huffman树 190
5.6.1带权路径长度的概念 190
5.6.2 Huffman树的概念 191
5.6.3扩展阅读：最优判定树 194
5.6.4 Huffman编码 196
5.7堆 198
5.7.1小根堆和大根堆 198
5.7.2堆的建立 199
5.7.3堆的插入 201
5.7.4堆的删除 202
5.8等价类与并查集 202
5.8.1等价关系与等价类 202
5.8.2确定等价类的方法 203
5.8.3并查集的定义及其实现 203
5.8.4并查集操作的分析和改进 205
5.9扩展阅读：八皇后问题与树的剪枝 207
5.9.1八皇后问题的提出 207
5.9.2八皇后问题的状态树 208
5.9.3八皇后问题算法 210
小结 211
习题 212
第6章图 216
6.1图的基本概念 216
6.1.1与图有关的若干概念 216
6.1.2图的基本操作 219
6.2图的存储结构 221
6.2.1图的邻接矩阵表示 221
6.2.2图的邻接表表示 225
6.2.3邻接矩阵表示与邻接表表示的比较 229
6.2.4图的邻接多重表和十字链表表示 230
6.3图的遍历 231
6.3.1深度优先搜索 232
6.3.2广度优先搜索 234
6.3.3连通分量 235
6.3.4双连通图 237
6.3.5有向图的强连通分量 238
6.4最小生成树 240
6.4.1最小生成树求解和贪心法 240
6.4.2 Kruskal算法 242
6.4.3 Prim算法 244
6.4.4扩展阅读：其他建立最小生成树的方法 246
6.5最短路径 248
6.5.1非负权值的单源最短路径 248
6.5.2扩展阅读：边上权值为任意值的单源最短路径问题 252
6.5.3所有顶点之间的最短路径 254
6.5.4无权值的最短路径 257
6.6活动网络 259
6.6.1 AOV网络与拓扑排序 259
6.6.2 AOE网络与关键路径法 262
小结 267
习题 268
第7章 查找 273
7.1查找的概念及简单查找方法 273
7.1.1查找的基本概念 273
7.1.2顺序查找法 274
7.1.3折半查找法 276
7.1.4扩展阅读：次优查找树 279
7.1.5扩展阅读：斐波那契查找和插值查找 282
7.1.6扩展阅读：跳表 283
7.2二叉查找树 284
7.2.1二叉查找树的概念 285
7.2.2二叉查找树的查找 285
7.2.3二叉查找树的插入 286
7.2.4二叉查找树的删除 288
7.2.5二叉查找树的性能分析 289
7.3 AVL树 292
7.3.1 AVL树的概念 292
7.3.2平衡化旋转 293
7.3.3 AVL树的插入 295
7.3.4 AVL树的删除 296
7.3.5 AVL树的性能分析 299
7.4 B树 300
7.4.1索引顺序表与分块查找 300
7.4.2多级索引结构与m叉查找树 301
7.4.3 B树的概念 302
7.4.4 B树上的查找 304
7.4.5 B树上的插入 305
7.4.6 B树上的删除 306
7.4.7 B＋树 308
7.5扩展阅读：其他查找树 311
7.5.1红黑树 311
7.5.2伸展树 313
7.5.3字典树 315
7.6散列表及其查找 317
7.6.1散列的概念 318
7.6.2常见的散列函数 318
7.6.3解决冲突的开地址法 321
7.6.4解决冲突的链地址法 327
7.6.5散列法分析 329
小结 330
习题 330
第8章 排序 335
8.1排序的概念 335
8.1.1排序的相关概念 335
8.1.2排序算法的性能分析 336
8.1.3数据表的结构定义 337
8.2插入排序 338
8.2.1直接插入排序 338
8.2.2基于静态链表的直接插入排序 339
8.2.3折半插入排序 341
8.2.4希尔排序 342
8.3交换排序 343
8.3.1起泡排序 344
8.3.2快速排序 345
8.3.3快速排序的改进算法 348
8.4选择排序 350
8.4.1简单选择排序 350
8.4.2锦标赛排序 351
8.4.3堆排序 352
8.5归并排序 356
8.5.1二路归并排序的设计思路 356
8.5.2二路归并排序的递归算法 356
8.5.3扩展阅读：基于链表的归并排序算法 358
8.5.4扩展阅读：迭代的归并排序算法 359
8.6基数排序 361
8.6.1基数排序 362
8.6.2 MSD基数排序 362
8.6.3 LSD基数排序 364
8.7内排序算法的分析和比较 367
8.7.1排序方法的下界 367
8.7.2各种内排序方法的比较 368
8.8外排序 371
8.8.1常用的外存储器与缓冲区 371
8.8.2基于磁盘的外排序过程 372
8.8.3 m路平衡归并的过程 374
8.8.4初始归并段的生成 378
8.8.5最佳归并树 381
8.8.6磁带归并排序 382
小结 385
习题 386
附录A实训作业要求与样例 391
A.1实训作业要求 391
A.2实训作业样例 392
附录B词汇索引 397
参考文献 405