第1 章 引论 ············································································································································1
1.1 算法及其复杂性的概念 ··········································································································1
1.1.1 算法与程序 ························································································································1
1.1.2 算法复杂性的概念 ·············································································································1
1.1.3 算法复杂性的渐近性态·······································································································3
1.2 算法的表达与数据表示 ··········································································································5
1.2.1 问题求解 ···························································································································5
1.2.2 表达算法的抽象机制 ··········································································································5
1.3 抽象数据类型 ··························································································································8
1.3.1 抽象数据类型的基本概念 ···································································································8
1.3.2 使用抽象数据类型的好处 ···································································································9
1.4 数据结构、数据类型和抽象数据类型 ··············································································· 10
1.5 用C 语言描述数据结构与算法 ··························································································· 11
1.5.1 变量和指针 ······················································································································ 11
1.5.2 函数与参数传递 ·············································································································· 12
1.5.3 结构 ······························································································································· 13
1.5.4 动态存储分配 ················································································································· 14
1.6 递归 ········································································································································ 15
1.6.1 递归的基本概念 ·············································································································· 15
1.6.2 间接递归 ························································································································ 17
本章小结 ········································································································································· 18
习题1 ·············································································································································· 18
算法实验题1 ·································································································································· 19
第2 章 表 ············································································································································· 21
2.1 表的基本概念 ······················································································································· 21
2.2 用数组实现表 ······················································································································· 22
2.3 用指针实现表 ······················································································································· 26
2.4 用间接寻址方法实现表 ······································································································· 30
2.5 用游标实现表 ······················································································································· 32
2.6 循环链表 ································································································································ 37
2.7 双链表 ···································································································································· 39
2.8 表的搜索游标 ······················································································································· 43
2.8.1 用数组实现表的搜索游标 ································································································ 43
2.8.2 单循环链表的搜索游标···································································································· 44
VI
2.9 应用举例 ································································································································ 45
本章小结 ········································································································································· 47
习题2 ·············································································································································· 47
算法实验题2 ·································································································································· 49
第3 章 栈 ············································································································································· 52
3.1 栈的基本概念 ······················································································································· 52
3.2 用数组实现栈 ······················································································································· 53
3.3 用指针实现栈 ······················································································································· 55
3.4 应用举例 ································································································································ 57
本章小结 ········································································································································· 60
习题3 ·············································································································································· 60
算法实验题3 ·································································································································· 62
第4 章 队列 ········································································································································· 64
4.1 队列的基本概念 ··················································································································· 64
4.2 用指针实现队列 ··················································································································· 64
4.3 用循环数组实现队列 ··········································································································· 67
4.4 应用举例 ································································································································ 70
本章小结 ········································································································································· 74
习题4 ·············································································································································· 74
算法实验题4 ·································································································································· 75
第5 章 排序与选择算法 ····················································································································· 78
5.1 简单排序算法 ······················································································································· 78
5.1.1 冒泡排序算法 ················································································································· 79
5.1.2 插入排序算法 ················································································································· 79
5.1.3 选择排序算法 ················································································································· 80
5.1.4 简单排序算法的计算复杂性 ····························································································· 80
5.2 快速排序算法 ······················································································································· 81
5.2.1 算法基本思想及实现 ······································································································· 81
5.2.2 算法的性能 ····················································································································· 82
5.2.3 随机快速排序算法 ·········································································································· 83
5.2.4 非递归快速排序算法 ······································································································· 83
5.2.5 三数取中划分算法 ·········································································································· 84
5.2.6 三划分快速排序算法 ······································································································· 85
5.3 合并排序算法 ······················································································································· 86
5.3.1 算法基本思想及实现 ······································································································· 86
5.3.2 对基本算法的改进 ·········································································································· 87
5.3.3 自底向上的合并排序算法 ································································································ 88
5.3.4 自然合并排序算法 ·········································································································· 88
5.3.5 链表结构的合并排序算法 ································································································ 89
5.4 线性时间排序算法 ··············································································································· 90
VII
5.4.1 计数排序算法 ················································································································· 90
5.4.2 桶排序算法 ····················································································································· 91
5.4.3 基数排序算法 ················································································································· 92
5.5 中位数与第k 小元素 ············································································································ 94
5.5.1 平均情况下的线性时间选择算法 ······················································································ 94
5.5.2 最坏情况下的线性时间选择算法 ······················································································ 95
5.6 应用举例 ································································································································ 98
本章小结 ······································································································································· 100
习题5 ············································································································································ 100
算法实验题5 ································································································································ 101
第6 章 树 ··········································································································································· 104
6.1 树的定义 ······························································································································ 104
6.2 树的遍历 ······························································································································ 106
6.3 树的表示法 ·························································································································· 108
6.3.1 父结点数组表示法 ········································································································ 108
6.3.2 儿子链表表示法 ············································································································ 108
6.3.3 左儿子右兄弟表示法 ····································································································· 108
6.4 二叉树的基本概念 ············································································································· 109
6.5 二叉树的运算 ······················································································································ 111
6.6 二叉树的实现 ······················································································································ 112
6.6.1 二叉树的顺序存储结构··································································································· 112
6.6.2 二叉树的结点度表示法··································································································· 113
6.6.3 用指针实现二叉树 ········································································································· 113
6.7 线索二叉树 ··························································································································· 118
6.8 二叉搜索树 ··························································································································· 119
6.9 线段树 ·································································································································· 128
6.10 序列树 ································································································································ 134
6.11 应用举例 ···························································································································· 142
本章小结 ······································································································································· 147
习题6 ············································································································································ 147
算法实验题6 ································································································································ 149
第7 章 散列表 ··································································································································· 154
7.1 集合的基本概念 ················································································································· 154
7.1.1 集合的定义和记号 ········································································································ 154
7.1.2 定义在集合上的基本运算 ······························································································ 155
7.2 简单集合的实现方法 ········································································································· 156
7.2.1 用位向量实现集合 ········································································································ 156
7.2.2 用链表实现集合 ············································································································ 158
7.3 散列技术 ······························································································································ 161
7.3.1 符号表 ·························································································································· 161
VIII
7.3.2 开散列 ·························································································································· 163
7.3.3 闭散列 ·························································································································· 164
7.3.4 散列函数及其效率 ········································································································ 168
7.3.5 闭散列的重新散列技术·································································································· 169
7.4 应用举例 ······························································································································ 170
本章小结 ······································································································································· 171
习题7 ············································································································································ 172
算法实验题7 ································································································································ 173
第8 章 优先队列 ······························································································································· 176
8.1 优先队列的定义 ················································································································· 176
8.2 优先队列的简单实现 ········································································································· 177
8.3 优先级树和堆 ····················································································································· 177
8.4 用数组实现堆 ····················································································································· 179
8.5 可并优先队列 ····················································································································· 181
8.5.1 左偏树的定义 ··············································································································· 182
8.5.2 用左偏树实现可并优先队列 ··························································································· 182
8.6 应用举例 ······························································································································ 185
本章小结 ······································································································································· 190
习题8 ············································································································································ 190
算法实验题8 ································································································································ 191
第9 章 并查集 ··································································································································· 194
9.1 并查集的定义及其简单实现 ····························································································· 194
9.2 用父结点数组实现并查集 ································································································· 195
9.3 应用举例 ······························································································································ 198
本章小结 ······································································································································· 201
习题9 ············································································································································ 201
算法实验题9 ································································································································ 202
第10 章 图 ········································································································································· 205
10.1 图的基本概念 ··················································································································· 205
10.2 抽象数据类型图 ··············································································································· 208
10.3 图的表示法 ························································································································ 209
10.3.1 邻接矩阵表示法 ·········································································································· 209
10.3.2 邻接表表示法 ·············································································································· 209
10.3.3 紧缩邻接表表示法 ······································································································· 210
10.4 用邻接矩阵实现图 ············································································································ 211
10.4.1 用邻接矩阵实现赋权有向图 ·························································································· 211
10.4.2 用邻接矩阵实现赋权无向图 ························································································· 213
10.4.3 用邻接矩阵实现有向图 ································································································ 213
10.4.4 用邻接矩阵实现无向图 ································································································ 213
10.5 用邻接表实现图 ··············································································································· 214
IX
10.5.1 用邻接表实现有向图 ··································································································· 214
10.5.2 用邻接表实现无向图 ··································································································· 217
10.5.3 用邻接表实现赋权有向图 ···························································································· 218
10.5.4 用邻接表实现赋权无向图 ···························································································· 221
10.6 图的遍历 ···························································································································· 222
10.6.1 广度优先搜索 ·············································································································· 222
10.6.2 深度优先搜索 ·············································································································· 224
10.7 最短路径 ···························································································································· 225
10.7.1 单源最短路径 ·············································································································· 225
10.7.2 Bellman-Ford 最短路径算法 ························································································· 228
10.7.3 所有顶点对之间的最短路径 ························································································· 230
10.8 无圈有向图 ························································································································ 231
10.8.1 拓扑排序 ···················································································································· 231
10.8.2 DAG 的最短路径 ········································································································· 233
10.8.3 DAG 的最长路径 ········································································································· 234
10.8.4 DAG 所有顶点对之间的最短路径 ················································································ 234
10.9 最小支撑树 ························································································································ 235
10.9.1 最小支撑树性质 ·········································································································· 235
10.9.2 Prim 算法 ···················································································································· 235
10.9.3 Kruskal 算法 ················································································································ 237
10.10 图匹配 ······························································································································ 239
10.11 应用举例 ·························································································································· 241
本章小结 ······································································································································· 243
习题10 ·········································································································································· 244
算法实验题10 ······························································································································ 245
参考文献 ··············································································································································· 250