第一章 预备知识 1
1．1 C++语言对C的基本扩充 1
1．2 对象和类 6
1．3 类的界面描述和实现 10
1．3．1 类的数据域 11
1．3．2 对象的行为——成员函数 12
1．3．3 运算符作为成员函数 13
1．3．4 用构造函数进行实例的初始化 15
1．3．5 普通运算符 18
1．3．6 普通函数 20
1．4 对象的输入和输出 20
1．5 类的合成、继承和多态性 24
1．5．1 合成 24
1．5．2 继承 27
1．5．3 多态性 28
1．6 面向对象的程序设计* 28
1．6．1 分析阶段 29
1．6．2 设计阶段 30
1．6．3 编码阶段 32
1．6．4 测试和维护 34
1．7 算法分析与设计* 34
小结 38
习题 39
第二章 字符串——数据封装技术 41
2．1 C++语言的字符和字符串 41
2．2 字符串数据抽象的描述和实现 43
2．2．1 字符串类的定义 44
2．2．2 构造函数的定义 46
2．2．3 析构函数 49
2．2．4 基本成员函数的实现 50
2．2．5 比较运算符 54
2．2．6 串连接 56
2．2．7 输入和输出 57
2．3 子串 59
2．4 模式匹配 64
2．4．1 简单字符串匹配 66
2．4．2 Knuth-Morris-Pratt模式匹配算法* 69
2．4．3 Boyer-Moore字符串匹配算法* 73
小结 77
习题 77
第三章 向量——程序重用技术 79
3．1 模板类 80
3．2 向量的实现 82
3．3 程序的重用、定界向量和位向量 85
3．3．1 继承方式的重用：定界向量 86
3．3．2 通过合成方式的重用——位向量 89
3．4 其他向量类型* 94
3．4．1 用枚举类型作为指标 94
3．4．2 矩阵 96
3．5 排序——模板函数 100
3．5．1 插入排序 101
3．5．2 起泡排序 102
3．5．3 选择排序 103
3．5．4 快速排序算法 104
小结 106
习题 107
4．1 遍历器（Iterator） 108
第四章 遍历器——继承和多态性 108
4．1．1 抽象的遍历器类 109
4．1．2 向量遍历器 110
4．2 有序向量和二分法检索 114
4．3 继承和多态——进一步的讨论 117
4．3．1 静态、动态类型和多态性 117
4．3．2 框架和虚函数 119
4．3．3 两类继承 120
4．3．4 对虚函数和普通函数的遮蔽* 121
4．4 多态性的形式和例子* 122
4．4．1 参数多态性——归约 122
4．4．2 切割问题 124
小结 125
习题 126
第五章 动态数据结构——链表 127
5．1 单链表的定义 127
5．1．1 表类 127
5．1．2 链类 129
5．2 单链表的实现 130
5．2．1 链类的实现 130
5．2．2 表类的实现 132
5．3 表遍历器 136
5．3．1 表遍历器类 136
5．4 表的应用：多项式处理* 142
5．4．1 项类 142
5．4．2 多项式类 144
5．5 有序链表 147
5．5．1 有序表类 147
5．5．2 有序表类的实现 148
5．5．3 有序表的应用——表插入排序 149
5．6 其他链表 150
5．6．1 自组织表 150
5．6．2 双端表 151
5．6．3 循环表 152
5．6．4 双链表 152
5．7 可利用空间表 153
小结 155
习题 157
第六章 栈和队列 158
6．1 抽象类栈和队列 158
6．2 栈的实现 159
6．2．1 栈的向量实现 160
6．2．2 栈的链表实现 162
6．3 栈的应用——表达式计算 164
6．3．1 后缀表达式的求值 164
6．3．2 中缀表达式到后缀表达式的转换 167
5．3．2 表遍历器类的实现 167
6．4 队列的实现 169
6．4．1 队列的向量实现 169
6．4．2 用双端表实现队列 171
6．4．3 用循环表实现队列 172
6．5 应用实例——农夫过河问题* 174
6．5．1 广度优先搜索法 176
6．5．2 深度优先搜索法 178
小结 179
习题 180
第七章 树和二叉树 182
7．1 基本概念 183
7．1．1 树 183
7．1．2 二叉树 185
7．1．3 树与二叉树的关系 187
7．2 二叉树的实现 188
7．2．1 二叉树结点类 188
7．2．2 基本二叉树类 191
7．2．3 二叉树的构造 193
7．3 二叉树的周游 195
7．3．1 周游的递归实现 195
7．3．2 通过遍历器实现周游 197
7．3．3 前序周游器类 198
7．3．4 中序周游器类 201
7．3．5 后序周游器类 203
7．3．6 层次周游算法（按宽度方向周游） 205
7．4 二叉树的向量表示 207
7．4．1 二叉树向量表示的一种基本方法 207
7．4．2 记录结构信息的二叉树向量表示 208
7．5 二叉排序树 209
7．6 平衡的二叉排序树 215
7．6．1 AVL树上的操作 215
7．6．1 AVL树的实现* 219
7．7 二叉树的应用——哈夫曼树 227
小结 230
习题 231
第八章 优先队列 233
8．1 优先队列的抽象 233
8．2 堆 236
8．3 堆排序 240
8．4 斜堆 241
8．5 离散事件模拟* 246
8．5．1 模拟类的结构 247
8．5．2 冰淇淋店的模拟 250
8．5．3 随机数* 252
小结 255
习题 255
第九章 散列结构 257
9．1 散列向量 257
9．2 开地址散列 260
9．3 散列表——用桶解决碰撞 263
9．4 散列表遍历器 266
9．5 桶排序 269
9．6 散列函数 270
小结 272
习题 272
第十章 集合与字典 274
10．1 集合及其运算 274
10．2 位向量集合 275
10．2．1 字符集 278
10．2．2 应用——将字符串分解为单词* 279
10．3 集合的表实现 281
10．4 用散列表实现集合 283
10．4．1 应用——拼写检查器* 285
10．5 字典与关联 287
10．6 字典的关联表实现 288
10．7．1 稀疏矩阵 291
10．7 字典的应用 291
10．7．2 索引的实现 295
10．8 用散列表实现字典 297
小结 300
习题 301
第十一章 图 303
11．1 基本概念 303
11．2 图的邻接矩阵表示和Warshall算法 304
11．2．2 图结点的可达性问题 305
11．3 邻接表方式的图表示和深度优先搜索 306
11．3．1 邻接表表示的结点类 306
11．3．2 用深度优先方式求解可达性问题 308
11．4 带权图的矩阵表示和Floyd算法 309
11．4．2 带权图最短路径问题和Floyd算法 310
11．4．1 带权图的邻接矩阵 310
11．5 带权图的邻接表表示与Dijkstra算法 312
11．5．1 带权图的邻接表表示 312
11．5．2 从一个结点出发的最短路径和Dijkstra算法 313
11．6 有限自动机* 315
11．7 拓扑排序 319
小结 320
习题 321
第十二章 文件 323
12．1 外存、文件及其问题 323
12．1．1 外存储器的特点与信息组织 323
12．1．2 文件基本结构和操作 324
12．1．3 文件与字典 325
12．1．4 文件组织 326
12．2 C++的字符流文件及其操作 327
12．3 归并排序 332
12．4 文件的随机访问* 336
12．5 文件索引结构 338
12．5．1 索引向量 339
12．5．2 树形索引结构 339
12．5．3 B树* 341
12．5．4 B+树* 344
小结 346
习题 346
附录A 主要抽象数据类及其相互关系 348
A．1 串及其主要相关类 348
A．2 向量及其主要相关类 349
A．3 表及其主要相关类 349
A．6 优先队列及其主要相关类 350
A．4 栈及其主要相关类 350
A．5 队列及其相关类 350
A．7 树及其主要相关类 351
A．8 散列表及其主要相关类 351
A．9 字典及其主要相关类 352
附录B Borland C++集成开发环境使用入门 353
B．1 概况 353
B．2 启动与退出 353
B．3 菜单与会话框操作 354
B．4 窗口管理 355
B．5 编辑命令 356
B．6 一些主要菜单命令 358
B．7 编程的几个基本步骤 362
参考文献 365