C/C++常用算法手册（含盘）

第1篇  算法基础篇
第1章  算法概述
1.1  什么是算法 2
1.2  算法的发展历史 3
1.3  算法的分类 4
1.4  算法相关概念的区别 4
1.5  算法的表示 5
1.5.1  自然语言表示 5
1.5.2  流程图表示 6
1.5.3  N-S图表示 7
1.5.4  伪代码表示 7
1.6  伪代码与算法程序的对应 8
1.6.1  基本对应规则 8
1.6.2  分支结构 9
1.6.2  循环结构 10
1.6.3  数组及函数 11
1.7  算法的性能评价 11
1.8  算法实例 12
1.8.1  查找数字 12
1.8.2  创建项目 13
1.8.3  编译执行 15
1.9  算法的新进展 16
1.10  小结 17
第2章  数据结构
2.1  数据结构概述 18
2.1.1  什么是数据结构 18
2.1.2  数据结构中的基本 19
2.1.3  数据结构的内容 19
2.1.4  数据结构的分类 21
2.1.5  数据结构的几种存储方式 21
2.1.6  数据类型 22
2.1.7  常用的数据结构 23
2.1.8  选择合适的数据结构解决实际问题 24
2.2  线性表 24
2.2.1  什么是线性表 25
2.2.2  线性表的基本运算 25
2.3  顺序表结构 26
2.3.1  准备数据 26
2.3.2  初始化顺序表 27
2.3.3  计算顺序表长度 27
2.3.4  插入结点 27
2.3.5  追加结点 28
2.3.6  删除结点 28
2.3.7  查找结点 29
2.3.8  显示所有结点 29
2.3.9  顺序表操作示例 30
2.4  链表结构 33
2.4.1  什么是链表结构 34
2.4.2  准备数据 35
2.4.3  追加结点 35
2.4.4  插入头结点 36
2.4.5  查找结点 37
2.4.6  插入结点 38
2.4.7  删除结点 39
2.4.8  计算链表长度 39
2.4.9  显示所有结点 40
2.4.10  链表操作示例 40
2.5  栈结构 45
2.5.1  什么是栈结构 45
2.5.2  准备数据 46
2.5.3  初始化栈结构 46
2.5.4  判断空栈 47
2.5.5  判断满栈 47
2.5.6  清空栈 47
2.5.7  释放空间 48
2.5.8  入栈 48
2.5.9  出栈 48
2.5.10  读结点数据 49
2.5.11  栈结构操作示例 49
2.6  队列结构 52
2.6.1  什么是队列结构 52
2.6.2  准备数据 53
2.6.3  初始化队列结构 53
2.6.4  判断空队列 54
2.6.5  判断满队列 54
2.6.6  清空队列 54
2.6.7  释放空间 55
2.6.8  入队列 55
2.6.9  出队列 56
2.6.10  读结点数据 56
2.6.11  计算队列长度 57
2.6.12  队列结构操作示例 57
2.7  树结构 60
2.7.1  什么是树结构 60
2.7.2  树的基本概念 61
2.7.3  二叉树 62
2.7.4  准备数据 65
2.7.5  初始化二叉树 65
2.7.6  添加结点 66
2.7.7  查找结点 68
2.7.8  获取左子树 68
2.7.9  获取右子树 69
2.7.10  判断空树 69
2.7.11  计算二叉树深度 69
2.7.12  清空二叉树 70
2.7.13  显示结点数据 70
2.7.14  遍历二叉树 71
2.7.15  树结构操作示例 73
2.8  图结构 75
2.8.1  什么是图结构 75
2.8.2  图的基本概念 76
2.8.3  准备数据 80
2.8.4  创建图 82
2.8.5  清空图 83
2.8.6  显示图 83
2.8.7  遍历图 84
2.8.8  图结构操作示例 85
2.9  小结 88
第3章  基本算法思想
3.1  常用算法思想概述 89
3.2  穷举算法思想 89
3.2.1  穷举算法基本思想 90
3.2.2  穷举算法示例 90
3.3  递推算法思想 92
3.3.1  递推算法基本思想 92
3.3.2  递推算法示例 92
3.4  递归算法思想 94
3.4.1  递归算法基本思想 94
3.4.2  递归算法示例 95
3.5  分治算法思想 96
3.5.1  分治算法基本思想 96
3.5.2  分治算法示例 96
3.6  概率算法思想 100
3.6.1  概率算法基本思想 100
3.6.2  概率算法示例 101
3.7  小结 103
 
第2篇  算法基本应用篇
 
