目录 1
出版者的话 1
专家指导委员会 1
译者序 1
前言 1
第1章 基本概念 1
1.1 综述：系统生命周期 1
1.2 算法描述 3
1.2.1 引言 3
1.2.2 递归算法 6
1.3 数据抽象 9
1.4.1 空间复杂性 12
1.4 算法的性能分析 12
1.4.2 时间复杂性 14
1.4.3 渐近记号（O,Ω,Θ） 19
1.4.4 实际可行的复杂性 24
1.5 性能测量 26
1.6 参考文献和文献选读 31
第2章 数组与结构 32
2.1 ADT数组 32
2.2 结构与共用体 34
2.2.1 结构 34
2.2.2 共用体 36
2.2.3 结构的内部实现 37
2.2.4 自引用结构 37
2.3 ADT多项式 38
2.4.1 概述 43
2.4 ADT稀疏矩阵 43
2.4.2 矩阵转置 44
2.4.3 矩阵乘法 47
2.5 多维数组的存储表示 50
2.6 ADT字符串 52
2.6.1 概述 52
2.6.2 模式匹配 55
2.7 参考文献和文献选读 59
2.8 附加习题 59
第3章 栈与队列 65
3.1 ADT栈 65
3.2 ADT队列 68
3.3 迷宫问题 72
3.4.1 概述 75
3.4 表达式求值 75
3.4.2 后缀表达式求值 77
3.4.3 中缀表达式到后缀表达式的转换 79
3.5 多栈和多队列 81
3.6 参考文献和文献选读 84
3.7 附加习题 84
第4章 链表 86
4.1 指针 86
4.1.1 指针的危险性 87
4.1.2 动态存储分配 87
4.2 单向链表 88
4.3 动态链栈与动态链队列 93
4.4 多项式 96
4.4.1 多项式的单向链表表示 96
4.4.2 多项式加法 97
4.4.3 多项式删除 99
4.4.4 多项式的循环链表表示 100
4.4.5 小结 103
4.5 链表的其他操作 104
4.5.1 单向链表的操作 104
4.5.2 循环链表的操作 105
4.6 等价关系 106
4.7 稀疏矩阵 109
4.8 双向链表 114
4.9 参考文献和文献选读 116
4.10 附加习题 117
5.1 概述 118
5.1.1 术语 118
第5章 树 118
5.1.2 树的存储表示 119
5.2 二叉树 121
5.2.1 抽象数据型 121
5.2.2 二叉树的性质 123
5.2.3 二叉树的存储表示 124
5.3 二叉树的遍历 126
5.4 二叉树的其他操作 130
5.5 线索二叉树 133
5.6 堆 137
5.6.1 ADT堆 137
5.6.2 优先级队列 138
5.6.3 最大堆的插入操作 139
5.6.4 最大堆的删除操作 140
5.7.1 概述 142
5.7 二叉查找树 142
5.7.2 二叉查找树的查找 143
5.7.3 二叉查找树的插入 144
5.7.4 二叉查找树的删除 145
5.7.5 二叉查找树的高度 145
5.8 选择树 146
5.9 森林 148
5.9.1 森林转换为二叉树 148
5.9.2 森林的遍历 149
5.10 集合表示 149
5.10.1 Union和Find操作 150
5.10.2 等价类 155
5.11.1 不同的二叉树 156
5.11.2 栈排列 156
5.11 二叉树计数 156
5.11.3 矩阵乘法 158
5.11.4 不同的二叉树数量 159
5.12 参考文献和文献选读 159
5.13 附加习题 160
第6章 图 162
6.1 ADT图 162
6.1.1 概述 162
6.1.2 定义 163
6.1.3 图的存储表示 165
6.2 图的基本操作 170
6.2.1 深度优先搜索 171
6.2.2 广度优先搜索 171
6.2.3 连通分支 173
6.2.4 生成树 174
6.2.5 双连通分支与关节点 175
6.3 最小代价生成树 179
6.4 最短路径与传递闭包 183
6.4.1 单源多目标最短路径 184
6.4.2 所有顶点对之间的最短路径 187
6.4.3 传递闭包 188
6.5 活动网络 190
6.5.1 AOV网 190
6.5.2 AOE网 194
6.6 参考文献和文献选读 200
6.7 附加习题 200
7.1.1 概述 202
7.1.2 顺序查找 202
7.1 查找与表验证 202
第7章 排序 202
7.1.3 折半查找 203
7.1.4 表验证 204
7.2 定义 206
7.3 插入排序 207
7.4 快速排序 208
7.5 最优的排序时间 211
7.6 归并排序 212
7.6.1 归并 212
7.6.2 归并排序的迭代算法 216
7.6.3 归并排序的递归算法 217
7.7 堆排序 220
7.8 基数排序 223
7.9 利用链表和映射表进行排序 227
7.10 内部排序总结 233
7.11 外部排序 236
7.11.1 概述 236
7.11.2 k路归并 239
7.11.3 并行操作的缓冲区处理 240
7.11.4 归并段的生成 244
7.11.5 归并段的最优归并 246
7.12 参考文献和文献选读 249
7.13 附加习题 249
第8章 散列 251
8.1 ADT符号表 251
8.2 静态散列 252
8.2.1 散列表 252
8.2.2 散列函数 253
8.2.3 溢出处理 254
8.2.4 溢出处理技术的理论分析 259
8.3 动态散列 262
8.3.1 带目录的动态散列 263
8.3.2 带目录的动态散列的分析 268
8.3.3 无目录的动态散列 269
8.4 参考文献和文献选读 272
第9章 堆结构 274
9.1 最小-最大堆 274
9.1.1 定义 274
9.1.2 最小-最大堆插入 274
9.1.3 删除最小元素 277
9.2 双端堆 279
9.2.1 定义 279
9.2.2 插入操作 280
9.2.3 删除最小元素操作 282
9.3 左高树 284
9.4 二项堆 289
9.4.1 分摊代价 289
9.4.2 二项堆的定义 290
9.4.3 插入操作 291
9.4.4 合并操作 291
9.4.5 删除最小元素操作 291
9.4.6 代价分摊分析 293
9.5 斐波那契堆 294
9.5.1 定义 294
9.5.2 删除操作 295
9.5.3 关键字减值操作 295
9.5.4 级联剪枝操作 296
9.5.5 分析 297
9.5.6 F堆的应用 298
9.6 参考文献和文献选读 299
第10章 查找结构 301
10.1 最优二叉查找树 301
10.2 AVL树 307
10.3 2-3树 317
10.3.1 定义与性质 317
10.3.2 2-3树的查找操作 318
10.3.3 2-3树的插入操作 318
10.3.4 2-3树的删除操作 321
10.4 2-3-4树 325
10.4.1 定义与性质 325
10.4.2 2-3-4树的插入操作 327
10.4.3 2-3-4树的删除操作 329
10.5 红黑树 331
10.5.1 定义与性质 331
10.5.2 红黑树的查找 332
10.5.3 自顶向下的插入 333
10.5.4 自底向上的插入 334
10.5.5 从红黑树删除结点 335
10.6 B树 337
10.6.1 m路查找树的定义 337
10.6.2 m路查找树的查找 338
10.6.3 B树的定义和性质 338
10.6.4 B树的插入操作 340
10.6.5 B树的删除操作 342
10.6.6 可变长的关键字值 343
10.7 伸展树 345
10.8 数字查找树 349
10.8.1 数字查找树 349
10.8.2 二叉检索树 350
10.8.3 Patricia树 351
10.9 检索树 355
10.9.1 定义 355
10.9.2 检索树的查找操作 356
10.9.3 采样策略 356
10.9.4 检索树的插入操作 358
10.9.5 检索树的删除操作 358
10.10 差分文件 359
10.11 参考文献和文献选读 362
附录 ANSI C和K R C 364
索引 370