C/C++常用算法手册 第3版PDF|Epub|txt|kindle电子书版本网盘下载

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