C/C++常用算法手册（第4版） PDF下载

第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 章　数据结构
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 章　基本算法思想
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.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 章　查找算法
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