第一部分 面向对象的C＋＋程序设计基础 1
第1章 面向对象的设计方法 1
1.1 面向对象的思想 1
1.1.1 面向对象的程序设计 2
1.1.2 面向对象的语言 2
1.2 面向对象的基本概念 2
1.2.1 对象 2
1.2.2 消息 3
1.2.3 类 4
1.3 面向对象的基本特性 4
1.3.1 封装性 4
1.3.2 继承性 5
1.3.3 多态性 5
1.4 C＋＋的初步知识 5
1.4.1 从C到C＋＋ 6
1.4.2 最简单的C＋＋程序 8
1.4.3 C＋＋程序的构成和书写形式 11
1.4.4 C＋＋程序的编写和实现 12
习题一 14
第2章 C＋＋类及其对象的封装性 15
2.1 类的声明和对象的定义 15
2.1.1 类和对象的关系 15
2.1.2 声明类类型 16
2.1.3 定义对象的方法 18
2.1.4 类和结构体类型的异同 20
2.2 类的成员函数 22
2.2.1 成员函数的性质 22
2.2.2 在类外定义成员函数 22
2.2.3 inline成员函数 23
2.2.4 成员函数的存储方式 24
2.3.1 通过对象名和成员运算符访问对象中的成员 26
2.3.2 通过指向对象的指针访问对象中的成员 26
2.3 对象成员的引用 26
2.4 类的封装性和信息隐蔽 28
2.4.1 公共接口和私有实现的分离 28
2.4.2 类声明和成员函数定义的分离 29
2.5 构造函数 32
2.5.1 对象的初始化 32
2.5.2 构造函数的作用 33
2.5.3 带参数的构造函数 35
2.5.4 用参数初始化表对数据成员初始化 36
2.5.5 构造函数的重载 36
2.5.6 使用默认参数的构造函数 38
2.6 析构函数 42
2.7 调用构造函数和析构函数的顺序 44
2.8 对象指针 45
2.8.1 指向对象的指针 45
2.8.2 指向对象成员的指针 46
2.8.3 this指针 49
2.9 动态存储 50
2.10 C＋＋中的对象 51
习题二 53
第3章 友元、重载和引用 55
3.1 友元 55
3.1.1 友元的定义 55
3.1.2 友元函数 56
3.1.3 友元成员 57
3.1.4 友元类 60
3.2 重载 62
3.2.1 函数重载 62
3.2.2 运算符重载 66
3.3 引用 80
3.3.1 引用的概念 80
3.3.2 引用的应用 82
3.3.3 引用作为函数参数 83
习题三 89
第4章 继承与派生 91
4.1 继承与派生的概念 91
4.2 派生类的声明方式 92
4.3 派生类的构成 93
4.4 派生类成员函数的访问属性 95
4.4.1 公有继承 95
4.4.2 私有继承 97
4.4.3 保护成员和保护继承 99
4.4.4 多级派生时的访问属性 103
4.5 派生类的构造函数和析构函数 110
4.5.1 简单的派生类的构造函数 110
4.5.2 有子对象的派生类的构造函数 112
4.5.3 多级派生时的构造函数 114
4.5.4 派生类构造函数的特殊形式 116
4.5.5 派生类的析构造函数 116
4.6 多继承 117
4.6.1 声明多继承的方法 118
4.6.2 多继承派生类的构造函数 118
4.6.3 多继承的析构函数 120
4.6.4 多继承引起的二义性问题 121
4.7 虚基类 124
4.7.1 虚基类的概念 124
4.7.2 虚基类的初始化 126
习题四 129
第5章 多态性与虚函数 133
5.1 多态性 133
5.1.1 多态性的概念 133
5.1.2 编译时的多态性 133
5.1.3 运行时的多态性 135
5.2 虚函数 137
5.2.1 虚函数的作用 137
5.2.2 虚函数的声明 138
5.2.3 虚析构函数 141
5.3 纯虚函数与抽象类 142
5.3.1 纯虚函数 142
5.3.2 抽象类 144
5.3.3 应用实例 146
习题五 151
第6章 模板 154
6.1 模板的概念 154
6.2 函数模板 155
6.2.1 函数模板和模板函数 155
6.2.2 重载模板函数 160
6.3 类模板 161
6.3.1 类模板和模板类的概念 161
6.3.2 类模板的派生 164
习题六 165
7.1 数据结构的基本概念 166
第7章 绪论 166
第二部分 数据结构——用面向对象方法与C＋＋描述 166
7.2 抽象数据类型及面向对象概念 168
7.2.1 数据类型 168
7.2.2 数据抽象与抽象数据类型 168
7.3 算法和算法分析 169
7.3.1 算法 169
7.3.2 算法设计的要求 169
7.3.3 算法效率的度量 170
7.4 数据结构的抽象层次 172
习题七 173
第8章 线性表 174
8.1 线性表的定义 174
8.1.1 线性表的逻辑结构 174
8.1.2 线性表的存储表示 174
8.2 抽象链表类 176
8.2.1 线性链表的特点 176
8.2.2 抽象链表类的定义 177
8.2.3 抽象链表中各成员函数的实现 178
8.3 单链表 180
8.3.1 单链表的定义 180
8.3.2 单链表类的定义 180
8.3.3 单链表的常用成员函数的实现 181
8.3.4 单链表举例——一元多项式加法 185
8.4.1 循环链表的定义 188
8.4.2 循环链表类的定义 188
8.4 循环链表 188
8.4.3 循环链表常用函数的实现 189
8.4.4 循环链表举例——约瑟夫（Josephu）问题 194
8.5 双向链表 195
8.5.1 双向链表的定义 195
8.5.2 双向链表类的定义 196
8.5.3 双向链表的常用成员函数的实现 196
习题八 201
9.1.2 数组的存储结构 203
9.1.1 数组的逻辑结构 203
第9章 数组 203
9.1 数组的定义 203
9.1.3 数组的常用操作 204
9.2 数组类的定义及实现 204
9.2.1 数组类的定义 204
9.2.2 数组类常用函数的实现 206
9.2.3 数组类的应用举例——一元多项式加法 212
习题九 215
第10章 串 217
10.1 串的概念 217
10.1.1 串的定义 217
10.1.2 串的基本术语 217
10.1.3 串的存储表示和实现 218
10.1.4 串的基本运算 218
10.2.1 字符串类的定义 219
10.2 字符串类的定义及实现 219
10.2.2 字符串类中常用成员函数的实现 220
习题十 232
第11章 堆栈与队列 233
11.1 堆栈的概念及其运算 233
11.2 栈的抽象类定义 234
11.3 栈的定义及其实现 235
11.3.1 顺序栈的定义 235
11.3.2 顺序栈类的定义及典型成员函数的实现 235
11.3.3 多栈共享空间问题 238
11.3.4 链栈的定义 240
11.3.5 链式栈类的定义及典型成员函数的实现 241
11.4 堆栈的应用举例 244
11.4.1 数制转换 244
11.4.2 一个趣味游戏——迷宫问题 245
11.6 抽象队列类的定义 250
11.5 队列的概念及其运算 250
11.7 队列的定义及其实现 251
11.7.1 队列的顺序存储结构 251
11.7.2 循环队列的定义 253
11.7.3 顺序循环队列类的定义及常用成员函数的实现 254
11.7.4 链式队列的定义 256
11.7.5 链式队列类的定义及常用成员函数的实现 257
11.7.6 链式队列的应用举例 260
11.7.8 优先级队列类的定义及常用成员函数的实现 262
11.7.7 优先级队列的定义 262
习题十一 266
第12章 树 268
12.1 树、二叉树与森林的基本概念 268
12.1.1 树 268
12.1.2 二叉树 269
12.1.3 树与森林的存储结构 275
12.2.1 二叉树的抽象类 279
12.2 二叉树的抽象类和树的抽象类 279
12.2.2 树的抽象类 286
12.3 二叉树的遍历和树的遍历 293
12.3.1 二叉树的遍历 293
12.3.2 树的遍历 300
12.4 二叉排序树 303
12.5 二叉树的计数 308
12.6 赫夫曼树及其应用 310
12.6.1 最优二叉树（赫夫曼树） 310
12.6.2 赫夫曼编码 312
习题十二 314
第13章 图 316
13.1 图的基本概念 316
13.1.1 图的定义 316
13.1.2 图的术语 317
13.1.3 图的基本操作 319
13.1.4 图的存储表示 320
13.2 图的抽象类 325
13.2.1 图的邻接矩阵类 325
13.2.2 图的邻接表类 331
13.3 图的遍历 339
13.3.1 深度优先搜索DFS 340
13.3.2 广度（或宽度）优先搜索BFS 341
13.4 图的连通性与最小生成树 342
13.4.1 无向图的连通分量和生成树 342
13.4.2 最小生成树 342
13.4.3 关节点和重连通分量 349
13.5 最短路径 352
13.5.1 图结点的可达性 352
13.5.2 从某个源点到其余各顶点的最短路径 353
13.5.3 每一对顶点之间的最短路径 355
13.6 活动网络 357
13.6.1 用顶点表示活动的网络（AOV网络） 358
13.6.2 用边表示活动的网络（AOE网络） 359
习题十三 361
第14章 查找与散列结构 364
14.1 静态查找表 365
14.1.1 顺序表的查找 365
14.1.2 有序表的查找 367
14.1.3 索引顺序表的查找 369
14.2 动态查找表 370
14.3 哈希表及其查找 376
14.3.1 哈希表 376
14.3.2 哈希函数的构造方法 378
14.3.3 处理冲突的方法 381
14.3.4 哈希表的查找及其分析 382
习题十四 385
第15章 排序 387
15.1 排序的基本概念 387
15.2.1 直接插入排序 389
15.2 插入排序 389
15.2.2 其他插入排序 391
15.2.3 希尔排序 394
15.3 快速排序 396
15.4 选择排序 399
15.4.1 简单选择排序 399
15.4.2 锦标赛排序 400
15.4.3 堆排序 404
15.5 归并排序 410
15.5.1 归并 410
15.5.2 迭代的归并排序算法 411
15.6 基数排序 413
15.6.1 多关键字排序 413
15.6.2 链式基数排序 414
习题十五 417
参考文献 418