第1章 C++面向对象程序设计要点 1
1．1 函数和函数参数 1
1．1．1 函数类型 1
1．1．2 函数名重载 1
1．1．3 函数参数 2
1．1．4 成员函数返回值 3
1．2 输入输出 4
1．2．1 键盘屏幕输入输出 4
1．2．2 文件输入输出 5
1．3 类 6
1．3．1 类的存取权限 8
1．3．2 构造函数和析构函数 8
1．3．3 操作符重载 9
1．3．4 友元 10
1．3．5 分辨符 10
1．3．6 内联函数 10
1．3．7 默认值 10
1．3．8 多态性和虚函数 11
1．3．9 纯虚函数和抽象类 12
1．3．10 派生类继承方式 13
1．3．11 结构体 13
1．3．12 对象 13
1．4 抽象类型和模板 13
1．4．1 抽象类型 14
1．4．2 模板 14
习题一 15
第2章 面向对象程序设计和算法性能分析 17
2．1 抽象数据类型 17
2．1．1 数据结构 17
2．1．2 数据类型 18
2．1．3 抽象数据类型 19
2．1．4 抽象数据类型的描述方法 19
2．1．5 抽象数据类型的特点 20
2．2 面向对象程序设计和类 20
2．3 对象 22
2．4 算法、算法设计目标和算法性能分析 22
2．4．1 算法 22
2．4．2 算法设计目标 22
2．4．3 算法的时间效率 23
2．4．4 算法的符号命名、书写格式和注释格式 26
习题二 27
第3章 顺序存储结构的表、堆栈和队列 30
3．1 顺序存储结构 30
3．2 表和顺序表 32
3．2．1 顺序表的类定义 32
3．2．2 顺序表的类实现 33
3．2．3 顺序表上插入、删除算法的效率分析 35
3．2．4 顺序表的应用 37
3．3 堆栈和顺序堆栈 38
3．3．1 顺序堆栈类定义和实现 39
3．3．2 顺序堆栈应用——表达式计算 43
3．4 队列和顺序队列 48
3．4．1 顺序循环队列 49
3．4．2 顺序循环队列类的定义和实现 50
3．4．3 顺序循环队列的应用 52
3．5 优先级队列和顺序优先级队列 54
3．5．1 顺序优先级队列类定义和类实现 54
3．5．2 顺序优先级队列应用 57
3．6 顺序存储结构的特点 59
习题三 60
第4章 链式存储结构的表、堆栈和队列 63
4．1 链式存储结构 63
4．2 单链表 65
4．2．1 结点类的定义和实现 67
4．2．2 单链表类的定义和实现 68
4．2．3 单链表类的应用 73
4．3 单循环链表 74
4．3．1 单循环链表类的定义和实现 74
4．3．2 单循环链表类的应用 76
4．4 双向循环链表 78
4．4．1 双向循环链表概念 78
4．4．2 双向循环链表类定义和实现 79
4．5 链式堆栈 83
4．5．1 链式堆栈类的定义和实现 83
4．5．2 链式堆栈类的应用 86
4．6 链式队列 87
4．7 链式存储结构的特点 92
4．8 应用问题的面向对象程序设计方法 94
习题四 98
第5章 数组和串 100
5．1 数组 100
5．1．1 C++的数组 100
5．1．2 安全数组类的定义和实现 101
5．2 间接地址 105
5．3 特殊矩阵的压缩存储 106
5．3．1 矩阵的定义和操作 107
5．3．2 对称矩阵的压缩存储 107
5．3．3 上三角矩阵压缩存储类 108
5．4 稀疏矩阵的压缩存储 114
5．4．1 稀疏矩阵的三元组表 114
5．4．2 稀疏矩阵的三元组顺序表存储类 115
5．4．3 稀疏矩阵的三元组链表 119
5．5 串 119
5．5．1 串的定义、存储结构和操作 119
5．5．2 C++的串 121
5．5．3 方便用户使用的串类的定义和实现 123
5．5．4 模式匹配的Brute—Force算法 129
5．5．5 模式匹配的KMP算法 131
习题五 135
第6章 递归 137
6．1 递归的概念 137
6．2 递归算法的设计 139
6．3 递归过程和递归工作栈 143
6．4 递归算法的效率分析 144
6．5．1 尾递归和单向递归的消除 146
6．5 转化递归算法为非递归算法 146
6．5．2 模拟系统的运行时栈消除递归 147
6．6 回溯法 150
习题六 154
第7章 树和二叉树 157
7．1 仿真指针 157
7．2 树 158
7．2．1 树的定义 158
7．2．2 树的表示方法 160
7．2．3 树的基本操作 161
7．2．4 树的存储结构 162
7．2．5 树类 164
7．3．1 二叉树的定义 172
7．3 二叉树 172
7．3．2 二叉树的性质 173
7．3．3 二叉树的操作 175
7．3．4 二叉树的存储结构 177
7．3．5 树和二叉树的转换 179
7．4 链式存储结构的二叉树设计 180
7．4．1 二叉树结点类 181
7．4．2 二叉树的遍历 182
7．4．3 二叉树遍历的应用 183
7．4．4 应用示例 187
7．4．5 二叉树类 190
7．5 二叉树遍历游标类 192
7．5．1 二叉树中序遍历游标类 194
7．5．2 二叉树前序遍历游标类 198
7．5．3 二叉树层序遍历游标类 199
7．6 线索二叉树 200
7．6．1 线索二叉树的存储结构 201
7．6．2 线索二叉树类 202
7．6．3 中序线索二叉树类 204
7．7 堆 208
7．7．1 堆的定义 208
7．7．2 最小堆类 209
7．7．3 最小堆类的测试 215
7．8 哈夫曼树 216
7．8．1 路径长度和哈夫曼树 217
7．8．2 哈夫曼编码 218
7．8．4 哈夫曼编码问题算法设计 219
7．8．3 哈夫曼编码问题数据结构设计 219
习题七 223
第8章 图 226
8．1 图的基本概念和基本操作 226
8．1．1 图的基本概念 226
8．1．2 图的基本操作 229
8．2 图的邻接矩阵存储结构 229
8．2．1 邻接矩阵 229
8．2．2 邻接矩阵表示的图类 231
8．2．3 邻接矩阵图类的深度优先搜索遍历 235
8．2．4 邻接矩阵图类的广度优先搜索遍历 237
8．2．5 非连通图和连通分量 238
8．2．6 邻接矩阵图类的测试 239
8．3．1 图的邻接表存储结构 241
8．3 图的邻接表存储结构 241
8．3．2 邻接表存储结构的图类 242
8．3．3 邻接表存储结构图类的测试 249
8．4 图的其他存储结构 249
8．4．1 逆邻接表 249
8．4．2 十字链表 249
8．4．3 邻接多重表 250
8．5 最小生成树 251
8．5．1 最小生成树的基本概念 251
8．5．2 普里姆算法 252
8．5．3 克鲁斯卡尔算法 256
8．6．2 从一个顶点到其余各顶点的最短路径 258
8．6．1 最短路径的基本概念 258
8．6 最短路径 258
8．6．3 所有顶点之间的最短路径 262
习题八 266
第9章 排序 269
9．1 排序的基本概念 269
9．2 插入排序 271
9．2．1 直接插入排序 271
9．2．2 链表插入排序 274
9．2．3 希尔排序 276
9．3 选择排序 278
9．3．1 直接选择排序 278
9．3．2 堆排序 279
9．4．1 冒泡排序 280
9．4 交换排序 280
9．4．2 快速排序 282
9．5 归并排序 284
9．6 基数排序 287
习题九 289
第10章 查找 292
10．1 查找的基本概念 292
10．2 顺序表查找 294
10．2．1 无序顺序表顺序查找 294
10．2．2 有序顺序表查找 296
10．3 索引表查找 297
10．3．1 索引表结构 297
10．3．3 倒排索引表 300
10．3．2 索引结构查找的效率分析 300
10．4 树表查找 301
10．4．1 二叉排序树 301
10．4．2 二叉排序树类 301
10．4．3 二叉排序树的性能分析 307
10．4．4 平衡二叉树 308
10．4．5 B_树 311
10．5 哈希表查找 315
10．5．1 哈希表的基本概念 315
10．5．2 哈希函数构造方法 317
10．5．3 哈希冲突解决方法 318
1O．5．4 哈希表类 320
习题十 324
参考文献 326