第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章 数据结构
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章 基本算法思想
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篇 算法应用篇

第4章 排序算法
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章 查找算法
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章 基本数学问题
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】求4×5的二维多项式在给定处的值 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
【程序示例6-14】一个复数的复指数运算 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