算法分析与设计PDF电子书下载

第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.1　定义及基本操作 51

3.2　二叉树 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.1 冒泡法排序 151

7.2　交换排序 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.1　集合的运算 172

8.2　集合的基本运算 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.1　动态规划法的概念 183

第9章　动态规划 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