第1章 绪论 1
1.1 二元关系 1
1.1.1 二元关系的定义 1
1.1.2 二元关系的基本性质和几种重要关系 3
1.2 数据结构 4
1.2.1 数据结构的引出 4
1.2.2 数据的逻辑结构和存储结构 5
1.2.3 数据结构的表示 8
1.3 抽象数据类型 9
1.3.1 抽象数据类型 9
1.3.2 面向对象方法与抽象数据类型 11
1.3.3 抽象数据类型的实现 12
1.4 算法与算法评价 14
1.4.1 算法 14
1.4.2 算法描述与算法描述语言 16
1.4.3 算法的评价 26
1.5 习题 30
第2章 线性表的顺序存储及其运算 32
2.1 线性表的概念 32
2.1.1 线性表 32
2.1.2 线性表的抽象数据类型 34
2.2 线性表的顺序存储及其运算 35
2.2.1 线性表的顺序存储——顺序表 35
2.2.2 顺序表的基本运算 36
2.2.3 顺序表的类定义 41
2.3 栈 42
2.3.1 栈 42
2.3.2 栈的抽象数据类型 45
2.3.3 栈的顺序存储及其运算 45
2.3.4 顺序栈的类定义 49
2.3.5 栈应用举例 49
2.4 队列 70
2.4.1 队列及其抽象数据类型 70
2.4.2 顺序队列及其运算 71
2.4.3 队列应用举例 76
2.4.4 优先队列 81
2.5 数组与特殊矩阵的表示 83
2.5.1 数组的顺序存储 83
2.5.2 规则矩阵的压缩存储 85
2.5.3 稀疏矩阵的三列二维数组表示——三元组顺序表 87
2.6 习题 90
第3章 链表 92
3.1 线性表的链式存储——线性链表 92
3.1.1 线性链表的概念 92
3.1.2 线性链表的运算 93
3.1.3 线性链表的类定义 100
3.2 链式栈与链式队列 101
3.2.1 链式栈 101
3.2.2 链式队列 105
3.3 循环链表 108
3.3.1 循环链表的结构特点 108
3.3.2 循环链表的基本运算 109
3.4 多重链表 113
3.4.1 多重链表的结构 113
3.4.2 双向链表 114
3.4.3 稀疏矩阵的十字链表表示 116
3.5 广义表 118
3.5.1 广义表的概念 118
3.5.2 广义表的存储表示 120
3.5.3 广义表的基本运算 122
3.6 习题 125
第4章 树与二叉树 128
4.1 树的基本概念 128
4.1.1 树结构的引出 128
4.1.2 树的定义与表示 129
4.1.3 树的性质 131
4.2 二叉树及其运算 132
4.2.1 二叉树的定义 132
4.2.2 二叉树的基本性质 132
4.2.3 二叉树的抽象数据类型 135
4.2.4 二叉树的存储结构 136
4.2.5 二叉树的遍历及其他运算 137
4.2.6 线索二叉树 143
4.2.7 二叉树的计数 146
4.3 二叉树的应用 148
4.3.1 利用二叉树实现表达式线性化 149
4.3.2 最优二叉树 150
4.3.3 二叉搜索树 156
4.3.4 堆 161
4.4 树的运算 169
4.4.1 树的抽象数据类型 169
4.4.2 树的存储结构 169
4.4.3 树的遍历 171
4.4.4 树遍历运算的应用——树的其他运算 172
4.4.5 树结构应用举例 177
4.5 森林的遍历 180
4.5.1 森林与二叉树的转换 180
4.5.2 森林的遍历 181
4.6 习题 182
第5章 图 184
5.1 图的基本概念 184
5.1.1 图的定义和概念 184
5.1.2 图的抽象数据类型 187
5.1.3 欧拉路径和汉密尔顿路径 188
5.2 图的存储结构 189
5.2.1 图的邻接矩阵表示 190
5.2.2 图的邻接表表示 192
5.2.3 图的其他表示方法 195
5.3 图的遍历 197
5.3.1 图的深度优先遍历 197
5.3.2 图的广度优先遍历 198
5.3.3 图遍历的应用 199
5.3.4 广义图搜索 201
5.3.5 图的连通性 202
5.4 有向图与有向无环图 203
5.4.1 有向图的连通性和传递闭包 203
5.4.2 有向无环图和拓扑排序 205
5.4.3 关键路径 208
5.5 最小生成树 209
5.5.1 图的生成树与最小生成树 209
5.5.2 普里姆（Prim）算法 211
5.5.3 克鲁斯卡尔（Kruskal）算法 213
5.5.4 贪心算法 215
5.6 最短路径问题 216
5.6.1 单源最短路径 216
5.6.2 带负权值边的单源最短路径 218
5.6.3 全源最短路径 220
5.6.4 动态规划算法 223
5.7 图应用举例 224
5.7.1 问题描述 224
5.7.2 问题求解思路 225
5.8 习题 225
第6章 查找 228
6.1 线性查找表 228
6.1.1 顺序查找 229
6.1.2 折半查找 229
6.1.3 斐波那契查找 231
6.1.4 线性查找表的性能比较 231
6.2 二叉搜索树的查找性能 231
6.2.1 二叉搜索树与线性查找表的比较 231
6.2.2 二叉搜索树的查找性能 233
6.3 AVL树 234
6.3.1 BST的旋转操作 234
6.3.2 AVL树的插入和平衡化旋转 235
6.3.3 AVL树的删除 237
6.3.4 AVL树的性能 239
6.4 B-树 240
6.4.1 多路动态搜索树 240
6.4.2 B-树的查找 241
6.4.3 B-树的插入 241
6.4.4 B-树的删除 242
6.5 2-3-4树和红黑树 245
6.5.1 2-3-4树 245
6.5.2 红黑树 246
6.6 散列方法 249
6.6.1 散列技术 249
6.6.2 散列函数 250
6.6.3 冲突处理 252
6.6.4 散列的删除 254
6.6.5 散列的性能 255
6.7 静态索引结构 255
6.7.1 索引查找 255
6.7.2 索引存储方式 256
6.7.3 索引文件结构 258
6.8 模式匹配算法 261
6.8.1 字符串的概念和ADT 261
6.8.2 字符串的存储表示 262
6.8.3 字符串的模式匹配和简单匹配算法 263
6.8.4 KMP算法 263
6.9 习题 266
第7章 排序 268
7.1 排序的概念及算法性能分析 268
7.2 基本排序方法 269
7.2.1 冒泡排序 270
7.2.2 插入排序 271
7.2.3 直接选择排序 275
7.2.4 基本排序方法的比较 276
7.3 快速排序 277
7.3.1 快速排序的过程 277
7.3.2 快速排序的性能分析 279
7.3.3 快速排序的改进算法 279
7.3.4 三路划分的快速排序算法 280
7.4 归并排序 282
7.4.1 二路归并 282
7.4.2 自底向上的归并排序 283
7.4.3 自顶向下的归并排序 284
7.5 锦标赛排序 285
7.6 堆排序 286
7.6.1 堆排序的思想 286
7.6.2 堆排序的实现 288
7.7 内排序方法分析 289
7.7.1 排序方法的下界 289
7.7.2 内排序方法的比较 291
7.8 线性时间复杂度的排序算法 292
7.8.1 计数排序 292
7.8.2 箱排序 293
7.8.3 基数排序 294
7.9 排序网络 297
7.9.1 排序网络的概念 297
7.9.2 巴彻尔奇偶归并排序 298
7.10 外部排序 302
7.10.1 外部排序方法 302
7.10.2 基于败者树的k路归并算法 302
7.10.3 排序-归并的改进 304
7.11 习题 307
参考文献 309