国家精品在线开放课程配套教材 西安交通大学计算机基础系列教材 算法设计与问题求解PDF电子书下载

第1章 绪论 1

1.1算法的概念 1

1.1.1从计算机的优势和劣势谈起 1

1.1.2问题和算法 2

1.1.3什么是算法 4

1.2算法设计的要求 5

1.3算法效率的度量 6

1.3.1时间复杂度 6

1.3.2空间复杂度 7

1.4本书的总体结构 8

1.5相关语言和函数库简介 8

1.5.1从C到C＋＋ 9

1.5.2C＋＋语言的功能改进 10

1.5.3命名空间 12

1.5.4C＋＋的输入输出 14

1.5.5函数重载和函数模板 16

1.5.6面向对象初步 20

1.5.7string类 22

习题 24

第2章 若干数学问题的算法 25

2.1数论相关问题 25

2.2多项式四则运算 29

2.2.1一元多项式乘法 29

2.2.2一元多项式除法 32

2.3多项式插值问题 33

2.3.1拉格朗日插值法 33

2.3.2牛顿插值法 36

2.4非线性方程求解 38

2.4.1二分法 39

2.4.2牛顿迭代法 41

2.5线性方程组求解 42

2.5.1雅克比迭代法 42

2.5.2高斯消去法 46

2.6一元线性回归 51

习题 55

第3章 线性结构的妙用 57

3.1数据结构基本概念 57

3.2线性表概念及应用 58

3.2.1线性表基本概念 58

3.2.2顺序表概念及实现 59

3.2.3顺序表应用：学生名册管理 69

3.2.4链表的概念及实现 72

3.2.5单链表应用：通讯录管理 83

3.3堆栈和队列的应用 87

3.3.1堆栈的概念及实现 87

3.3.2堆栈应用：表达式求值 92

3.3.3队列的概念及实现 94

3.3.4队列应用：整数排序 101

3.3.5优先队列的概念及实现 103

习题 109

第4章 哈夫曼编码和图的最短路径 111

4.1树和二叉树 111

4.1.1树 111

4.1.2二叉树 113

4.2二叉树的实现与分析 114

4.3二叉树的遍历 124

4.3.1二叉树的遍历方式 124

4.3.2遍历算法的实现 125

4.4二叉树的示例 128

4.5哈夫曼树 134

4.5.1哈夫曼树和哈夫曼编码 134

4.5.2构造哈夫曼编码 136

4.5.3哈夫曼编码实现 136

4.6图和邻接表 145

4.6.1图的存储 145

4.6.2图的搜索 146

4.7图的最短路径 153

习题 157

第5章 马踏棋盘与道路规划 159

5.1贪心算法 159

5.2活动安排问题 160

5.3马踏棋盘问题 166

5.4道路规划和最小生成树问题 174

5.4.1Prim算法 175

5.4.2Kruskal算法 182

习题 188

第6章 动态规划 189

6.1动态规划基本概念 189

6.1.1挖金矿问题 189

6.1.2动态规划算法的基本思想 192

6.1.3适用情况 192

6.1.4求解基本步骤 192

6.2 0-1背包问题 196

6.2.1最优性原理 197

6.2.2递推关系 197

6.2.3构造最优解 198

6.2.4算法实现 198

6.3最长公共子序列问题 201

6.3.1最长公共子序列的结构 202

6.3.2子问题的递归结构 202

6.3.3计算最优值 203

6.3.4构造最长公共子序列 203

6.3.5算法实现 204

6.4最大流问题 206

6.4.1流网络 206

6.4.2Ford-Fulkerson方法 209

6.4.3Ford-Fulkerson方法伪代码 209

6.4.4最小费用最大流 209

6.4.5动态规划与最大流问题 212

习题 213

第7章 遗传算法 217

7.1遗传算法的概念 217

7.2遗传算法的设计 218

7.3函数最值问题求解 220

7.4函数最值问题求解程序实现 222

7.5旅行商问题 230

习题 241

第8章 人工神经网络 243

8.1人工神经网络的概念 243

8.2感知器 246

8.3感知器算法 247

8.4BP算法 251

8.5BP算法中正向传播过程及代价函数的编程实现 252

8.6BP算法示例 258

习题 269

参考文献 271