C/C++常用算法手册 第3版PDF电子书下载

第1篇 算法基础篇 1

第1章 算法概述 1

1.1 什么是算法 1

1.2 算法的发展历史 2

1.3 算法的分类 3

1.4 算法相关概念的区别 3

1.5 算法的表示 4

1.5.1 自然语言表示 4

1.5.2 流程图表示 5

1.5.3 N-S图表示 6

1.5.4 伪代码表示 6

1.6 伪代码与算法程序的对应 7

1.6.1 基本对应规则 7

1.6.2 分支结构 8

1.6.3 循环结构 9

1.6.4 数组及函数 9

1.7 算法的性能评价 10

1.8 算法实例 10

1.8.1 查找数字 11

【程序示例1-1】在拥有20个整数数据的数组中查找某个数据 11

1.8.2 创建项目 12

1.8.3 编译执行 13

1.9 算法的新进展 14

1.10 小结 15

第2章 数据结构 16

2.1 数据结构概述 16

2.1.1 什么是数据结构 16

2.1.2 数据结构中的基本概念 17

2.1.3 数据结构的内容 17

2.1.4 数据结构的分类 19

2.1.5 数据结构的几种存储方式 19

2.1.6 数据类型 20

2.1.7 常用的数据结构 21

2.1.8 选择合适的数据结构解决实际问题 22

2.2 线性表 22

2.2.1 什么是线性表 22

2.2.2 线性表的基本运算 23

2.3 顺序表结构 23

2.3.1 准备数据 24

2.3.2 初始化顺序表 24

2.3.3 计算顺序表长度 25

2.3.4 插入结点 25

2.3.5 追加结点 25

2.3.6 删除结点 26

2.3.7 查找结点 26

2.3.8 显示所有结点 27

2.3.9 顺序表操作示例 27

【程序示例2-1】对某班级学生学号、姓名和年龄数据进行顺序表操作 27

2.4 链表结构 31

2.4.1 什么是链表结构 31

2.4.2 准备数据 32

2.4.3 追加结点 32

2.4.4 插入头结点 33

2.4.5 查找结点 34

2.4.6 插入结点 34

2.4.7 删除结点 35

2.4.8 计算链表长度 36

2.4.9 显示所有结点 37

2.4.10 链表操作示例 37

【程序示例2-2】使用链表操作实现用户管理 37

2.5 栈结构 41

2.5.1 什么是栈结构 41

2.5.2 准备数据 42

2.5.3 初始化栈结构 43

2.5.4 判断空栈 43

2.5.5 判断满栈 43

2.5.6 清空栈 44

2.5.7 释放空间 44

2.5.8 入栈 44

2.5.9 出栈 45

2.5.10 读结点数据 45

2.5.11 栈结构操作示例 45

【程序示例2-3】使用栈结构实现学生数据操作 45

2.6 队列结构 48

2.6.1 什么是队列结构 48

2.6.2 准备数据 49

2.6.3 初始化队列结构 49

2.6.4 判断空队列 50

2.6.5 判断满队列 50

2.6.6 清空队列 50

2.6.7 释放空间 51

2.6.8 入队列 51

2.6.9 出队列 52

2.6.10 读结点数据 52

2.6.11 计算队列长度 52

2.6.12 队列结构操作示例 53

【程序示例2-4】使用队列结构实现学生数据操作 53

2.7 树结构 56

2.7.1 什么是树结构 56

2.7.2 树的基本概念 57

2.7.3 二叉树 57

2.7.4 准备数据 61

2.7.5 初始化二叉树 61

2.7.6 添加结点 62

2.7.7 查找结点 63

2.7.8 获取左子树 64

2.7.9 获取右子树 64

2.7.10 判断空树 65

2.7.11 计算二叉树深度 65

2.7.12 清空二叉树 65

2.7.13 显示结点数据 66

2.7.14 遍历二叉树 66

2.7.15 树结构操作示例 68

【程序示例2-5】经典二叉树的遍历（4种遍历方式） 68

2.8 图结构 70

2.8.1 什么是图结构 71

2.8.2 图的基本概念 71

2.8.3 准备数据 75

2.8.4 创建图 77

