第1章 算法概述 1
1.1 什么是算法 1
1.2 算法的发展历史和分类 2
1.3 算法与相关概念的区别 3
1.3.1 算法和公式的关系 4
1.3.2 算法与程序的关系 4
1.3.3 算法与数据结构的关系 4
1.4 算法是计算机科学的灵魂 5
1.5 算法的表示 6
1.5.1 自然语言表示 6
1.5.2 流程图表示 6
1.5.3 N-S图表示 8
1.5.4 伪代码表示 8
1.6 伪代码与算法程序的对应 9
1.6.1 基本对应规则 9
1.6.2 分支结构 10
1.6.3 循环结构 10
1.6.4 数组及函数 11
1.7 算法的性能评价 11
1.8 算法实例 12
1.8.1 查找数字 12
实例1-1：在拥有20个整数数据的数组中查找某个数据 13
1.8.2 创建项目 14
1.8.3 编译执行 15
1.9 算法的新进展 16
1.10 小结：算法是程序设计的灵魂和基础 17
第2章 数据结构 18
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 什么是线性表 24
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-1：对某班级学生学号、姓名和年龄数据进行顺序表操作 30
2.4 链表结构 33
2.4.1 什么是链表结构 33
2.4.2 准备数据 34
2.4.3 追加结点 34
2.4.4 插入头结点 35
2.4.5 查找结点 36
2.4.6 插入结点 37
2.4.7 删除结点 38
2.4.8 计算链表长度 38
2.4.9 显示所有结点 39
2.4.10 链表操作示例 39
实例2-2：使用链表操作实现用户管理 39
2.5 栈结构 43
2.5.1 什么是栈结构 43
2.5.2 准备数据 44
2.5.3 初始化栈结构 44
2.5.4 判断空栈 45
2.5.5 判断满栈 45
2.5.6 清空栈 45
2.5.7 释放空间 46
2.5.8 入栈 46
2.5.9 出栈 46
2.5.10 读结点数据 47
2.5.11 栈结构操作示例 47
实例2-3：使用栈结构实现学生数据操作 47
2.6 队列结构 50
2.6.1 什么是队列结构 50
2.6.2 准备数据 50
2.6.3 初始化队列结构 51
2.6.4 判断空队列 51
2.6.5 判断满队列 52
2.6.6 清空队列 52
2.6.7 释放空间 52
2.6.8 入队列 52
2.6.9 出队列 53
2.6.10 读结点数据 53
2.6.11 计算队列长度 54
2.6.12 队列结构操作示例 54
实例2-4：使用队列结构实现学生数据操作 54
2.7 树结构 57
2.7.1 什么是树结构 57
2.7.2 树的基本概念 58
2.7.3 二叉树 58
2.7.4 准备数据 62
2.7.5 初始化二叉树 62
2.7.6 添加结点 63
2.7.7 查找结点 64
2.7.8 获取左子树 65
2.7.9 获取右子树 65
2.7.10 判断空树 65
2.7.11 计算二叉树深度 66
2.7.12 清空二叉树 66
2.7.13 显示结点数据 66
2.7.14 遍历二叉树 67
2.7.15 树结构操作示例 69
实例2-5：经典二叉树的遍历（4种遍历方式） 69
2.8 图结构 71
2.8.1 什么是图结构 71
2.8.2 图的基本概念 72
2.8.3 准备数据 76
2.8.4 创建图 78
2.8.5 清空图 78
2.8.6 显示图 79
2.8.7 遍历图 79
2.8.8 图结构操作示例 80
实例2-6：使用深度优先遍历算法遍历图操作程序 81
2.9 小结：数据结构＋算法＝程序 83
第3章 基本算法思想 84
3.1 常用算法思想概述 84
3.2 穷举算法思想 84
3.2.1 穷举算法基本思想 85
3.2.2 穷举算法示例 85
实例3-1：鸡兔同笼问题 85
3.3 递推算法思想 87
3.3.1 递推算法基本思想 87
3.3.2 递推算法示例 87
实例3-2：兔子产仔问题 87
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枚假银币 91
3.6 概率算法思想 95
3.6.1 概率算法基本思想 95
3.6.2 概率算法示例 95
实例3-5：利用蒙特卡罗算法计算圆周率π 95
3.7 贪心算法思想 97
3.7.1 贪心算法基本思想 97
3.7.2 贪心算法示例 98
实例3-6：利用贪心算法思想兑换硬币 98
3.8 小结：思路决定出路 99
第4章 排序算法 100
4.1 排序算法概述 100
4.2 冒泡排序法 101
4.2.1 冒泡排序算法 101
4.2.2 冒泡排序算法示例 102
实例4-1：对包含10个数字的整型数组进行排序 102
4.3 选择排序法 104
4.3.1 选择排序算法 104
4.3.2 选择排序算法示例 105
实例4-2：对包含10个数字的整型数组进行排序 105
4.4 插入排序法 106
4.4.1 插入排序算法 107
4.4.2 插入排序算法示例 108
实例4-3：对包含10个数字的整型数组进行排序 108
4.5 Shell排序法 109
4.5.1 Shell排序算法 109
4.5.2 Shell排序算法示例 111
实例4-4：对包含10个数字的整型数组进行排序 111
4.6 快速排序法 112
4.6.1 快速排序算法 112
4.6.2 快速排序算法示例 114
实例4-5：对包含18个数字的整型数组进行排序 114
4.7 堆排序法 116
4.7.1 堆排序算法 116
4.7.2 堆排序算法示例 120
实例4-6：对包含10个数字的整型数组进行排序 120
4.8 合并排序法 122
4.8.1 合并排序算法 122
4.8.2 合并排序算法示例 125
实例4-7：对包含15个数字的整型数组进行排序 125
4.9 排序算法的效率 128
4.10 排序算法的其他应用 128
4.10.1 反序排序 129
4.10.2 反序插入排序算法示例 129
实例4-8：对包含10个数字的整型数组进行排序 129
4.10.3 字符串的排序 131
4.10.4 字符串排序示例 132
实例4-9：用快速排序算法对包含16个字母的字符串进行排序 132
4.10.5 字符串数组的排序 133
4.10.6 字符串数组排序示例 134
实例4-10：用快速排序算法对包含5个单词的字符串数组进行排序 134
4.11 小结：排序是最基本的算法 136
第5章 查找算法 137
5.1 查找算法概述 137
5.2 顺序查找 138
5.2.1 顺序查找算法 138
5.2.2 顺序查找操作示例 138
实例5-1：在包含15个数字的数组中查找第7个数字 138
5.3 折半查找 140
5.3.1 折半查找算法 140
5.3.2 折半查找操作示例 142
实例5-2：在包含15个数字的数组中查找第11个数字 142
5.4 小结：查找是最基本的应用 144
第6章 基本数学问题 145
6.1 判断闰年 145
实例6-1：判断2000年到3000年之间所有的闰年 145
6.2 多项式计算 146
6.2.1 一维多项式求值 147
6.2.2 一维多项式求值示例 147
实例6-2：计算多项式在x取不同值时的值 147
6.2.3 二维多项式求值 148
6.2.4 二维多项式求值示例 149
实例6-3：求4×5的二维多项式在给定处的值 149
6.2.5 多项式乘法 150
6.2.6 多项式乘法示例 151
实例6-4：计算两个多项式的乘积多项式 151
6.2.7 多项式除法 152
6.2.8 多项式除法示例 153
实例6-5：计算A（x）/B（x）的商多项式和余多项式 153
6.3 随机数生成 154
6.3.1 C语言中的随机函数 155
实例6-6：在0～32767产生一组随机数 155
实例6-7：输出0～100的随机整数 155
6.3.2 [0，1]之间均匀分布的随机数算法 156
实例6-8：输出10个0～1的随机数 157
6.3.3 产生任意范围的随机数 158
实例6-9：输出10个10.0～20.0的浮点随机数 158
6.3.4 [m，n]之间均匀分布的随机整数算法 159
实例6-10：输出10个100～200的随机整数 159
6.3.5 正态分布的随机数生成算法 160
实例6-11：输出10个正态分布的随机数 160
6.4 复数运算 162
6.4.1 简单的复数运算 162
6.4.2 简单复数运算示例 163
实例6-12：计算两个复数的加减乘除 163
6.4.3 复数的幂运算 164
6.4.4 复数的幂运算示例 165
实例6-13：一个复数的n（n＝5）次幂运算 165
6.4.5 复指数运算 166
6.4.6 复指数运算示例 166
实例6-14：一个复数的复指数运算 166
6.4.7 复对数运算 167
6.4.8 复对数运算示例 167
实例6-15：一个复数的复对数计算 167
6.4.9 复正弦运算 168
6.4.10 复正弦运算示例 169
实例6-16：一个复数的复正弦运算 169
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 方程求解 182
6.8.1 线性方程求解——高斯消元法 182
6.8.2 高斯消元法示例 185
实例6-24：3个变量、3个方程的方程组的高斯消元法求解 186
6.8.3 非线性方程求解——二分法 187
6.8.4 二分法算法示例 188
实例6-25：使用二分法来求方程的解 188
6.8.5 非线性方程求解——牛顿迭代法 189
6.8.6 牛顿迭代法示例 190
实例6-26：使用牛顿迭代法求方程的解 191
6.9 开平方 192
6.9.1 开平方算法 192
6.9.2 开平方示例 193
实例6-27：求解两个数字开方的数值计算结果 193
6.10 小结：算法归根结底都是数学问题 194
第7章 游戏中的经典计算 195
7.1 扑克游戏问题——10点半 195
7.1.1 算法解析 195
7.1.2 求解示例 199
7.2 生命游戏 201
7.2.1 生命游戏的原理 201
7.2.2 算法解析 203
7.2.3 求解示例 204
7.3 小结：好算法好游戏 208
第8章 经典数据结构问题 209
8.1 动态数组排序 209
8.1.1 动态数组的存储和排序算法 209
8.1.2 动态数组排序示例 210
实例8-1：对以0结束的动态字符数组进行排序 210
8.2 约瑟夫环 212
8.2.1 约瑟夫环算法解析 212
8.2.2 约瑟夫环应用 213
实例8-2：总数为41人，报数3者自杀，求解约瑟夫环的解 213
8.2.3 约瑟夫环推广应用算法 215
8.2.4 约瑟夫环推广应用 216
实例8-3：n个人环坐（顺时针编号1、2、3…、n），每人随机取一张写有数字的纸条，报数m者出列，同时其手中数字为新的出列数字，求解约瑟夫环 216
8.3 城市之间的最短总距离和最短距离 218
8.3.1 最短总距离算法 219
8.3.2 最短路径算法 221
8.3.3 最短总距离求解示例 223
实例8-4：计算某地区5个城市间的最短总距离 223
8.4 解决括号匹配问题 227
8.4.1 括号匹配算法 227
8.4.2 括号匹配求解示例 229
实例8-5：对以0结束的一组括号进行匹配 229
8.5 小结：合理的数据结构＝高效率的算法 232
第9章 数论问题 233
9.1 数论概述及分类 233
9.1.1 数论概述 233
9.1.2 数论的分类 234
9.1.3 基本概念 235
9.2 完全数 236
9.2.1 完全数概述 236
9.2.2 生成完全数算法 237
9.2.3 查找完全数算法示例 238
实例9-1：查找10000以内的所有完全数 238
9.3 亲密数（对） 239
9.3.1 亲密数（对）概述 239
9.3.2 查找亲密数对算法 239
9.3.3 查找亲密数对算法示例 240
实例9-2：查找5000以内的所有亲密数对 240
9.4 水仙花数 242
9.4.1 水仙花数概述 242
9.4.2 查找水仙花数算法 243
9.4.3 查找水仙花数算法示例 243
实例9-3：查找3位数和4位数的水仙花数 243
9.5 自守数 245
9.5.1 自守数概述 245
9.5.2 查找自守数算法 246
9.5.3 查找自守数算法示例 247
实例9-4：请用两种算法查找1000以内和200000以内的自守数 247
9.6 最大公约数和最小公倍数 249
9.6.1 计算最大公约数算法——辗转相除法 249
9.6.2 计算最大公约数算法——Stein算法 250
9.6.3 计算最小公倍数算法——lcm算法 251
9.6.4 计算最大公约数示例 251
实例9-5：用辗转相除法计算12和34的最大公约数 252
9.6.5 计算最小公倍数示例 252
实例9-6：求12和34的最小公倍数 252
9.7 素数 254
9.7.1 素数概述 254
9.7.2 查找判断素数算法 254
9.7.3 查找判断素数算法示例 255
实例9-7：查找判断1～1000的所有素数 255
9.8 回文素数 256
9.8.1 回文素数概述 256
9.8.2 查找判断回文素数算法 256
9.8.3 查找判断回文素数算法示例 257
实例9-8：查找判断0～50000的回文素数 257
9.9 平方回文数 259
9.9.1 平方回文数概述 259
9.9.2 查找判断平方回文数算法 259
9.9.3 查找判断平方回文数算法示例 260
实例9-9：判断查找1～1000哪些数的平方可以得到回文数 260
9.10 分解质因数 261
9.10.1 质因数分解算法 261
9.10.2 质因数分解算法示例 262
实例9-10：对合数1155分解质因数 262
9.11 小结：数论是算法最好的练兵场 263
第10章 经典趣题计算机算法求解 264
10.1 不定方程问题：百钱买百鸡 264
10.2 不定方程问题：五家共井 266
10.3 递归算法问题：猴子吃桃 269
10.4 级数求和问题：舍罕王赏麦 270
10.5 递归算法问题：汉诺塔 272
10.6 关于最优化的问题：窃贼问题 275
10.7 递归算法问题：马踏棋盘 280
10.8 回溯算法问题：八皇后问题 283
10.9 递归算法问题：青蛙过河 286
10.10 最优化算法：三色旗 290
10.11 递推算法问题：渔夫捕鱼 293
10.12 数论问题：爱因斯坦的阶梯 295
10.13 让算法决定输赢：常胜将军 297
10.14 排列组合问题：三色球 299
10.15 小结：算法融入有趣实践 301
第11章 数学能力测试 302
11.1 最后有哪些灯是亮着的 302
11.2 用一笔画出经过9个点的4条直线 303
11.3 在9个点上画10条线 304
11.4 时、分和秒针重合问题 304
11.5 可以喝多少瓶汽水 307
11.6 怎样拿到第100号球 308
11.7 烧绳计时 309
11.8 分裂的小虫 310
11.9 看起来像相遇问题 310
11.10 数学家的约会妙招 311
第12章 智商逻辑推理类面试题 313
12.1 脑筋急转弯 313
12.1.1 中国有多少辆汽车 313
12.1.2 下水道的盖子为什么是圆形的 314
12.1.3 分蛋糕 315
12.1.4 你怎样改造和重新设计一个ATM银行自动取款机 315
12.2 逻辑推理 316
12.2.1 哪个开关控制哪盏灯 316
12.2.2 谁先猜出自己帽子的颜色 317
12.2.3 海盗分金 318
12.2.4 罪犯认罪 319
12.2.5 找出质量不相同的那个球 320
12.2.6 有多少人及格 320
12.2.7 他说的是真话吗 321
12.3 计算推理 322
12.3.1 倒水问题 322
12.3.2 骗子购物 323
12.3.3 求最大的连续组合值（华为校园招聘笔试题） 324
12.3.4 巧妙过桥 325
12.3.5 字符移动（金山笔试题） 327
第13章 数据结构常见面试题及解答 329
13.1 基本数据结构面试题 329
13.1.1 如何实现数据缓存区 329
13.1.2 出栈队列 329
13.1.3 入栈队列 330
13.1.4 二叉树叶结点个数 331
13.1.5 有向图和无向图 332
13.2 数据结构应用面试题 332
13.2.1 设计包含min函数的栈 332
实例13-1：在函数min、push及pop时间复杂度都是O（1）的情况下，设计包含min函数的栈 333
13.2.2 设计计算指定结点层数算法 335
实例13-2：在给定的二叉树中，计算字符C的层数 336
13.2.3 链表法筛选成绩 337
实例13-3：某班级8位学生的成绩已给出，使用链表结构及指针操作来输出及格的成绩分数 337
13.2.4 将二叉树转变成排序的双向链表 339
实例13-4：将给出的二叉树转换成一个排序的双向链表（不能创建新的结点，只调整数指针的方向） 339
13.2.5 单链表逆转 340
实例13-5：编写算法将一个单链表实现逆转 341
第14章 算法常见面试题及解答 343
14.1 排序类算法面试题 343
14.1.1 排序算法效率 343
14.1.2 鸡尾酒排序算法 344
实例14-1：用鸡尾酒排序算法对一组整数进行排序 344
14.1.3 文件排序 345
14.1.4 城市名称 347
实例14-2：对任意输入的5个城市的拼音按照字母顺序重新排列输出 347
14.2 查找类算法面试题 348
14.2.1 递归求极值 348
实例14-3：用递归法求10个整数中的最大值 348
14.2.2 寻找共同元素 349
实例14-4：查找并输出两个整型数组中同时出现的元素 350
14.2.3 查找最大子串 351
实例14-5：在一个由0和1组成的字符串中，查找0和1连续出现的最大次数 351
14.3 综合类算法面试题 352
14.3.1 求序列和 353
实例14-6：求给出数据序列的前100项之和 353
14.3.2 递归求累加和 353
实例14-7：用递归算法求1＋2＋3＋4＋……＋100之和 354
14.3.3 猜苹果数 354
实例14-8：用递归算法计算给定题目中5个人各自拥有的苹果数 355
14.3.4 逆置字符串 356
实例14-9：将一个输入的字符串在不额外开辟空间的情况下进行逆置 356
14.3.5 位运算求负数 357
实例14-10：计算正整数20对应的负数（只可使用位运算实现） 357
