本书为普通高等教育“十一五”*规划教材。 本书内容分为3部分：算法和算法分析、算法设计策略、求解困难问题。第1部分介绍问题求解方法、算法复杂度和分析、递归算法和递推关系；第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分介绍NP完全问题、*算法、近似算法、遗传算法和密码算法，其中遗传算法是本次修订新增的内容。书中还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法，并对现代密码学做了简要论述。
教授，南京邮电大学计算机学院，主持了多项信息产业部基金项目的研究工作，并负责了多项企业办公自动化和信息管理网络系统的研制开发。出版多本教材。曾获江苏省普通高校教学成果三等奖，其主持的《数据结构》课程获江苏省高校一类优秀课程。
目 录
第1部分 算法和算法分析
第1章 算法问题求解基础1
1.1 算法概述1
1.1.1 什么是算法1
1.1.2 为什么学习算法3
1.2 问题求解方法3
1.2.1 问题和问题求解4
1.2.2 问题求解过程4
1.2.3 系统生命周期5
1.3 算法设计与分析5
1.3.1 算法问题求解过程5
1.3.2 如何设计算法6
1.3.3 如何表示算法6
1.3.4 如何确认算法6
1.3.5 如何分析算法7
1.4 递归和归纳7
1.4.1 递归7
1.4.2 递归算法示例9
1.4.3 归纳证明11
本章小结12
习题113
第2章 算法分析基础14
2.1 算法复杂度14
2.1.1 什么是好的算法14
2.1.2 影响程序运行时间的因素15
2.1.3 算法的时间复杂度16
2.1.4 使用程序步分析算法17
2.1.5 算法的空间复杂度18
2.2 渐近表示法19
2.2.1 大O记号19
2.2.2 ?记号20
2.2.3 ?记号21
2.2.4 小o记号21
2.2.5 算法按时间复杂度分类21
2.3 递推关系22
2.3.1 递推方程22
2.3.2 替换方法23
2.3.3 迭代方法23
2.3.4 主方法24
2.4 分摊分析25
2.4.1 聚集方法26
2.4.2 会计方法26
2.4.3 势能方法27
本章小结28
习题228
第3章 伸展树与跳表30
3.1 伸展树30
3.1.1 二叉搜索树30
3.1.2 自调节树和伸展树30
3.1.3 伸展操作31
3.1.4 伸展树类32
3.1.5 旋转的实现34
3.1.6 插入运算的实现34
3.1.7 分摊分析36
3.2 跳表38
3.2.1 什么是跳表38
3.2.2 跳表类39
3.2.3 级数分配41
3.2.4 插入运算的实现42
3.2.5 性能分析43
本章小结44
习题344
第2部分 算法设计策略
第4章 基本搜索和遍历方法45
4.1 基本概念45
4.2 图的搜索和遍历46
4.2.1 搜索方法46
4.2.2 邻接表类47
4.2.3 广度优先搜索48
4.2.4 深度优先搜索50
4.3 双连通分量53
4.3.1 基本概念53
4.3.2 发现关节点54
4.3.3 构造双连通图57
4.4 与或图58
4.4.1 问题分解58
4.4.2 判断与或树是否可解59
4.4.3 构建解树61
本章小结62
习题462
第5章 分治法64
5.1 一般方法64
5.1.1 分治法的基本思想64
5.1.2 算法分析65
5.1.3 数据结构66
5.2 求最大最小元67
5.2.1 分治法求解67
5.2.2 时间分析68
5.3 二分搜索69
5.3.1 分治法求解69
5.3.2 对半搜索70
5.3.3 二叉判定树71
5.3.4 搜索算法的时间下界73
5.4 排序问题74
5.4.1 合并排序74
5.4.2 快速排序76
5.4.3 排序算法的时间下界80
5.5 选择问题82
5.5.1 分治法求解82
5.5.2 随机选择主元82
5.5.3 线性时间选择算法84
5.5.4 时间分析86
5.5.5 允许重复元素的选择算法86
5.6 斯特拉森矩阵乘法87
5.6.1 分治法求解87
5.6.2 斯特拉森分治法88
本章小结88
习题588
第6章 贪心法91
6.1 一般方法91
6.2 背包问题92
6.2.1 问题描述92
6.2.2 贪心法求解92
6.2.3 算法正确性94
6.3 带时限的作业排序95
6.3.1 问题描述95
6.3.2 贪心法求解95
6.3.3 算法正确性97
6.3.4 可行性判定97
6.3.5 作业排序贪心算法98
6.3.6 一种改进算法99
6.4 最佳合并模式102
6.4.1 问题描述102
6.4.2 贪心法求解103
6.4.3 算法正确性104
6.5 最小代价生成树105
6.5.1 问题描述105
6.5.2 贪心法求解105
6.5.3 普里姆算法106
6.5.4 克鲁斯卡尔算法109
6.5.5 算法正确性111
6.6 单源最短路径111
6.6.1 问题描述112
6.6.2 贪心法求解112
6.6.3 迪杰斯特拉算法112
6.6.4 算法正确性115
6.7 磁带最优存储116
6.7.1 单带最优存储116
6.7.2 多带最优存储117
6.8 贪心法的基本要素119
6.8.1 最优量度标准119
6.8.2 最优子结构119
本章小结120
习题6120
第7章 动态规划法122
7.1 一般方法和基本要素122
7.1.1 一般方法122
7.1.2 基本要素123
7.1.3 多段图问题123
7.1.4 资源分配问题126
7.1.5 关键路径问题127
7.2 每对结点间的最短路径129
7.2.1 问题描述129
7.2.2 动态规划法求解130
7.2.3 弗洛伊德算法131
7.2.4 算法正确性132
7.3 矩阵连乘132
7.3.1 问题描述132
7.3.2 动态规划法求解133
7.3.3 矩阵连乘算法134
7.3.4 备忘录方法136
7.4 最长公共子序列137
7.4.1 问题描述137
7.4.2 动态规划法求解137
7.4.3 最长公共子序列算法138
7.4.4 算法的改进140
7.5 最优二叉搜索树140
7.5.1 问题描述140
7.5.2 动态规划法求解141
7.5.3 最优二叉搜索树算法143
7.6 0/1背包144
7.6.1 问题描述144
7.6.2 动态规划法求解145
7.6.3 0/1背包算法框架147
7.6.4 0/1背包算法150
7.6.5 性能分析152
7.6.6 使用启发式方法153
7.7 流水作业调度154
7.7.1 问题描述154
7.7.2 动态规划法求解155
7.7.3 Johnson算法157
本章小结158
习题7158
第8章 回溯法160
8.1 一般方法160
8.1.1 基本概念160
8.1.2 剪枝函数和回溯法161
8.1.3 回溯法的效率分析163
8.2 n-皇后163
8.2.1 问题描述163
8.2.2 回溯法求解164
8.2.3 n-皇后算法165
8.2.4 时间分析166
8.3 子集和数167
8.3.1 问题描述167
8.3.2 回溯法求解167
8.3.3 子集和数算法168
8.4 图的着色170
8.4.1 问题描述170
8.4.2 回溯法求解170
8.4.3 图着色算法171
8.4.4 时间分析172
8.5 哈密顿环172
8.5.1 问题描述172
8.5.2 哈密顿环算法173
8.6 0/1背包174
8.6.1 问题描述174
8.6.2 回溯法求解174
8.6.3 限界函数175
8.6.4 0/1背包算法176
8.7 批处理作业调度178
8.7.1 问题描述178
8.7.2 回溯法求解178
8.7.3 批处理作业调度算法178
本章小结180
习题8180
第9章 分枝限界法182
9.1 一般方法182
9.1.1 分枝限界法概述182
9.1.2 LC分枝限界法184
9.1.3 15谜问题185
9.2 求最优解的分枝限界法187
9.2.1 上下界函数187
9.2.2 FIFO分枝限界法188
9.2.3 LC分枝限界法189
9.3 带时限的作业排序190
9.3.1 问题描述190
9.3.2 分枝限界法求解190
9.3.3 带时限作业排序算法191
9.4 0/1背包193
9.4.1 问题描述193
9.4.2 分枝限界法求解194
9.4.3 0/1背包算法195
9.5 旅行商问题197
9.5.1 问题描述197
9.5.2 分枝限界法求解198
9.6 批处理作业调度201
9.6.1 问题描述201
9.6.2 分枝限界法求解201
9.6.3 批处理作业调度算法202
本章小结205
习题9205
第3部分 求解困难问题
第10章 NP完全问题207
10.1 基本概念207
10.1.1 不确定算法和不确定机208
10.1.2 可满足性问题210
10.1.3 P类和NP类问题211
10.1.4 NP难度和NP完全问题211
10.2 Cook定理和证明212
10.2.1 Cook定理212
10.2.2 简化的不确定机模型212
10.2.3 证明Cook定理214
10.3 一些典型的NP完全问题217
10.3.1 最大集团217
10.3.2 顶点覆盖218
10.3.3 三元CNF可满足性219
10.3.4 图的着色数220
10.3.5 有向哈密顿环221
10.3.6 恰切覆盖223
10.3.7 子集和数225
10.3.8 分划问题225
本章小结226
习题10226
第11章 随机算法228
11.1 基本概念228
11.1.1 随机算法概述228
11.1.2 随机数发生器228
11.1.3 随机算法分类228
11.2 拉斯维加斯算法229
11.2.1 标识重复元素算法229
11.2.2 性能分析230
11.3 蒙特卡罗算法231
11.3.1 素数测试问题231
11.3.2 伪素数测试231
11.3.3 米勒-拉宾算法232
11.3.4 性能分析233
11.4 舍伍德算法234
11.4.1 随机快速排序算法234
11.4.2 舍伍德算法的其他应用234
本章小结234
习题11235
第12章 近似算法236
12.1 近似算法的性能236
12.1.1 基本概念236
12.1.2 绝对性能保证236
12.1.3 相对性能保证237
12.1.4 近似方案238
12.2 绝对近似算法238
12.2.1 最多程序存储问题238
12.2.2 NP难度绝对近似算法239
12.3 ?-近似算法240
12.3.1 顶点覆盖近似算法240
12.3.2 旅行商问题241
12.3.3 NP难度?-近似旅行商问题242
12.3.4 具有三角不等式性质的旅行商问题243
12.3.5 任务调度近似算法244
12.4 ?(n)-近似算法247
12.4.1 集合覆盖问题247
12.4.2 集合覆盖近似算法247
12.4.3 ln(n)-近似算法248
12.5 多项式时间近似方案249
12.5.1 任务调度近似方案249
12.5.2 多项式时间近似方案251
12.6 子集和数的完全多项式时间近似方案251
12.6.1 子集和数的指数时间算法251
12.6.2 完全多项式时间近似方案252
本章小结254
习题12254
第13章 遗传算法256
13.1 进化计算256
13.2 遗传算法的生物学基础257
13.3 遗传算法的基本思想258
13.4 基本遗传算法259
13.4.1 基本遗传算法构成要素259
13.4.2 基本遗传算法流程图262
13.5 遗传算法的特点和应用262
13.5.1 遗传算法的特点2
当前图书最新荐购
