第1章 基本概念 1
1.1概观：系统生命周期 1
1.2指针和动态存储分配 3
1.2.1指针 3
1.2.2动态存储分配 4
1.2.3指针隐患 6
1.3算法形式规范 6
1.3.1综论 6
1.3.2递归算法 11
1.4数据抽象 14
1.5性能分析 17
1.5.1空间复杂度 18
1.5.2时间复杂度 20
1.5.3渐近记号（O，Ω，Θ） 27
1.5.4实际复杂度 33
1.6性能度量 35
1.6.1定时 35
1.6.2生成测试数据 39
1.7参考文献和选读材料 40
第2章 数组和结构 41
2.1数组 41
2.1.1数组的抽象数据类型 41
2.1.2C语言的数组 41
2.2数组的动态存储分配 44
2.2.1一维数组 44
2.2.2二维数组 44
2.3结构体和联合体 47
2.3.1结构体 47
2.3.2联合体 49
2.3.3结构的内部实现 50
2.3.4自引用结构 50
2.4多项式 51
2.4.1多项式的抽象数据类型 51
2.4.2多项式的表示 52
2.4.3多项式加法 55
2.5稀疏矩阵 58
2.5.1稀疏矩阵的抽象数据类型 58
2.5.2稀疏矩阵的表示 58
2.5.3矩阵转置 59
2.5.4矩阵相乘 63
2.6多维数组的表示 67
2.7字符串 68
2.7.1字符串的抽象数据类型 68
2.7.2C语言的字符串 68
2.7.3模式匹配 71
2.8参考文献和选读材料 77
2.9补充习题 78
第3章 栈与队列 83
3.1栈 83
3.2动态栈 87
3.3队列 88
3.4动态循环队列 92
3.5迷宫问题 95
3.6表达式求值 98
3.6.1表达式 98
3.6.2后缀表达式求值 100
3.6.3中缀表达式转换成后缀表达式 103
3.7多重栈与多重队列 108
3.8补充习题 111
第4章 链表 113
4.1单向链表 113
4.2用C语言表示单向链表 115
4.3链式栈与链式队列 121
4.4多项式 124
4.4.1多项式表示 124
4.4.2多项式加法 125
4.4.3销毁多项式 128
4.4.4循环链表与多项式 129
4.4.5小结 130
4.5其它链表操作 133
4.5.1单向链表操作 133
4.5.2循环链表操作 134
4.6等价类 135
4.7稀疏矩阵 139
4.7.1稀疏矩阵表示 139
4.7.2输入稀疏矩阵 142
4.7.3输出稀疏矩阵 144
4.7.4销毁稀疏矩阵 144
4.8双向链表 146
第5章 树 149
5.1引论 149
5.1.1术语 149
5.1.2树的表示 151
5.2二叉树 154
5.2.1二叉树的抽象数据类型 154
5.2.2二叉树的性质 155
5.2.3二叉树的表示 157
5.3遍历二叉树 159
5.3.1中序遍历 160
5.3.2先序遍历 161
5.3.3后序遍历 161
5.3.4非递归（循环）中序遍历 162
5.3.5层序遍历 163
5.3.6不设栈遍历二叉树 163
5.4其它二叉树操作 164
5.4.1复制二叉树 164
5.4.2判断两个二叉树全等 164
5.4.3可满足性问题 165
5.5线索二叉树 168
5.5.1线索 168
5.5.2中序遍历线索二叉树 169
5.5.3线索二叉树插入结点 170
5.6堆 172
5.6.1优先级队列 172
5.6.2大根堆定义 174
5.6.3大根堆插入操作 174
5.6.4大根堆删除操作 176
5.7二叉查找树 178
5.7.1定义 178
5.7.2二叉查找树的查找 179
5.7.3二叉查找树的插入 180
5.7.4二叉查找树的删除 181
5.7.5二叉查找树的合并与分裂 182
5.7.6二叉查找树的高度 183
5.8选拔树 185
5.8.1引子 185
5.8.2优胜树 186
5.8.3淘汰树 187
5.9森林 188
5.9.1森林转换为二叉树 189
5.9.2遍历森林 189
5.10不相交集合的表示 190
5.10.1引子 190
5.10.2合并与查找操作 191
5.10.3划分等价类 197
5.11二叉树的计数 199
5.11.1不同态二叉树 199
5.11.2栈置换 200
5.11.3矩阵乘法 201
5.11.4不同二叉树的数目 203
5.12参考文献和选读材料 204
第6章 图 205
6.1图的抽象数据类型 205
6.1.1引子 205
6.1.2图的定义和术语 206
6.1.3图的表示 210
6.2图的基本操作 216
6.2.1深度优先搜索 216
6.2.2广度优先搜索 217
6.2.3连通分量 218
6.2.4生成树 219
6.2.5重连通分量 220
6.3最小代价生成树 225
6.3.1Kruskal算法 225
6.3.2Prim算法 228
6.3.3Sollin算法 229
6.4最短路径和迁移闭包 230
6.4.1单源点至所有其它节点：边权值非负 231
6.4.2单源点至所有其它节点：边权值正负无限制 233
6.4.3所有节点两两之间的最短路径 237
6.4.4迁移闭包 238
6.5活动网络 242
6.5.1活动节点（AOV）网络 242
6.5.2活动边（AOE）网络 247
6.6参考文献和选读材料 253
6.7补充习题 254
第7章 排序 256
7.1动机 256
7.2插入排序 259
7.3快速排序 261
7.4排序最快有多快 264
7.5归并排序 265
7.5.1归并 265
7.5.2非递归归并排序 266
7.5.3递归归并排序 267
7.6堆排序 270
7.7多关键字排序 273
7.8链表排序和索引表排序 277
7.9内部排序小结 284
7.10外部排序 289
7.10.1引子 289
7.10.2k路归并 291
7.10.3缓存与并行操作 292
7.10.4生成多路数据 298
7.10.5最优多路归并 300
7.11参考文献和选读材料 303
第8章 Hash法 304
8.1引言 304
8.2静态Hash法 304
8.2.1Hash表 304
8.2.2Hash函数 305
8.2.3溢出处理 307
8.2.4处理溢出方法的理论估计 312
8.3动态Hash法 315
8.3.1动态Hash法的动机 315
8.3.2设目录的动态Hash法 316
8.3.3不设目录的动态Hash法 318
8.4Bloom滤波器 320
8.4.1差异文件及其应用 320
8.4.2设计Bloom滤波器 321
8.5参考文献和选读材料 323
第9章 优先级队列 324
9.1单端优先级队列与双端优先级队列 324
9.2左倾树 325
9.2.1高度左倾树 325
9.2.2权值左倾树 330
9.3二项式堆 332
9.3.1代价分摊 332
9.3.2二项式堆的定义 333
9.3.3二项式堆的插入 333
9.3.4融合两个二项式堆 334
9.3.5删除最小元 334
9.3.6分析 336
9.4Fibonacci堆 338
9.4.1定义 338
9.4.2F-堆的删除 338
9.4.3减小关键字 339
9.4.4上行切除 339
9.4.5分析 340
9.4.6F-堆与最短路径问题 342
9.5配偶堆 344
9.5.1定义 344
9.5.2融合与插入 344
9.5.3减小关键字值 345
9.5.4删除最小元 346
9.5.5删除任意元 348
9.5.6实现细节 349
9.5.7复杂度分析 349
9.6对称最小-最大堆 350
9.6.1定义与性质 350
9.6.2SMMH的表示 351
9.6.3SMMH的插入 351
9.6.4SMMH的删除 353
9.7区间堆 358
9.7.1定义和性质 358
9.7.2区间堆的插入 359
9.7.3删除最小元 360
9.7.4区间堆的初始化 361
9.7.5区间堆操作的复杂度 361
9.7.6区间外查找 361
9.8参考文献和选读材料 363
第10章 高效二叉查找树 366
10.1最优二叉查找树 366
10.2AVL树 373
10.3红-黑树 384
10.3.1定义 384
10.3.2红-黑树的表示 386
10.3.3红-黑树的查找 386
10.3.4红-黑树的插入 386
10.3.5红-黑树的删除 389
10.3.6红-黑树的合并 389
10.3.7红-黑树的分裂 391
10.4Splay树 393
10.4.1自底向上Splay树 394
10.4.2自顶向下Splay树 398
10.5参考文献和选读材料 403
第11章 多路查找树 405
11.1m-路查找树 405
11.1.1定义和性质 405
11.1.2m-路查找树的查找 406
11.2B-树 407
11.2.1定义和性质 407
11.2.2B-树中数据元素的个数 408
11.2.3B-树的插入 409
11.2.4B-树的删除 412
11.3B+-树 419
11.3.1定义 419
11.3.2B+-树的查找 420
11.3.3B+-树的插入 420
11.3.4B+-树的删除 422
11.4参考文献和选读材料 426
第12章 数字查找结构 427
12.1数字查找树 427
12.1.1定义 427
12.1.2查找、插入、删除 427
12.2二路Trie树与Patricia树 428
12.2.1二路Trie树 428
12.2.2压缩二路Trie树 429
12.2.3Patricia树 429
12.3多路Trie树 434
12.3.1定义 434
12.3.2Trie树的查找 436
12.3.3取样策略 437
12.3.4Trie树的插入 439
12.3.5Trie树的删除 439
12.3.6变长关键字 440
12.3.7Trie树的高度 440
12.3.8空间需求与其它结点结构 440
12.3.9查找前缀及其应用 443
12.3.10压缩Trie树 444
12.3.11设skip域的压缩Trie树 446
12.3.12设边标记的压缩Trie树 446
12.3.13压缩Trie树的空间需求 449
12.4后缀树 450
12.4.1你见过基因串吗 450
12.4.2后缀树数据结构 450
12.4.3查！查！查子串！（后缀树的查找） 453
12.4.4后缀树的妙用 454
12.5Trie树与互连网的包转发 455
12.5.1IP路由 455
12.5.21-bit Trie树 456
12.5.3固定步长Trie树 457
12.5.4不定步长Trie树 459
12.6参考文献和选读材料 461
索引 463