第4章  排序算法
4.1  排序算法概述 106
4.2  冒泡排序法 107
4.2.1  冒泡排序算法 107
4.2.2  冒泡排序算法示例 108
4.3  选择排序法 110
4.3.1  选择排序算法 110
4.3.2  选择排序算法示例 111
4.4  插入排序法 113
4.4.1  插入排序算法 113
4.4.2  插入排序算法示例 114
4.5  Shell排序法 116
4.5.1  Shell排序算法 116
4.5.2  Shell排序算法示例 117
4.6  快速排序法 119
4.6.1  快速排序算法 119
4.6.2  快速排序算法示例 121
4.7  堆 排 序 法 123
4.7.1  堆排序算法 123
4.7.2  堆排序算法示例 128
4.8  合并排序法 130
4.8.1  合并排序算法 130
4.8.2  合并排序算法示例 133
4.9  排序算法的效率 136
4.10  排序算法的其他应用 137
4.10.1  反序排序 137
4.10.2  字符串数组的排序 140
4.10.3  字符串的排序 142
4.11  小结 145
第5章  查找算法
5.1  查找算法概述 146
5.2  顺序查找 147
5.2.1  顺序查找算法 147
5.2.2  顺序查找操作示例 147
5.3  折半查找 149
5.3.1  折半查找算法 149
5.3.2  折半查找操作示例 151
5.4  数据结构中的查找算法 153
5.4.1  顺序表结构中的查找算法 153
5.4.2  链表结构中的查找算法 157
5.4.3  树结构中的查找算法 160
5.4.4  图结构中的查找算法 161
5.5  小结 162
第6章  基本数学问题
6.1  判断闰年 163
6.2  多项式计算 165
6.2.1  一维多项式求值 165
6.2.2  二维多项式求值 167
6.2.3  多项式乘法 169
6.2.4  多项式除法 171
6.3  随机数生成算法 173
6.4  复数运算 181
6.4.1  简单的复数运算 181
6.4.2  复数的幂运算 184
6.4.3  复指数运算 186
6.4.4  复对数运算 187
6.4.5  复正弦运算 188
6.4.6  复余弦运算 189
6.5  阶乘 190
6.6  计算π的近似值 193
6.6.1  割圆术 193
6.6.2  蒙特卡罗算法 196
6.6.3  级数公式 198
6.7  矩阵运算 200
6.7.1  矩阵加法 200
6.7.2  矩阵减法 202
6.7.3  矩阵乘法 204
6.8  方 程 求 解 206
6.8.1  线性方程求解——高斯消元法 206
6.8.2  非线性方程求解——二分法 211
6.8.3  非线性方程求解——牛顿迭代法 213
6.9  小结 216
第7章  复杂的数值计算算法
7.1  拉格朗日插值 217
7.1.1  拉格朗日插值算法 217
7.1.2  拉格朗日插值示例 218
7.2  数值积分 221
7.2.1  数值积分算法 221
7.2.2  数值积分示例 222
7.3  开平方 224
7.3.1  开平方算法 224
7.3.2  开平方示例 225
7.4  极值问题的求解算法 226
7.4.1  极值求解算法 226
7.4.2  极值求解示例 229
7.5  特殊函数的计算算法 232
7.5.1  伽玛函数 232
7.5.2  贝塔函数 236
7.5.3  正弦积分函数 240
7.5.4  余弦积分函数 244
7.5.5  指数积分函数 247
7.6  小结 252
第8章  经典数据结构问题
8.1  动态数组排序 253
8.1.1  的存储和排序 253
8.1.2  动态数组排序示例 254
8.2  约 瑟 夫 环 256
8.2.1  简单约瑟夫环算法 257
8.2.2  简单约瑟夫环求解 258
8.2.3  复杂约瑟夫环算法 260
8.2.4  复杂约瑟夫环求解 261
8.3  城市之间的最短总距离 264
8.3.1  最短总距离算法 264
8.3.2  最短总距离求解 267
8.4  最短路径 271
8.4.1  最短路径算法 271
8.4.2  最短路径求解 273
8.5  括号匹配 278
8.5.1  括号匹配算法 279
8.5.2  括号匹配求解 281
8.6  小结 284
第9章  数论问题
9.1  数论 285
9.1.1  数论概述 285
9.1.2  数论的分类 286
9.1.3  初等数论 287
9.1.4  基本概念 287
9.2  完全数 288
9.2.1  完全数概述 288
9.2.2  计算完全数算法 289
9.3  亲密数 291
9.3.1  亲密数概述 291
9.3.2  计算亲密数算法 291
9.4  水仙花数 294
9.4.1  水仙花数概述 294
9.4.2  计算水仙花数算法 295
9.5  自守数 297
9.5.1  自守数概述 297
9.5.2  计算自守数算法 298
9.6  最大公约数 302
9.6.1  计算最大公约数算法——
辗转相除法 302
9.6.2  计算最大公约数算法——Stein算法 303
9.6.3  计算最大公约数示例 304
9.7  最小公倍数 305
9.8  素数 307
9.8.1  素数概述 307
9.8.2  计算素数算法 308
9.9  回文素数 309
9.9.1  回文素数概述 310
9.9.2  计算回文素数算法 310
9.10  平方回文数 313
9.10.1  平方回文数概述 313
9.10.2  计算平方回文数算法 313
9.11  分解质因数 315
9.12  小结 318
第10章  算法经典趣题
10.1  百钱买百鸡 319
10.1.1  百钱买百鸡算法 319
10.1.2  百钱买百鸡求解 320
10.2  五家共井 321
10.2.1  五家共井算法 321
10.2.2  五家共井求解 323
10.3  鸡兔同笼 324
10.3.1  鸡兔同笼算法 325
10.3.2  鸡兔同笼求解 325
10.4  猴子吃桃 326
10.4.1  猴子吃桃算法 326
10.4.2  猴子吃桃求解 327
10.5  舍罕王赏麦 328
10.5.1  舍罕王赏麦问题 328
10.5.2  舍罕王赏麦求解 329
10.6  汉诺塔 330
10.6.1  汉诺塔算法 330
10.6.2  汉诺塔求解 332
10.7  窃贼问题 333
10.7.1  窃贼问题算法 333
10.7.2  窃贼问题求解 335
10.8  马踏棋盘 338
10.8.1  马踏棋盘算法 338
10.8.2  马踏棋盘求解 340
10.9  八皇后问题 342
10.9.1  八皇后问题算法 342
10.9.2  八皇后问题求解 343
10.10  寻找假银币 346
10.10.1  寻找假银币算法 346
10.10.2  寻找假银币求解 348
10.11  青蛙过河 350
10.11.1  青蛙过河算法 351
10.11.2  青蛙过河求解 352
10.12  三色旗 355
10.12.1  三色旗算法 355
10.12.2  三色旗求解 356
10.13  渔夫捕鱼 359
10.13.1  渔夫捕鱼算法 359
10.13.2  渔夫捕鱼求解 360
10.14  爱因斯坦的阶梯 360
10.14.1  爱因斯坦的阶梯算法 361
10.14.2  爱因斯坦的阶梯求解 361
10.15  兔子产仔 362
10.15.1  兔子产仔算法 363
10.15.2  兔子产仔求解 363
10.16  常胜将军 364
10.16.1  常胜将军算法 364
10.16.2  常胜将军求解 365
10.17  新郎和新娘 367
10.17.1  新郎和新娘算法 367
10.17.2  新郎和新娘求解 368
10.18  三色球 370
10.18.1  三色球算法 370
10.18.2  三色球求解 371
10.19  小结 372
第11章  游戏中的算法
11.1  洗扑克牌 373
11.1.1  洗扑克牌算法 373
11.1.2  洗扑克牌示例 374
11.2  取火柴游戏 377
11.2.1  取火柴游戏算法 377
11.2.2  取火柴游戏示例 378
11.3  10点半 380
11.3.1  10点半算法 380
11.3.2  10点半游戏示例 385
11.4  生命游戏 390
11.4.1  生命游戏的原理 391
11.4.2  生命游戏的算法 392
11.4.3  生命游戏示例 393
11.5  小结 399
 