2.8.5 清空图 78

2.8.6 显示图 78

2.8.7 遍历图 79

2.8.8 图结构操作示例 80

【程序示例2-6】使用深度优先遍历算法遍历图操作程序 80

2.9 小结 83

第3章 基本算法思想 84

3.1 常用算法思想概述 84

3.2 穷举算法思想 85

3.2.1 穷举算法基本思想 85

3.2.2 穷举算法示例 85

【程序示例3-1】鸡兔同笼问题 86

3.3 递推算法思想 87

3.3.1 递推算法基本思想 87

3.3.2 递推算法示例 87

【程序示例3-2】兔子产仔问题 88

3.4 递归算法思想 89

3.4.1 递归算法基本思想 89

3.4.2 递归算法示例 90

【程序示例3-3】求数字12的阶乘 90

3.5 分治算法思想 91

3.5.1 分治算法基本思想 91

3.5.2 分治算法示例 91

【程序示例3-4】从30枚银币中找出仅有的1枚假银币 93

3.6 概率算法思想 95

3.6.1 概率算法基本思想 95

3.6.2 概率算法示例 96

【程序示例3-5】利用蒙特卡罗算法计算圆周率π 96

3.7 小结 97

第2篇 算法应用篇 98

第4章 排序算法 98

4.1 排序算法概述 98

4.2 冒泡排序法 99

4.2.1 冒泡排序算法 99

4.2.2 冒泡排序算法示例 100

【程序示例4-1】对包含10个数字的整型数组进行排序 100

4.3 选择排序法 102

4.3.1 选择排序算法 102

4.3.2 选择排序算法示例 103

【程序示例4-2】对包含10个数字的整型数组进行排序 103

4.4 插入排序法 105

4.4.1 插入排序算法 105

4.4.2 插入排序算法示例 106

【程序示例4-3】对包含10个数字的整型数组进行排序 106

4.5 Shell排序法 108

4.5.1 Shell排序算法 108

4.5.2 Shell排序算法示例 109

【程序示例4-4】对包含10个数字的整型数组进行排序 109

4.6 快速排序法 111

4.6.1 快速排序算法 111

4.6.2 快速排序算法示例 112

【程序示例4-5】对包含18个数字的整型数组进行排序 112

4.7 堆排序法 114

4.7.1 堆排序算法 114

4.7.2 堆排序算法示例 119

【程序示例4-6】对包含10个数字的整型数组进行排序 119

4.8 合并排序法 121

4.8.1 合并排序算法 121

4.8.2 合并排序算法示例 124

【程序示例4-7】对包含15个数字的整型数组进行排序 124

4.9 排序算法的效率 127

4.10 排序算法的其他应用 128

4.10.1 反序排序 128

4.10.2 反序插入排序算法示例 129

【程序示例4-8】对包含10个数字的整型数组进行排序 129

4.10.3 字符串的排序 130

4.10.4 字符串排序示例 131

【程序示例4-9】用快速排序算法对包含16个字母的字符串进行排序 131

4.10.5 字符串数组的排序 133

4.10.6 字符串数组排序示例 134

【程序示例4-10】用快速排序算法对包含5个单词的字符串数组进行排序 134

4.11 小结 135

第5章 查找算法 136

5.1 查找算法概述 136

5.2 顺序查找 137

5.2.1 顺序查找算法 137

5.2.2 顺序查找操作示例 137

【程序示例5-1】在包含15个数字的数组中查找第7个数字 137

5.3 折半查找 139

5.3.1 折半查找算法 139

5.3.2 折半查找操作示例 141

【程序示例5-2】在包含15个数字的数组中查找第11个数字 141

5.4 小结 143

第6章 基本数学问题 144

6.1 判断闰年 144

【程序示例6-1】判断2000年到3000年之间所有的闰年 145

6.2 多项式计算 146

6.2.1 一维多项式求值 146

6.2.2 一维多项式求值示例 147

【程序示例6-2】计算多项式在x取不同值时的值 147

6.2.3 二维多项式求值 148

6.2.4 二维多项式求值示例 148

【程序示例6-3】求4x5的二维多项式在给定处的值 149

