第1章 绪论 1
1.1 引论 1
1.2 从问题到程序 3
1.3 抽象数据类型 7
1.4 算法的分析 13
1.4.1 算法设计 13
1.4.2 算法的复杂性测度 14
1.5 算法描述及语句简介 16
1.5.1 C中的标准数据类型 17
1.5.2 C中的运算符 18
1.5.3 C中的语句简介 19
小结 22
练习一 22
一、填空题 22
二、选择题 23
三、简答题 24
第2章 递归技术 25
2.1 递归过程 25
2.2 递归技术 26
2.3 递归过程的实现 29
2.4 递归函数 29
2.5 递归方程 33
2.6 递归方程求解 35
2.6.1 迭代法 36
2.6.2 套用差分方程法 37
2.6.3 套用公式法 38
2.6.4 生成函数与求和 39
2.7 递归消除 42
2.7.1 简单递归消除 42
2.7.2 基于栈的递归消除 44
小结 46
练习二 46
一、填空题 46
二、选择题 46
三、简答题 47
第3章 树 48
3.1 树的结构定义及基本操作 48
3.2 二叉树 51
3.2.1 定义及基本操作 51
3.2.2 二叉树性质 52
3.2.3 二叉树存储结构 54
3.3 遍历二叉树和线索二叉树 57
3.3.1 遍历二叉树 58
3.3.2 线索二叉树 60
3.4 树和森林 64
3.4.1 树的存储结构 64
3.4.2 树和森林的遍历 67
3.4.3 森林与二叉树的转换 68
3.5 树的计数 73
3.6 哈夫曼树 74
小结 77
练习三 78
一、填空题 78
二、选择题 78
三、简答题 79
第4章 图及有向图的应用 81
4.1 基本定义与术语 81
4.2 图的存储结构 84
4.2.1 图的邻接矩阵表示法 84
4.2.2 邻接表表示法 86
4.3 图的遍历 88
4.3.1 深度优先搜索 89
4.3.2 广度优先搜索 91
4.4 单源最短路径问题 93
4.5 顶点对之间最短路径 95
4.6 拓扑排序 97
4.7 关键路径 101
小结 104
练习四 104
一、填空题 104
二、选择题 105
三、简答题 106
第5章 无向图 108
5.1 最小生成树 108
5.1.1 最小生成树性质 109
5.1.2 Prim算法 109
5.1.3 Kruskal算法 111
5.2 无向图遍历 113
5.3 迷宫问题 114
5.4 最短路径 117
小结 120
练习五 120
一、填空题 120
二、选择题 120
三、简答题 121
第6章 查找 123
6.1 基本概念 123
6.2 顺序表查找 124
6.2.1 顺序查找 125
6.2.2 折半查找 126
6.3 分块查找 128
6.4 树表 130
6.5 散列表的查找 141
6.5.1 散列表的概念 142
6.5.2 散列函数的构造 142
6.5.3 处理冲突的方法 144
6.5.4 散列表分析 145
小结 146
练习六 146
一、填空题 146
二、选择题 147
三、简答题 149
第7章 排序 150
7.1 排序的定义 150
7.2 交换排序 151
7.2.1 冒泡法排序 151
7.2.2 快速排序 153
7.3 插入法排序 156
7.3.1 直接插入排序 156
7.3.2 希尔排序 157
7.4 选择排序 158
7.4.1 简单选择排序 158
7.4.2 堆排序 159
7.5 归并排序 161
7.5.1 排序文件的合并 162
7.5.2 二路归并排序 162
7.6 基数排序 163
7.7 各种内部排序方法的比较和选择 165
小结 166
练习七 166
一、填空题 166
二、选择题 167
三、简答题 168
第8章 集合操作 170
8.1 集合的基本概念 170
8.1.1 集合的概念 170
8.1.2 集合的表示法 170
8.1.3 常见的一些集合 171
8.1.4 集合间的关系 171
8.1.5 集合例题 171
8.2 集合的基本运算 172
8.2.1 集合的运算 172
8.2.2 文氏图 173
8.2.3 集合运算律 174
8.2.4 集合论进一步研究 175
8.3 链表结构与顺序搜索 176
8.3.1 链表结构 176
8.3.2 链表的运算 179
小结 181
练习八 181
一、填空题 181
二、选择题 181
三、简答题 182
第9章 动态规划 183
9.1 动态规划法的概念 183
9.1.1 动态规划模型的基本要素 184
9.1.2 动态规划的基本定理和基本方程 184
9.1.3 动态规划法的基本步骤 186
9.1.4 动态规划与其他算法的比较 186
9.2 计算二项式系数 187
9.3 最佳折半查找树 188
9.3.1 查找树的期望深度 189
9.3.2 最佳折半查找树的动态规划算法 190
9.4 资源分配问题 191
9.5 多机系统的可靠性设计 193
9.6 背包问题 195
9.7 货郎担问题 196
小结 198
练习九 198
一、填空题 198
二、选择题 199
三、简答题 199
第10章 贪心法 201
10.1 贪心算法 201
10.2 背包问题 202
10.3 多处理机调度 205
10.4 单源最短路径 210
10.5 最佳合并顺序 212
小结 213
练习十 214
一、填空题 214
二、选择题 214
三、简答题 214
第11章 回溯法 215
11.1 一般方法 215
11.2 效能统计 218
11.3 哈密尔顿回路 220
11.4 图的可着色性 223
11.5 子集和问题 224
小结 225
练习十一 225
一、填空题 225
二、选择题 225
三、简答题 225
第12章 分治与平衡 227
12.1 分治算法 227
12.2 合并排序 230
12.3 快速排序 231
12.4 整数乘法和矩阵乘法 237
12.4.1 整数乘法 237
12.4.2 strassen矩阵乘法 239
12.5 马的周游路线问题 241
小结 243
练习十二 244
一、填空题 244
二、选择题 244
三、简答题 244
第13章 NP完全问题 245
13.1 确定图灵机 245
13.2 不确定图灵机 249
13.3 P和NP类 251
13.4 NP完全性和COOK定理 254
13.5 若干NP完全问题 258
小结 260
练习十三 261
一、填空题 261
二、选择题 261
三、简答题 261
参考文献 262
鄂公网安备 42010302001612号 