程序基本算法教程PDF电子书下载

第1章 程序与算法 1

1.1 计算机基础知识 1

1.1.1 硬件 1

1.1.2 软件 2

1.2 程序设计 3

1.2.1 程序设计内容 3

1.2.2 程序设计过程 3

1.3 算法 3

1.3.1 五个属性 5

1.3.2 三个层次 5

1.4 算法复杂性 6

1.4.1 空间复杂度 6

1.4.2 时间复杂度 7

1.4.3 算法评价标准 7

1.4.4 算法效率 8

1.5 算法表示方式 10

1.5.1 程序流程图 10

1.5.2 N-S图 10

1.5.3 伪语言 11

1.6 习题 11

第2章 程序设计语言 13

2.1 程序设计语言演变历史 13

2.1.1 机器语言 13

2.1.2 汇编语言 13

2.1.3 面向过程设计语言 13

2.1.4 面向对象程序设计语言 14

2.1.5 智能化语言 14

2.2 结构化程序设计 14

2.2.1 自顶向下 14

2.2.2 逐步细化 14

2.2.3 模块化设计 15

2.2.4 结构化编码 15

2.3 三种基本结构 15

2.3.1 顺序结构 16

2.3.2 选择结构 16

2.3.3 循环结构 17

2.4 高级程序设计语言的基本结构 18

2.4.1 面向过程程序设计语言 18

2.4.2 面向对象程序设计语言 19

2.5 代码书写规则 20

2.5.1 缩进 20

2.5.2 逻辑行与物理行 20

2.5.3 注释 21

2.5.4 编码习惯 21

2.6 程序调试 22

2.6.1 调试策略 23

2.6.2 三种调试工具 23

2.7 选择语言的标准 25

2.7.1 项目应用领域 25

2.7.2 算法复杂度 25

2.7.3 数据结构复杂性 25

2.7.4 开发人员水平 26

2.8 习题 26

第3章 数据结构 27

3.1 概述 27

3.2 线性表 27

3.2.1 相关概念 27

3.2.2 线性表存储 28

3.3 栈 32

3.3.1 相关概念 32

3.3.2 栈的存储 32

3.4 队列 34

3.4.1 概念 34

3.4.2 队列存储 34

3.5 树 39

3.5.1 相关概念 39

3.5.2 二叉树的性质 40

3.5.3 二叉树存储 41

3.5.4 二叉树遍历 42

3.5.5 二叉树创建 46

3.6 图 46

3.6.1 相关概念 46

3.6.2 图的存储 47

3.6.3 图的遍历 52

3.6.4 最小生成树 55

3.6.5 最短路径 57

3.7 习题 61

第4章 查找与排序 63

4.1 查找 63

4.1.1 顺序查找 63

4.1.2 折半查找 63

4.1.3 分块查找 65

4.2 排序 66

4.2.1 插入类 67

4.2.2 交换类 70

4.2.3 选择类 72

4.2.4 归并类 78

4.3 排序法总结 79

4.3.1 时间性能 79

4.3.2 空间性能 79

4.3.3 稳定性能 79

4.4 习题 80

第5章 穷举法 82

5.1 概述 82

5.2 例题 82

5.2.1 杨辉三角形 82

5.2.2 螺旋数阵 84

5.2.3 百钱买百鸡 84

5.2.4 啤酒和饮料 86

5.3 有意思的数 87

5.3.1 素数 87

5.3.2 孪生素数 88

5.3.3 回文素数 89

5.3.4 水仙花数 90

5.3.5 北斗七星数 91

5.3.6 完全数 92

5.3.7 倒序数 93

5.4 习题 93

第6章 递归法 94

6.1 概述 94

6.1.1 简介 94

6.1.2 内存组织方式 95

6.1.3 递归适用场合 95

6.2 基本递归 96

6.2.1 相关概念 96

6.2.2 基本递归运行原理 97

6.3 尾递归 98

6.3.1 相关概念 98

6.3.2 尾递归运行原理 98

6.4 相似术语解析 99

6.4.1 递归与循环 99

6.4.2 迭代和递推 99

6.4.3 迭代与遍历 100

6.4.4 递归和递推 100

6.5 例题 103

6.5.1 最大公约数 103

6.5.2 最近公共子结点 105

6.5.3 汉诺塔问题 106

6.5.4 平面划分 107

6.5.5 切面条 109

6.5.6 全排列问题 110

6.5.7 整数划分问题 112

6.6 习题 113

第7章 分治法 114

7.1 概述 114

7.2 从求数组最值谈起 114

7.3 算法框架 120

7.4 查找与排序中的分治法 122

7.4.1 二分查找算法 122

7.4.2 快速排序算法 123

7.5 乘法中的分治法 126

7.5.1 大整数乘法 126

7.5.2 Strassen矩阵乘法 128

7.6 棋盘覆盖问题 132

7.7 习题 135

第8章 动态规划法 136

8.1 概述 136

8.2 矩阵连乘积问题 136

8.3 字符串相似度问题 144

8.3.1 最长公共子序列问题 144

8.3.2 编辑距离问题 149

8.4 数字三角形问题 151

8.5 0-1背包问题 152

8.6 习题 154

第9章 贪心法 156

9.1 概述 156

9.2 活动安排问题 157

9.3 贪心算法和动态规划算法关系 159

9.4 最优装载问题 161

9.5 最优分解问题 163

9.6 单源最短路径问题 164

9.7 习题 168

第10章 回溯法 170

10.1 概述 170

10.2 从0-1背包问题看回溯法的算法框架 170

10.3 装载问题 175

10.4 批处理作业调度问题 177

10.5 n皇后问题 179

10.6 最小重量机器设计问题 181

10.7 工作分配问题 182

10.8 习题 183

附录 各类软件竞赛 184

A.1 计算机认证考试 184

A.2 全国计算机等级考试 184

A.3 计算机技术与软件专业技术资格（水平）考试 185

A.4 ACM国际大学生程序设计竞赛 185

A.5 蓝桥杯 185

A.6 全国Java程序设计大赛 186

参考文献 187