6.2.5 多项式乘法 150

6.2.6 多项式乘法示例 150

【程序示例6-4】计算两个多项式的乘积多项式 150

6.2.7 多项式除法 151

6.2.8 多项式除法示例 152

【程序示例6-5】计算A（x）/B（x）的商多项式和余多项式 153

6.3 随机数生成 154

6.3.1 C语言中的随机函数 154

【程序示例6-6】在0～32767之间产生一组随机数 154

【程序示例6-7】输出0～100之间的随机整数 155

6.3.2 ［0，1］之间均匀分布的随机数算法 156

【程序示例6-8】输出10个0～1之间的随机数 156

6.3.3 产生任意范围的随机数 157

【程序示例6-9】输出10个10.0～20.0之间的浮点随机数 157

6.3.4 ［m，n］之间均匀分布的随机整数算法 158

【程序示例6-10】输出10个100～200之间的随机整数 158

6.3.5 正态分布的随机数生成算法 159

【程序示例6-11】输出10个正态分布的随机数 160

6.4 复数运算 161

6.4.1 简单的复数运算 161

6.4.2 简单复数运算示例 163

【程序示例6-12】计算两个复数的加减乘除 163

6.4.3 复数的幂运算 164

6.4.4 复数的幂运算示例 164

【程序示例6-13】一个复数的n（n＝5）次幂运算 164

6.4.5 复指数运算 166

6.4.6 复指数运算示例 166

【程序示例614】一个复数的复指数运算 166

6.4.7 复对数运算 167

6.4.8 复对数运算示例 167

【程序示例6-15】一个复数的复对数计算 167

6.4.9 复正弦运算 168

6.4.10 复正弦运算示例 168

【程序示例6-16】一个复数的复正弦运算 168

6.4.11 复余弦运算 169

6.4.12 复余弦运算示例 170

【程序示例6-17】一个复数的复余弦运算 170

6.5 阶乘 170

6.5.1 使用循环计算阶乘 171

6.5.2 循环计算阶乘示例 171

【程序示例6-18】求输入整数的阶乘运算结果 171

6.6 计算π的近似值 172

6.6.1 割圆术 172

6.6.2 割圆术算法示例 174

【程序示例6-19】用割圆术计算圆周率π（根据输入的切割次数） 174

6.6.3 级数公式 175

6.6.4 级数公式算法示例 176

【程序示例6-20】用级数公式的算法计算圆周率π 176

6.7 矩阵运算 177

6.7.1 矩阵加法 177

6.7.2 矩阵加法示例 178

【程序示例6-21】计算两个矩阵相加 178

6.7.3 矩阵减法 179

6.7.4 矩阵减法示例 179

【程序示例6-22】计算两个矩阵相减 179

6.7.5 矩阵乘法 180

6.7.6 矩阵乘法示例 181

【程序示例6-23】计算两个矩阵相乘 181

6.8 方程求解 183

6.8.1 线性方程求解——高斯消元法 183

6.8.2 高斯消元法示例 186

【程序示例6-24】3个变量、3个方程的方程组的高斯消元法求解 186

6.8.3 非线性方程求解——二分法 188

6.8.4 二分法算法示例 189

【程序示例6-25】使用二分法来求方程的解 189

6.8.5 非线性方程求解——牛顿迭代法 190

6.8.6 牛顿迭代法示例 191

【程序示例6-26】使用牛顿迭代法求方程的解 191

6.9 小结 193

第7章 复杂的数值计算算法 194

7.1 拉格朗日插值 194

7.1.1 拉格朗日插值算法 194

7.1.2 拉格朗日插值示例 195

【程序示例7-1】给出10个数据点，求解x不同取值时的函数近似值 196

7.2 数值积分 198

7.2.1 数值积分算法 198

7.2.2 数值积分示例 199

【程序示例7-2】求解两个定积分的数值计算结果 199

7.3 开平方 201

7.3.1 开平方算法 201

7.3.2 开平方示例 201

【程序示例7-3】求解两个数字开方的数值计算结果 201

7.4 极值问题的求解算法 203

7.4.1 极值求解算法 203

7.4.2 迭代法极值求解示例 205

