第1部分 算法分析与程序设计基础 3
第1章 算法的基本概念 3
1.1算法的基本概念 3
1.1.1算法的特征 3
1.1.2算法的4个标准 4
1.1.3算法的描述形式 5
1.2算法复杂性分析框架 6
1.2.1增长次数 6
1.2.2渐进符号 6
1.2.3时间复杂度 7
1.2.4空间复杂度 9
本章小结 10
课后习题 10
第2章C++算法程序设计基础 12
2.1 C++语言概述 12
2.1.1 C++语言的优势 12
2.1.2 C++语言的内容 13
2.1.3编程工具 13
2.2 C++程序结构初步 17
2.2.1预处理指示符初步 17
2.2.2注释 17
2.2.3基本输入／输出 17
2.3使用C++语言编写简单代码 17
2.3.1面向过程的C语言 18
2.3.2面向过程的C++语言 18
2.3.3面向对象的C++语言 19
2.4 C++面向对象基础 23
2.4.1数据成员 24
2.4.2成员函数 24
2.4.3类对象成员的访问 26
2.4.4类的访问限制 27
2.4.5动态内存分配 28
2.4.6 C++程序内存分配 30
2.5构造函数和析构函数 30
2.5.1构造函数的概念 30
2.5.2析构函数的概念 31
2.5.3带参数的构造函数 32
2.5.4重载构造函数 33
2.6类中的this指针 34
2.7类中的const修饰符 35
2.7.1常对象 35
2.7.2常成员函数 36
2.7.3常数据成员 37
2.8模板的基本概念 37
2.8.1使用模板的必要性 37
2.8.2模板的分类 38
2.9函数模板 38
2.9.1函数模板的定义 38
2.9.2使用函数模板 38
2.9.3函数模板的重载 40
2.10类模板 41
2.10.1类模板的定义 41
2.10.2使用类模板 41
2.11继承的基本概念 43
2.11.1继承的必要性 43
2.11.2继承的实现方式 45
2.11.3继承中的静态数据成员 47
2.12基类和派生类的关系 48
2.12.1基类指针 48
2.12.2继承下的构造函数和析构函数 49
2.12.3重写基类成员 50
2.12.4调用基类成员函数 51
2.13详解protected关键字 53
2.14保护继承与私有继承 54
2.14.1公有继承 54
2.14.2私有继承 55
2.14.3保护继承 56
本章小结 56
课后习题 56
第2部分 算法设计数据结构基础 61
第3章 线性数据结构基础 61
3.1抽象数据类型 61
3.2线性表基础 61
3.2.1线性表定义及特点 62
3.2.2顺序表 62
3.2.3链表 72
3.2.4数组与链表性能比较 79
3.3栈与队列基础 80
3.3.1栈 80
3.3.2队列 83
本章小结 91
课后习题 91
第4章 非线性数据结构基础 93
4.1树与二叉树 93
4.1.1树的基本概念 93
4.1.2二叉树 94
4.2树与二叉树的存储结构 95
4.2.1二叉树的存储结构 95
4.2.2树的存储结构 96
4.2.3二叉树的遍历 97
4.3图 104
4.3.1图的基本概念 104
4.3.2图的存储结构 105
本章小结 113
课后习题 113
第5章 排序与搜索算法基础 114
5.1排序算法的基本概念 114
5.1.1排序的分类 114
5.1.2排序算法的评价标准 114
5.2简单排序算法 114
5.2.1插入排序 115
5.2.2选择排序 117
5.2.3冒泡排序 119
5.3快速排序 121
5.4堆排序 124
5.5归并排序 127
5.6希尔排序 130
5.7线性表查找 133
5.7.1顺序查找 134
5.7.2二分查找 134
5.8树与图的搜索 135
5.8.1二叉排序树搜索 135
5.8.2 B-树 136
5.8.3广度优先搜索 138
5.8.4图的深度优先搜索 140
本章小结 141
课后习题 141
第3部分 典型算法分析与问题求解 147
第6章 递归与分治法算法设计 147
6.1递归法 147
6.1.1递归算法的特性 148
6.1.2递归的执行过程 148
6.2递归法应用举例 148
6.2.1汉诺塔问题求解 148
6.2.2斐波那契数列问题求解 150
6.2.3八皇后问题 151
6.3分治法 154
6.3.1问题提出 154
6.3.2分治法概述 156
6.4分治法应用举例 157
本章小结 158
课后习题 159
第7章 贪心算法设计 161
7.1贪心法 161
7.1.1问题提出 161
7.1.2贪心法的基本思路 162
7.2贪心法应用举例 163
7.2.1背包问题 163
7.2.2哈夫曼编码 167
7.2.3单源最短路径 173
7.2.4最小生成树 177
本章小结 184
课后习题 185
第8章 动态规划算法设计 187
8.1动态规划法 187
8.1.1动态规划法的基本概念 187
8.1.2多阶段决策 188
8.1.3动态规划法适用条件 189
8.1.4动态规划法解决问题的步骤 189
8.2动态规划法应用举例 190
8.2.1多源最短路径 190
8.2.2最大公共子序列问题 194
8.2.3导弹拦截问题 197
本章小结 200
课后习题 200
第9章 回溯法算法设计 202
9.1回溯法 202
9.1.1回溯法的基本概念 202
9.1.2回溯法的基本思想 203
9.1.3回溯法求解问题的步骤 204
9.2回溯法应用举例 205
9.2.1小老鼠走迷宫问题 205
9.2.2子集合问题 209
9.2.3全排列问题 210
9.2.4八皇后问题 211
9.2.5 0-1背包问题 213
本章小结 216
课后习题 216
第10章 分支限界算法设计 218
10.1分支限界 218
10.1.1分支限界法的基本思想 218
10.1.2求解问题的适用条件和步骤 219
10.1.3分支限界的优缺点 219
10.2分支限界应用举例 219
10.2.1 0-1背包问题 219
10.2.2旅行售货员问题 226
本章小结 230
课后习题 230
附录A部分习题参考答案 232
参考文献 235