出版说明 1
前言 1
第1章 概论 1
1.1 数据类型和抽象数据类型 1
目录 1
1.2 用类实现抽象数据类型 5
1.3 类关系和多态性 10
1.3.1 组合 10
1.3.2 继承 10
＊1.3.3 多态性 11
1.4.1 类模板 13
1.4 模板 13
1.4.2 函数模板 14
1.5 C＋＋标准模板库（STL）和名字空间 15
1.5.1 标准模板库 15
＊1.5.2 名字空间 15
＊1.6 异常处理 17
1.7 算法及算法分析 20
1.7.1 算法的概念 20
＊1.7.2 算法分析 21
1.8 小结 28
1.9 习题 29
1.10 上机题 31
第2章 向量、矩阵和字符串 32
2.1 向量 32
2.1.1 数组 32
2.1.2 类Vector 34
2.1.3 STL的向量容器vector 39
2.2 矩阵 50
2.2.1 矩阵类Matrix 50
2.2.2 特殊矩阵 55
2.3.1 串的概念 62
2.3 字符串 62
2.3.2 串类string 64
＊2.4 模式匹配 66
2.5 小结 71
2.6 习题 72
2.7 上机题 74
第3章 表 76
3.1 抽象数据类型表 76
3.2 表的实现 77
3.2.1 表的顺序存储 77
3.2.2 表的链接存储 78
3 3.2 双向链表 82
3.3 其他表结构 82
3.3.1 循环链表 82
3.4 表类和表迭代器类 84
3.4.1 表类和表迭代器类的定义 84
3.4.2 稀疏多项式的实现 90
3.5 STL表容器list 96
＊3.6 表的应用举例 97
3.6.1 大整数加法 97
3.6.2 稀疏矩阵的链表表示 104
3.8 习题 106
3.7 小结 106
3.9 上机题 108
第4章 栈和队列 109
4.1 抽象数据类型栈 109
4.1.1 用向量（vector）实现栈 109
4.1.2 用表（list）实现栈 113
4.2 抽象数据类型队列 118
4.2.1 用数组实现队列 119
4.2.2 用表（list）实现队列 122
4.3 双端队列（deque） 126
4.4.1 stack容器 129
4.4 STL stack容器和queue容器 129
4.4.2 queue容器 130
4.5 应用举例 130
4.5.1 算术表达式求值 130
＊4.5.2 售票窗口的模拟 139
4.6 优先队列 147
4.7 小结 149
4.8 习题 149
4.9 上机题 150
5.1 递归的概念 152
第5章 递归 152
5.2 用递归求解问题 156
＊5.3 递归过程的实现 166
5.4 广义表 175
5.4.1 广义表的概念 175
5.4.2 广义表的存储表示 177
＊5.4.3 实现广义表的算法 179
5.4.4 二元多项式的表示 185
5.5 小结 186
5.6 习题 187
5.7 上机题 189
6.1 树的概念 190
第6章 树和二叉树 190
6.2 二叉树 192
6.2.1 定义和性质 192
6.2.2 存储表示 194
6.3 二叉树的遍历 196
6.3.1 先序、中序、后序和层次遍历 196
6.3.2 二叉树计数 201
6.3.3 基于遍历的其他操作 202
6.3.4 二叉树类 206
＊6.3.5 用迭代器实现二叉树的遍历 209
6.4.1 线索二叉树的概念 216
6.4 线索二叉树 216
6.4.2 线索二叉树的遍历 220
6.5 树和森林 222
6.5.1 树和森林的二叉树表示 222
＊6.5.2 树和森林的遍历 224
＊6.5.3 树和森林的数组（或向量）表示 225
6.6 堆和优先队列 228
6.6.1 堆 228
6.6.2 优先队列的实现 236
6.7 数据压缩和哈夫曼编码 237
＊6.8 抽象数据类型并查集（Union-Find Sets）的实现 243
6.9 小结 250
6.10 习题 251
6.11 上机题 253
第7章 搜索树 254
7.1 二叉搜索树 254
7.1.1 二叉搜索树的操作 254
7.1.2 二叉搜索树类BinSearchTree 255
7.1.3 类BinSearchTree的迭代器类Iterator 259
7.1.4 二叉搜索树操作的时间分析 263
7.2 平衡的二叉搜索树（AVL树） 265
7.2.1 AVL树的插入 266
7.2.2 AVL树的删除 274
7.2.3 AVL树的高度 276
＊7.3 红黑树（RED-BLACKTREES） 278
7.3.1 红黑树的概念 278
7.3.2 红黑树的插入 280
7.3.3 红黑树的删除 287
7.4 标准模板库的关联容器 289
7.4.1 关联容器 289
7.4.2 集合（set）的运算 291
7.4.3 映射（map）的下标操作 292
7.6 习题 295
7.5 小结 295
7.7 上机题 297
第8章 散列 298
8.1 散列表 298
8.2 散列函数 299
8.2.1 函数对象 299
8.2.2 构造散列函数的方法 301
8.3 处理冲突的方法 303
8.3.1 开放定址法 303
8.3.2 拉链法 305
8.4.1 散列表的元素 306
＊8.4 散列表类及迭代器类 306
8.4.2 散列表类HashTable 307
8.4.3 迭代器类 309
8.5 小结 313
8.6 习题 313
8.7 上机题 315
第9章 排序 317
9.1 插入排序 317
9.1.1 直接插入排序 317
9.1.2 二分法插入排序 319
9.2 快速排序 320
9.3 堆排序 325
9.4 归并排序 327
＊9.5 基于比较的排序方法所需时间的最小上界 333
9.6 小结 334
9.7 习题 334
9.8 上机题 335
第10章 图 337
10.1 图的概念 337
10.2 图类 339
10.2.2 图的存储表示及图类的实现 340
10.2.1 图的操作 340
10.3 图的遍历 349
10.3.1 深度优先搜索 349
10.3.2 广度优先搜索 351
10.4 最小代价生成树 354
10.5 最短路径 359
10.6 拓扑排序 365
10.7 小结 369
10.8 习题 369
10.9 上机题 370
参考文献 371