【程序示例7-4】给定函数和其对应的导函数，请对该函数求解 205

7.5 特殊函数的计算算法 209

7.5.1 伽玛函数算法 209

7.5.2 伽玛函数求解示例 210

【程序示例7-5】求解伽玛函数г（2.0）和г（3.0）的值 211

7.5.3 贝塔函数算法 213

7.5.4 贝塔函数求解示例 214

【程序示例7-6】求解贝塔函数B（2.0，3.0）和B（1.5 ，4.5 ）的值 214

7.5.5 正弦积分函数算法 216

7.5.6 正弦积分函数求解示例 217

【程序示例7-7】求解正弦积分函数Si（2.0）和Si（5.5 ）的值 218

7.5.7 余弦积分函数算法 220

7.5.8 余弦积分函数求解示例 221

【程序示例7-8】求解余弦积分函数Co（2.0）和Co（5.5 ）的值 221

7.5.9 指数积分函数算法 223

7.5.10 指数积分函数求解示例 225

【程序示例7-9】求解指数积分函数Ex（2.0）和Ex（5.5 ）的值 225

7.6 小结 227

第8章 经典数据结构问题 228

8.1 动态数组排序 228

8.1.1 动态数组的存储和排序算法 228

8.1.2 动态数组排序示例 229

【程序示例8-1】对以0结束的动态字符数组进行排序 229

8.2 约瑟夫环 231

8.2.1 约瑟夫环算法 232

8.2.2 约瑟夫环应用 233

【程序示例8-2】总数为41人，报数3者自杀，求解约瑟夫环的解 233

8.2.3 约瑟夫环推广应用算法 235

8.2.4 约瑟夫环推广应用 236

【程序示例8-3】n个人环坐（顺时针编号1、2、3…n），每人随机取一张写有数字的纸条，报数m者出列，同时其手中数字为新的出列数字，求解约瑟夫环 236

8.3 城市之间的最短总距离和最短距离 238

8.3.1 最短总距离算法 238

8.3.2 最短路径算法 241

8.3.3 最短总距离求解示例 243

【程序示例8-4】计算某地区5个城市间的最短总距离 243

8.4 括号匹配 247

8.4.1 括号匹配算法 248

8.4.2 括号匹配求解示例 249

【程序示例8-5】对以0结束的一组括号进行匹配 250

8.5 小结 253

第9章 数论问题 254

9.1 数论概述及分类 254

9.1.1 数论概述 254

9.1.2 数论的分类 255

9.1.3 基本概念 256

9.2 完全数 257

9.2.1 完全数概述 257

9.2.2 生成完全数算法 258

9.2.3 查找完全数算法示例 259

【程序示例9-1】查找10000以内的所有完全数 259

9.3 亲密数（对） 260

9.3.1 亲密数（对）概述 260

9.3.2 查找亲密数对算法 260

9.3.3 查找亲密数对算法示例 261

【程序示例9-2】查找5000以内的所有亲密数对 261

9.4 水仙花数 263

9.4.1 水仙花数概述 263

9.4.2 查找水仙花数算法 263

9.4.3 查找水仙花数算法示例 264

【程序示例9-3】查找3位数和4位数的水仙花数 264

9.5 自守数 266

9.5.1 自守数概述 266

9.5.2 查找自守数算法 267

9.5.3 查找自守数算法示例 268

【程序示例9-4】用两种算法查找1000以内和200000以内的自守数 268

9.6 最大公约数和最小公倍数 270

9.6.1 计算最大公约数算法——辗转相除法 270

9.6.2 计算最大公约数算法——Stein算法 271

9.6.3 计算最小公倍数算法 272

9.6.4 计算最大公约数示例 273

【程序示例9-5】用辗转相除法计算12和34的最大公约数 273

9.6.5 计算最小公倍数示例 274

【程序示例9-6】求12和34的最小公倍数 274

9.7 素数 275

9.7.1 素数概述 275

9.7.2 查找判断素数算法 276

9.7.3 查找判断素数算法示例 276

【程序示例9-7】查找判断1～1000之间的所有素数 276

9.8 回文素数 277

9.8.1 回文素数概述 277

