第1章 绪论 1
1.1 数据结构简介 1
1.1.1 数据结构课程的内容 1
1.1.2 数据结构的基本概念和术语 1
1.2 抽象数据类型 4
1.3 算法的执行效率及其度量 6
1.3.1 算法 6
1.3.2 算法设计的要求 7
1.3.3 算法效率的度量 8
1.3.4 算法的存储空间需求 11
1.4 算法分析 11
1.4.1 算法设计与分析的重要性 11
1.4.2 一个简单的算法分析设计实例 13
习题 17
ACM/ICPC实战练习 19
第2章 线性结构 20
2.1 线性表 20
2.1.1 线性表的定义 20
2.1.2 线性表的抽象数据类型 20
2.1.3 线性表的存储结构 21
2.2 线性表的顺序存储及运算实现 22
2.2.1 顺序表 22
2.2.2 顺序表上基本运算的实现 23
2.2.3 顺序表应用举例 25
2.3 线性表的链式存储和运算实现 26
2.3.1 单链表 27
2.3.2 单链表上基本运算的实现 28
2.3.3 循环链表 33
2.3.4 双向链表 34
2.3.5 静态链表 35
2.3.6 单链表应用举例 36
2.3.7 线性表实现方法比较 39
2.4 栈 40
2.4.1 顺序栈 41
2.4.2 链式栈 42
2.4.3 栈的应用举例 43
2.4.4 栈与递归 51
2.5 队列 52
2.5.1 顺序队列 52
2.5.2 链式队列 55
2.5.3 基于队列的算法设计实例 56
2.6 数组 59
2.6.1 数组的定义 59
2.6.2 数组的顺序表示和实现 59
2.6.3 特殊矩阵的压缩存储 60
习题 68
ACM/ICPC实战练习 69
第3章 字符串 70
3.1 串类型定义 70
3.2 串的表示和实现 71
3.2.1 串的定长顺序存储结构及其基本运算实现 71
3.2.2 串的堆存储结构及其基本运算实现 73
3.2.3 串的链式存储结构及其基本运算实现 75
3.3 串的模式匹配算法 77
3.3.1 朴素匹配算法 78
3.3.2 KMP算法 79
3.3.3 基于KMP算法的应用举例 82
习题 84
ACM/ICPC实战练习 84
第4章 树和二叉树 86
4.1 树 86
4.1.1 树的定义和基本术语 86
4.1.2 树的抽象数据类型 87
4.1.3 树的存储结构 88
4.1.4 树的遍历 89
4.1.5 树的应用 89
4.2 二叉树 98
4.2.1 二叉树的定义 98
4.2.2 二叉树的性质 99
4.2.3 二叉树的存储结构 100
4.2.4 表达式树 102
4.2.5 二叉树的基本操作及实现 104
4.3 遍历二叉树和线索二叉树 106
4.3.1 遍历二叉树 106
4.3.2 二叉树遍历的非递归实现 108
4.3.3 线索二叉树 112
4.4 树、森林和二叉树的转换 118
4.4.1 树转换为二叉树 118
4.4.2 森林转换为二叉树 119
4.4.3 二叉树转换为树和森林 120
4.5 Huffman编码树 121
4.5.1 最优二叉树（Huffman树） 121
4.5.2 Huffman编码 124
4.6 二叉搜索树 126
4.6.1 二叉搜索树的基本操作 126
4.6.2 平衡二叉树（AVL树） 131
4.7 伸展树 136
4.7.1 伸展树的基本操作 136
4.7.2 伸展树的参考例程 138
4.8 堆与优先队列 141
4.8.1 堆的逻辑定义 141
4.8.2 堆的性质 142
4.8.3 堆的基本操作 142
4.8.4 堆的实现例程 142
4.9 B-树和B+树 144
4.9.1 B-树及其查找 144
4.9.2 B-树的插入和删除 146
4.9.3 B+树 149
4.10 树型结构搜索算法应用案例 149
4.10.1 基于二叉树遍历的应用 149
4.10.2 ACM/ICPC竞赛题例分析 152
习题 158
ACM/ICPC实战练习 159
第5章 图论算法 161
5.1 图 161
5.1.1 图的定义和术语 161
5.1.2 图的抽象数据类型 164
5.1.3 图的存储结构 164
5.2 图的遍历算法 171
5.2.1 深度优先搜索 172
5.2.2 广度优先搜索 173
5.2.3 深度与广度优先搜索应用 175
5.3 图的连通性 182
5.3.1 无向图的连通性 183
5.3.2 有向图的连通性 183
5.3.3 生成树和生成森林 184
5.3.4 关节点和重连通分量 186
5.3.5 有向图的强连通分量 188
5.4 有向无环图及其应用 194
5.4.1 有向无环图的概念 194
5.4.2 AOV网与拓扑排序 195
5.4.3 AOE网与关键路径 199
5.5 最短路径算法 203
5.5.1 无权最短路径 204
5.5.2 Dijkstra算法 205
5.5.3 具有负边值的图 209
5.5.4 所有点对的最短路径 212
5.6 最小支撑树 216
5.6.1 Prim算法 217
5.6.2 Kruskal算法 219
5.6.3 最小生成树算法应用 222
5.7 网络流问题 223
5.7.1 网络流的最大流问题 224
5.7.2 网络流应用 229
习题 232
ACM/ICPC实战练习 235
第6章 内部排序 236
6.1 概述 236
6.2 基于顺序比较的简单排序算法 236
6.2.1 插入排序（Insertion Sort） 236
6.2.2 冒泡排序（Bubble Sort） 241
6.2.3 直接选择排序（Directly Selection Sort） 242
6.2.4 简单排序算法的时间代价对比 242
6.3 缩小增量排序方法——Shell排序（Shell Sort） 243
6.4 基于分治策略的排序 244
6.4.1 快速排序（Quick Sort） 244
6.4.2 归并排序（Merge Sort） 247
6.5 树形排序方法 249
6.5.1 堆排序（Heap Sort） 249
6.5.2 树形选择排序（Tree Select Sort） 252
6.6 分配排序和基数排序 253
6.6.1 桶式排序（Bucket Sort） 253
6.6.2 基数排序（Radix Sort） 253
6.7 内部排序问题讨论与分析 257
6.7.1 常用排序算法性能简要分析 257
6.7.2 排序问题的下限 257
6.8 排序应用举例 258
习题 262
ACM/ICPC实战练习 264
第7章 文件管理和外排序 265
7.1 外存储器 265
7.1.1 磁盘 265
7.1.2 磁盘访问时间估算 267
7.2 外存文件的组织 268
7.2.1 文件组织 268
7.2.2 文件上的操作 270
7.2.3 C语言中的文件流操作 270
7.3 缓冲区和缓冲池 272
7.4 外排序（External Sort） 273
7.4.1 二路外排序 274
7.4.2 多路平衡归并的实现 275
7.5 置换-选择排序 279
7.6 最佳归并树 283
习题 284
第8章 检索与散列表 286
8.1 检索的基本概念 286
8.2 基于线性表的检索 288
8.2.1 顺序检索 288
8.2.2 有序表的二分检索 289
8.2.3 有序表的插值查找和斐波那契查找 293
8.2.4 分块检索 294
8.3 集合的检索 295
8.3.1 集合的数学特性 295
8.3.2 计算机中的集合 296
8.4 键树 298
8.4.1 基本概念 298
8.4.2 键树的存储表示 298
8.4.3 键树相关算法实现 299
8.5 散列方法及其检索 301
8.5.1 散列函数 303
8.5.2 开散列方法（分离链接法） 307
8.5.3 开放定址法 308
8.5.4 散列方法的效率分析 310
8.6 散列表及检索的应用 312
习题 318
ACM/ICPC实战练习 319
第9章 算法设计方法 321
9.1 算法设计方法概论 321
9.1.1 常用的算法设计方法 321
9.1.2 算法设计中的最优化问题 322
9.2 分治法 324
9.2.1 分治策略的思想 324
9.2.2 高精度计算 326
9.2.3 矩阵相乘的Strassen算法 334
9.2.4 选择问题的分治算法 335
9.2.5 分治法求最近点对问题 336
9.2.6 分治法的应用 338
9.3 贪心法 347
9.3.1 贪心算法的思想 347
9.3.2 活动安排问题 348
9.3.3 背包问题 350
9.3.4 多机调度问题的近似算法 352
9.3.5 任务调度问题 353
9.3.6 贪心算法的应用 355
9.4 回溯与分支限界 362
9.4.1 回溯与分支限界简介 362
9.4.2 八皇后问题 364
9.4.3 0-1背包问题的回溯算法 366
9.4.4 分支限界算法 368
9.4.5 回溯与分支限界应用 370
9.5 动态规划法 377
9.5.1 Fibonacci数的计算 377
9.5.2 矩阵连乘的顺序问题 379
9.5.3 适合动态规划算法的两个条件 384
9.5.4 最长不降子序列问题 390
9.5.5 最长公共子序列问题 393
9.5.6 石子合并问题 399
9.5.7 凸多边形最优三角剖分 405
习题 408
ACM/ICPC实战练习 409
参考文献 411