C/C++常用算法手册（第3版）

第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.3N-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.5Shell排序法 108

4.5.1Shell排序算法 108

4.5.2Shell排序算法示例 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.1C语言中的*函数 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