9.8.2 查找判断回文素数算法 278

9.8.3 查找判断回文素数算法示例 279

【程序示例9-8】查找判断0～ 50000之间的回文素数 279

9.9 平方回文数 280

9.9.1 平方回文数概述 280

9.9.2 查找判断平方回文数算法 281

9.9.3 查找判断平方回文数算法示例 281

【程序示例9-9】判断查找1～1000之间哪些数的平方可以得到回文数 281

9.10 分解质因数 283

9.10.1 质因数分解算法 283

9.10.2 质因数分解算法示例 284

【程序示例9-10】对合数1155分解质因数 284

9.11 小结 285

第10章 算法经典趣题 286

10.1 百钱买百鸡 286

10.1.1 算法解析 286

10.1.2 求解示例 287

【程序示例10-1】百钱买鸡问题示例 287

10.2 五家共井 288

10.2.1 算法解析 288

10.2.2 求解示例 289

【程序示例10-2】五家共井问题示例 290

10.3 猴子吃桃 291

10.3.1 算法解析 291

10.3.2 求解示例 292

【程序示例10-3】猴子吃桃问题示例 292

10.4 舍罕王赏麦 293

10.4.1 算法解析 293

10.4.2 求解示例 294

【程序示例10-4】舍罕王赏麦问题示例 294

10.5 汉诺塔 295

10.5.1 算法解析 295

10.5.2 求解示例 296

【程序示例10-5】汉诺塔问题示例 297

10.6 窃贼问题 298

10.6.1 算法解析 298

10.6.2 求解示例 300

【程序示例10-6】窃贼问题示例 300

10.7 马踏棋盘 303

10.7.1 算法解析 303

10.7.2 求解示例 304

【程序示例10-7】马踏棋盘问题示例 304

10.8 八皇后问题 306

10.8.1 算法解析 306

10.8.2 求解示例 308

【程序示例10-8】八皇后问题示例 308

10.9 青蛙过河 310

10.9.1 算法解析 310

10.9.2 求解示例 311

【程序示例10-9】青蛙过河问题示例 311

10.10 三色旗 314

10.10.1 算法解析 314

10.10.2 求解示例 315

【程序示例10-10】三色旗问题示例 316

10.11 渔夫捕鱼 317

10.11.1 算法解析 318

10.11.2 求解示例 318

【程序示例10-11】渔夫捕鱼问题示例 318

10.12 爱因斯坦的阶梯 319

10.12.1 算法解析 320

10.12.2 求解示例 320

【程序示例10-12】爱因斯坦的阶梯问题示例 320

10.13 常胜将军 321

10.13.1 算法解析 321

10.13.2 求解示例 322

【程序示例10-13】常胜将军问题解析 322

10.14 三色球 324

10.14.1 算法解析 324

10.14.2 求解示例 324

【程序示例10-14】三色球问题示例 325

10.15 小结 326

第11章 游戏中的算法 327

11.1 扑克游戏问题——10点半 327

11.1.1 算法解析 327

11.1.2 求解示例 331

【程序示例11-1】 10点半扑克游戏示例 332

11.2 生命游戏 334

11.2.1 生命游戏的原理 334

11.2.2 算法解析 335

11.2.3 求解示例 337

【程序示例11-2】生命游戏示例 337

11.3 小结 341

第3篇 算法面试题篇 342

第12章 智商逻辑推理类面试题 342

12.1 脑筋急转弯 342

12.1.1 中国有多少辆汽车 342

12.1.2 下水道的盖子为什么是圆形的 343

12.1.3 分蛋糕 344

12.1.4 你怎样改造和重新设计一个ATM银行自动取款机 344

12.2 逻辑推理 345

12.2.1 哪个开关控制哪盏灯 345

12.2.2 戴帽子 346

12.2.3 海盗分金 347

12.2.4 罪犯认罪 348

12.2.5 找出质量不相同的球 349

12.2.6 有多少人及格 349

12.2.7 他说的是真话吗 350

12.3 计算推理 351

12.3.1 倒水问题 351

12.3.2 骗子购物 352

12.3.3 求最大的连续组合值（华为校园招聘笔试题） 353