第3篇  算法高级应用篇
 
第12章  密码学算法
12.1  密码学概述 402
12.1.1  密码学的发展 402
12.1.2  密码学的基本概念 403
12.1.3  柯克霍夫斯原则 404
12.1.4  经典密码学算法 404
12.2  换位加密解密 405
12.2.1  换位加密解密算法 405
12.2.2  换位加密解密算法示例 408
12.3  替换加密解密 411
12.3.1  替换加密解密算法 411
12.3.2  替换加密解密算法示例 412
12.4  位加密解密 414
12.4.1  位加密解密算法 414
12.4.2  位加密解密算法示例 416
12.5  一次一密加密解密 417
12.5.1  一次一密加密解密算法 418
12.5.2  一次一密加密解密算法示例 419
12.6  小结 421
第13章  压缩与解压缩算法
13.1  压缩与解压缩概述 422
13.1.1  压缩与解压缩分类 422
13.1.2  典型的压缩解压缩算法 423
13.2  压缩算法 423
13.3  解压缩算法 426
13.4  压缩/解压缩示例 429
13.5  小结 432
 
第4篇  常见面试题
 
第14章  算法常见面试题及解答
14.1  排序类算法面试题 434
14.1.1  排序算法效率 434
14.1.2  鸡尾酒排序算法 435
14.1.3  文件排序 437
14.1.4  城市名称 438
14.2  查找类算法面试题 439
14.2.1  递归求极值 439
14.2.2  寻找共同元素 441
14.2.3  查找最大子串 442
14.3  综合类算法面试题 444
14.3.1  求序列和 444
14.3.2  递归球累加和 445
14.3.3  猜苹果数 446
14.3.4  拟置字符串 448
14.3.5  递归法拟置字符串 449
14.3.6  位运算求负数 450
14.4  小结 450
第15章  数据结构常见面试题及解答
15.1  基本数据结构面试题 451
15.1.1  如何实现数据缓存区 451
15.1.2  出栈队列 451
15.1.3  入栈队列 452
15.1.4  二叉树叶节点个数 453
15.1.5  有向图和无向图 454
15.2  数据结构应用面试题 454
15.2.1  设计包含min函数的栈 455
15.2.2  设计计算指定节点层数算法 458
15.2.3  链表法筛选成绩 459
15.2.4  将二叉树转变成排序的
双向链表 461
15.2.5  单链表逆转 463
15.3  小结 465