第1篇 算法基础篇 1
第1章 算法概述 1
1.1什么是算法 1
1.2算法的发展历史 2
1.3算法的分类 3
1.4算法相关概念的区别 3
1.4.1算法与公式的关系 4
1.4.2算法与程序的关系 4
1.4.3算法与数据结构的关系 4
1.5算法的表示 4
1.5.1自然语言表示 5
1.5.2流程图表示 5
1.5.3 N-S图表示 6
1.5.4伪代码表示 7
1.6算法的性能评价 7
1.6.1时间复杂度 8
1.6.2空间复杂度 8
1.7算法实例 8
1.7.1查找数字 8
1.7.2创建项目 10
1.7.3编译执行 12
1.8算法的新进展 13
1.9小结 14
第2章 数据结构 15
2.1数据结构概述 15
2.1.1什么是数据结构 15
2.1.2数据结构中的基本概念 16
2.1.3数据结构的内容 16
2.1.4数据结构的分类 18
2.1.5数据结构的几种存储方式 18
2.1.6数据类型 19
2.1.7常用的数据结构 20
2.1.8选择合适的数据结构解决实际问题 21
2.2线性表 21
2.2.1什么是线性表 21
2.2.2线性表的基本运算 22
2.3顺序表结构 23
2.3.1准备数据 23
2.3.2初始化顺序表 24
2.3.3计算顺序表长度 24
2.3.4插入结点 24
2.3.5追加结点 25
2.3.6删除结点 25
2.3.7查找结点 25
2.3.8显示所有结点 26
2.3.9顺序表操作实例 26
2.4链表结构 30
2.4.1什么是链表结构 30
2.4.2准备数据 31
2.4.3追加结点 31
2.4.4插入头结点 32
2.4.5查找结点 33
2.4.6插入结点 34
2.4.7删除结点 35
2.4.8计算链表长度 35
2.4.9显示所有结点 36
2.4.10链表操作实例 36
2.5栈结构 41
2.5.1什么是栈结构 41
2.5.2准备数据 41
2.5.3初始化栈结构 42
2.5.4判断空栈 42
2.5.5 判断满栈 43
2.5.6清空栈 43
2.5.7释放空间 43
2.5.8入栈 43
2.5.9出栈 44
2.5.10读结点数据 44
2.5.11栈结构操作实例 45
2.6队列结构 47
2.6.1什么是队列结构 48
2.6.2准备数据 48
2.6.3初始化队列结构 49
2.6.4判断空队列 49
2.6.5判断满队列 49
2.6.6清空队列 50
2.6.7释放空间 50
2.6.8入队列 50
2.6.9出队列 51
2.6.10读结点数据 51
2.6.11计算队列长度 52
2.6.12队列结构操作实例 52
2.7树结构 55
2.7.1什么是树结构 56
2.7.2树的基本概念 56
2.7.3二叉树 57
2.7.4准备数据 60
2.7.5初始化二叉树 61
2.7.6添加结点 61
2.7.7查找结点 63
2.7.8获取左子树 63
2.7.9获取右子树 64
2.7.10判断空树 64
2.7.11计算二叉树深度 64
2.7.12清空二叉树 65
2.7.13显示结点数据 65
2.7.14遍历二叉树 65
2.7.15 树结构操作实例 67
2.8图结构 74
2.8.1什么是图结构 74
2.8.2图的基本概念 75
2.8.3准备数据 79
2.8.4创建图 81
2.8.5清空图 82
2.8.6显示图 82
2.8.7遍历图 83
2.8.8图结构操作实例 84
2.9小结 87
第3章 基本算法思想 88
3.1常用算法思想概述 88
3.2穷举算法思想 88
3.2.1穷举算法基本思想 89
3.2.2穷举算法实例 89
3.3递推算法思想 90
3.3.1递推算法基本思想 91
3.3.2递推算法实例 91
3.4递归算法思想 92
3.4.1递归算法基本思想 93
3.4.2递归算法实例 93
3.5分治算法思想 94
3.5.1分治算法基本思想 94
3.5.2分治算法实例 95
3.6概率算法思想 98
3.6.1概率算法基本思想 99
3.6.2概率算法实例 99
3.7小结 101
第2篇 算法应用篇 102
第4章 排序算法 102
4.1排序算法概述 102
4.2冒泡排序法 103
4.2.1冒泡排序算法 103
4.2.2冒泡排序算法实例 104
4.3选择排序法 106
4.3.1选择排序算法 106
4.3.2选择排序算法实例 107
4.4插入排序法 109
4.4.1插入排序算法 109
4.4.2插入排序算法实例 111
4.5 Shell排序法 112
4.5.1 Shell排序算法 112
4.5.2 Shell排序算法实例 113
4.6快速排序法 115
4.6.1快速排序算法 115
4.6.2快速排序算法实例 117
4.7堆排序法 119
4.7.1堆排序算法 119
4.7.2堆排序算法实例 123
4.8合并排序法 125
4.8.1合并排序算法 126
4.8.2合并排序算法实例 128
4.9排序算法的效率 131
4.10排序算法的其他应用 132
4.10.1反序排序 132
4.10.2字符串数组的排序 134
4.10.3字符串的排序 137
4.11小结 139
第5章 查找算法 140
5.1查找算法概述 140
5.2顺序查找 141
5.2.1顺序查找算法 141
5.2.2顺序查找操作实例 141
5.3折半查找 143
5.3.1折半查找算法 143
5.3.2折半查找操作实例 145
5.4数据结构中的查找算法 147
5.4.1顺序表结构中的查找算法 148
5.4.2链表结构中的查找算法 151
5.4.3树结构中的查找算法 154
5.4.4图结构中的查找算法 155
5.5小结 156
第6章 基本数学问题 157
6.1判断闰年 157
6.2多项式计算 159
6.2.1一维多项式求值 159
6.2.2二维多项式求值 161
6.2.3多项式乘法 163
6.2.4多项式除法 164
6.3随机数生成算法 167
6.3.1 Java语言中的随机方法 167
6.3.2 [0, 1]之间均匀分布的随机数算法 169
6.3.3产生任意范围的随机数 170
6.3.4 [m, n]之间均匀分布的随机整数算法 171
6.3.5正态分布的随机数生成算法 173
6.4复数运算 174
6.4.1简单的复数运算 175
6.4.2复数的幂运算 177
6.4.3复指数运算 178
6.4.4复对数运算 180
6.4.5复正弦运算 181
6.4.6复余弦运算 182
6.5阶乘 183
6.5.1使用循环来计算阶乘 183
6.5.2使用递归来计算阶乘 184
6.6计算π的近似值 185
6.6.1割圆术 186
6.6.2蒙特卡罗算法 189
6.6.3级数公式 191
6.7矩阵运算 193
6.7.1矩阵加法 193
6.7.2矩阵减法 195
6.7.3矩阵乘法 196
6.8方程求解 198
6.8.1线性方程求解——高斯消元法 198
6.8.2非线性方程求解——二分法 203
6.8.3非线性方程求解——牛顿迭代法 205
6.9小结 208
第7章 数据结构问题 209
7.1动态数组排序 209
7.1.1动态数组的存储和排序 209
7.1.2动态数组排序实例 210
7.2约瑟夫环 212
7.2.1简单约瑟夫环算法 213
7.2.2简单约瑟夫环求解 214
7.2.3复杂约瑟夫环算法 216
7.2.4复杂约瑟夫环求解 217
7.3城市之间的最短总距离 220
7.3.1最短总距离算法 220
7.3.2最短总距离求解 222
7.4最短路径 227
7.4.1最短路径算法 227
7.4.2最短路径求解 229
7.5括号匹配 234
7.5.1括号匹配算法 235
7.5.2括号匹配求解 236
7.6小结 239
第8章 数论问题 240
8.1数论概述 240
8.1.1数论概述 240
8.1.2数论的分类 241
8.1.3初等数论 242
8.1.4本章用到的基本概念 242
8.2完全数 243
8.2.1什么是完全数 243
8.2.2计算完全数算法 244
8.3亲密数 246
8.3.1什么是亲密数 246
8.3.2计算亲密数算法 246
8.4水仙花数 249
8.4.1什么是水仙花数 249
8.4.2计算水仙花数算法 250
8.5自守数 252
8.5.1什么是自守数 252
8.5.2计算自守数算法 253
8.6最大公约数 257
8.6.1计算最大公约数算法——辗转相除法 257
8.6.2计算最大公约数算法——Stein算法 258
8.6.3计算最大公约数示例 259
8.7最小公倍数 260
8.8素数 262
8.8.1什么是素数 262
8.8.2计算素数算法 262
8.9回文素数 264
8.9.1什么是回文素数 264
8.9.2计算回文素数算法 264
8.10平方回文数 267
8.10.1什么是平方回文数 267
8.10.2计算平方回文数算法 267
8.11分解质因数 269
8.12小结 271
第9章 算法经典趣题 272
9.1百钱买百鸡 272
9.1.1百钱买百鸡算法 272
9.1.2百钱买百鸡求解 273
9.2五家共井 274
9.2.1五家共井算法 274
9.2.2五家共井求解 275
9.3鸡兔同笼 277
9.3.1鸡兔同笼算法 277
9.3.2鸡兔同笼求解 277
9.4猴子吃桃 278
9.4.1猴子吃桃算法 278
9.4.2猴子吃桃求解 279
9.5舍罕王赏麦 280
9.5.1舍罕王赏麦问题 280
9.5.2舍罕王赏麦求解 281
9.6汉诺塔 282
9.6.1汉诺塔算法 282
9.6.2汉诺塔求解 284
9.7窃贼问题 285
9.7.1窃贼问题算法 285
9.7.2窃贼问题求解 287
9.8马踏棋盘 290
9.8.1马踏棋盘算法 290
9.8.2马踏棋盘求解 291
9.9八皇后问题 294
9.9.1八皇后问题算法 294
9.9.2八皇后问题求解 295
9.10寻找假银币 297
9.10.1寻找假银币算法 297
9.10.2寻找假银币求解 299
9.11青蛙过河 301
9.11.1青蛙过河算法 302
9.11.2青蛙过河求解 303
9.12三色旗 306
9.12.1三色旗算法 306
9.12.2三色旗求解 308
9.13渔父捕鱼 310
9.13.1渔父捕鱼算法 310
9.13.2渔父捕鱼求解 310
9.14爱因斯坦的阶梯 311
9.14.1爱因斯坦的阶梯算法 312
9.14.2爱因斯坦的阶梯求解 312
9.15 兔子产仔 313
9.15.1兔子产仔算法 313
9.15.2兔子产仔求解 314
9.16常胜将军 315
9.16.1常胜将军算法 315
9.16.2常胜将军求解 316
9.17新郎和新娘 318
9.17.1新郎和新娘算法 318
9.17.2新郎和新娘求解 319
9.18三色球 320
9.18.1三色球算法 320
9.18.2三色球求解 321
9.19小结 322
第10章 游戏中的算法 323
10.1洗扑克牌算法 323
10.1.1洗扑克牌算法 323
10.1.2洗扑克牌实例 324
10.2取火柴游戏算法 327
10.2.1取火柴游戏算法 327
10.2.2取火柴游戏实例 328
10.3 10点半算法 330
10.3.1 10点半算法 330
10.3.2 10点半游戏实例 335
10.4生命游戏 342
10.4.1生命游戏的原理 342
10.4.2生命游戏的算法 343
10.4.3生命游戏实例 344
10.5小结 349
第11章 密码学概述 350
11.1密码学概述 350
11.1.1密码学的发展 350
11.1.2密码学的基本概念 351
11.1.3柯克霍夫斯原则 352
11.1.4经典密码学算法 352
11.2换位加密解密算法 353
11.2.1换位加密解密算法 353
11.2.2换位加密解密算法实例 356
11.3替换加密解密算法 359
11.3.1替换加密解密算法 359
11.3.2替换加密解密算法实例 360
11.4位加密解密算法 363
11.4.1位加密解密算法 363
11.4.2位加密解密算法实例 364
11.5一次一密加密解密算法 366
11.5.1一次一密加密解密算法 366
11.5.2一次一密加密解密算法实例 367
11.6小结 369
第12章 压缩与解压缩算法 370
12.1压缩与解压缩概述 370
12.1.1压缩与解压缩分类 370
12.1.2典型的压缩解压缩算法 370
12.2压缩算法 371
12.3解压缩算法 374
12.4压缩解压缩实例 376
12.5小结 384
第3篇 算法面试篇 385
第13章 算法面试题 385
13.1基础算法 385
13.1.1字符串匹配 385
13.1.2哥德巴赫猜想的近似证明 388
13.1.3将一个正整数分解质因数 389
13.1.4怎样实现金额转换 391
13.1.5数字排列 396
13.1.6数字拆解 398
13.1.7数字组合 400
13.2思维扩展算法 403
13.2.1蛇形打印 403
13.2.2 24点算法 405
13.2.3双色球随机摇号 409
13.2.4巧妙过桥 412
13.2.5猴子吃桃 415
13.2.6天平称物 416
13.2.7掷骰子游戏 418
13.3小结 421