12.3.4 巧妙过桥 354

12.3.5 字符移动（金山笔试题） 357

12.4 小结 358

第13章 数学能力测试 359

13.1 100盏灯 359

13.2 用笔画出经过9个点的4条直线 360

13.3 在9个点上画10条线 361

13.4 时、分和秒针重合问题 361

13.5 可以喝多少瓶汽水 364

13.6 怎样拿到第100号球 365

13.7 烧绳计时 366

第14章 算法常见面试题及解答 367

14.1 排序类算法面试题 367

14.1.1 排序算法效率 367

14.1.2 鸡尾酒排序算法 368

【程序示例14-1】用鸡尾酒排序算法对一组整数进行排序 368

14.1.3 文件排序 370

14.1.4 城市名称 371

【程序示例14-2】对任意输入的5个城市的拼音按照字母顺序重新排列输出 371

14.2 查找类算法面试题 372

14.2.1 递归求极值 372

【程序示例14-3】用递归法求10个整数中的最大值 372

14.2.2 寻找共同元素 373

【程序示例14-4】查找并输出两个整型数组中同时出现的元素 374

14.2.3 查找最大子串 375

【程序示例14-5】在一个由0和1组成的字符串中，查找0和1连续出现的最大次数 375

14.3 综合类算法面试题 377

14.3.1 求序列和 377

【程序示例14-6】求给出数据序列的前100项之和 377

14.3.2 递归求累加和 378

【程序示例14-7】用递归算法求1＋2＋3＋4＋…＋100之和 378

14.3.3 猜苹果数 379

【程序示例14-8】用递归算法计算给定题目中5个人各自拥有的苹果数 379

14.3.4 逆置字符串 380

【程序示例14-9】将一个输入的字符串在不额外开辟空间的情况下进行逆置 380

14.3.5 位运算求负数 381

【程序示例14-10】计算正整数20对应的负数（只可使用位运算实现） 381

14.4 小结 382

第15章 数据结构常见面试题及解答 383

15.1 基本数据结构面试题 383

15.1.1 如何实现数据缓存区 383

15.1.2 出栈队列 384

15.1.3 入栈队列 384

15.1.4 二叉树叶结点个数 385

15.1.5 有向图和无向图 386

15.2 数据结构应用面试题 386

15.2.1 设计包含min函数的栈 386

【程序示例15-1】在函数min、push及pop时间复杂度都是O（1）的情况下，设计包含min函数的栈 387

15.2.2 设计计算指定结点层数算法 390

【程序示例15-2】在给定的二叉树中，计算字符C的层数 390

15.2.3 链表法筛选成绩 391

【程序示例15-3】某班级8位学生的成绩已给出，使用链表结构及指针操作来输出及格的成绩分数 391

15.2.4 将二叉树转变成排序的双向链表 393

【程序示例 15-4】将给出的二叉树转换成一个排序的双向链表（不能创建新的结点，只调整数指针的方向） 393

15.2.5 单链表逆转 394

【程序示例15-5】编写算法将一个单链表实现逆转 395

15.3 小结 396

第4篇 算法高级应用篇 398

第16章 密码学算法 398

16.1 密码学概述 398

16.1.1 密码学的发展 398

16.1.2 密码学的基本概念 399

16.1.3 柯克霍夫斯原则 400

16.1.4 经典密码学算法 400

16.2 换位加密解密 401

16.2.1 换位加密解密算法 401

16.2.2 换位加密解密算法示例 404

16.3 替换加密解密 407

16.3.1 替换加密解密算法 407

16.3.2 替换加密解密算法示例 408

16.4 位加密解密 410

16.4.1 位加密解密算法 410

16.4.2 位加密解密算法示例 412

16.5 一次一密加密解密 413

16.5.1 一次一密加密解密算法 414

16.5.2 一次一密加密解密算法示例 415

16.6 小结 417

第17章 压缩与解压缩算法 418

17.1 压缩与解压缩概述 418

17.1.1 压缩与解压缩分类 418

17.1.2 典型的压缩解压缩算法 419

17.2 压缩算法 419

17.3 解压缩算法 422

17.4 压缩／解压缩示例 425

17.5 小结 428