第1章 数据结构的基本概念1
1.1 数据结构的概念和术语1
1.2 抽象数据类型3
1.2.1 数据类型3
1.2.2 数据抽象与抽象数据类型4
1.3 算法和算法分析5
1.3.1 算法5
1.3.2 算法设计的要求5
1.3.3 算法效率的度量6
1.4 面向对象概述8
1.4.1 面向对象的思想9
1.4.2 面向对象程序设计9
1.4.3 面向对象的语言9
1.4.4 面向对象的基本概念10
1.4.5 面向对象的基本特性11
1.5 本章小结13
习题113
第2章 C++初步知识14
2.1 C++语言14
2.2 数组14
2.2.1 一维数组15
2.2.2 二维数组17
2.2.3 字符数组和字符串20
2.3 指针24
2.3.1 指针的概念24
2.3.2 指针的定义24
2.3.3 指针的运算25
2.4 指针和数组27
2.4.1 指针与数组名27
2.4.2 指向数组的指针28
2.4.3 存储指针的数组31
2.4.4 动态存储32
2.5 结构34
2.5.1 结构类型的定义34
2.5.2 结构变量的说明35
2.5.3 结构成员的引用36
2.5.4 结构数组和结构指针37
2.6 函数39
2.6.1 函数的声明、定义和调用40
2.6.2 函数的参数传递41
2.6.3 带默认参数的函数42
2.6.4 内置函数43
2.6.5 函数的重载44
2.7 本章小结45
习题245
实验训练245
第3章 C++类及其对象的封装性48
3.1 类的声明和对象的定义48
3.1.1 声明类类型48
3.1.2 定义对象的方法50
3.1.3 对象成员的引用51
3.2 类的成员函数52
3.2.1 成员函数的访问属性52
3.2.2 在类外定义成员函数52
3.2.3 内置成员函数53
3.2.4 成员函数的存储方式54
3.3 构造函数和析构函数55
3.3.1 对象的初始化55
3.3.2 构造函数的作用55
3.3.3 带参数的构造函数57
3.3.4 构造函数的重载58
3.3.5 拷贝构造函数58
3.3.6 析构函数59
3.4 相关特性61
3.4.1 引用61
3.4.2 友元67
3.4.3 运算符重载70
3.5 本章小结77
习题377
实验训练378
第4章 继承性和多态性81
4.1 继承与派生的概念81
4.1.1 派生类的声明与构成81
4.1.2 派生类成员的访问83
4.2 派生类的构造函数和析构函数87
4.2.1 简单的派生类的构造函数87
4.2.2 有子对象的派生类的构造函数88
4.2.3 多级派生时的构造函数90
4.2.4 派生类的析构函数91
4.3 多继承92
4.3.1 多继承的声明与使用92
4.3.2 多继承引起的二义性问题94
4.3.3 虚基类的概念与使用96
4.4 多态性与虚函数99
4.4.1 多态的概念99
4.4.2 虚函数的定义与使用99
4.4.3 虚析构函数103
4.4.4 纯虚函数与抽象类104
4.5 本章小结107
习题4107
实验训练4107
第5章 模板与标准模板库112
5.1 模板112
5.1.1 模板的概念112
5.1.2 函数模板112
5.1.3 类模板117
5.2 标准模板库120
5.3 序列式容器121
5.3.1 vector容器121
5.3.2 使用迭代器123
5.3.3 list容器124
5.4 关联式容器125
5.4.1 pair类型126
5.4.2 map容器127
5.4.3 set容器128
5.5 本章小结130
习题5131
实验训练5131
第6章 线性表133
6.1 线性表的定义133
6.1.1 线性表的逻辑结构133
6.1.2 线性表的抽象类定义134
6.2 线性表的顺序表示和实现135
6.2.1 线性表的顺序表示135
6.2.2 顺序表类的定义135
6.2.3 顺序表类的实现136
6.3 线性表的链式表示和实现140
6.3.1 线性表的链式表示140
6.3.2 抽象链表类的定义140
6.3.3 抽象链表类各成员函数的实现142
6.4 单链表143
6.4.1 单链表的定义143
6.4.2 单链表类的定义144
6.4.3 单链表的常用成员函数的实现144
6.4.4 单链表举例——一元多项式加法147
6.5 循环链表150
6.5.1 循环链表的定义150
6.5.2 循环链表类的定义150
6.5.3 循环链表常用函数的实现151
6.5.4 循环链表举例——约瑟夫问题155
6.6 双向链表155
6.6.1 双向链表的定义155
6.6.2 双向链表类的定义156
6.6.3 双向链表的常用成员函数的实现157
6.7 本章小结161
习题6161
实验训练6162
第7章 堆栈、队列和递归169
7.1 堆栈的概念及其运算169
7.2 抽象堆栈类的定义170
7.3 堆栈的定义及其实现170
7.3.1 顺序栈的定义170
7.3.2 顺序栈类的定义及典型成员函数
的实现171
7.3.3 多栈共享空间问题174
7.3.4 链栈的定义175
7.3.5 链式栈类的定义及典型成员函数
的实现176
7.4 堆栈的应用举例179
7.4.1 数制转换179
7.4.2 迷宫问题180
7.5 队列的概念及其运算183
7.6 抽象队列类的定义184
7.7 队列的定义及其实现184
7.7.1 队列的顺序存储结构184
7.7.2 循环队列的定义186
7.7.3 顺序循环队列类的定义及常用
成员函数的实现187
7.7.4 链式队列的定义189
7.7.5 链式队列类的定义及常用成员
函数的实现190
7.7.6 链式队列的应用举例193
7.7.7 优先级队列的定义194
7.7.8 优先级队列类的定义及常用
成员函数的实现194
7.8 递归197
7.8.1 递归的概念197
7.8.2 递归的应用198
7.8.3 递归在计算机中的实现199
7.8.4 递归问题的非递归算法201
7.9 本章小结204
习题7204
实验训练7205
第8章 树与二叉树212
8.1 树、二叉树和森林的基本概念212
8.1.1 树212
8.1.2 二叉树213
8.1.3 树与森林的存储结构218
8.2 二叉树的抽象类和树的类222
8.2.1 二叉树的抽象类222
8.2.2 树的类227
8.3 二叉树的遍历和树的遍历233
8.3.1 二叉树的遍历233
8.3.2 树的遍历236
8.4 二叉排序树239
8.5 二叉树的计数244
8.6 哈夫曼树及其应用244
8.6.1 优二叉树244
8.6.2 哈夫曼编码246
8.7 本章小结247
习题8247
实验训练8248
第9章 图253
9.1 图的基本概念253
9.1.1 图的定义253
9.1.2 图的术语254
9.1.3 图的基本操作256
9.1.4 图的存储表示256
9.2 图的抽象类260
9.2.1 图的邻接矩阵类261
9.2.2 图的邻接表类265
9.3 图的遍历271
9.3.1 深度优先搜索272
9.3.2 广度优先搜索273
9.4 图的连通性与小生成树274
9.4.1 无向图的连通分量和生成树274
9.4.2 小生成树274
9.4.3 关节点和重连通分量279
9.5 短路径281
9.5.1 图结点的可达性281
9.5.2 从某个源点到其余各顶点的 短路径282
9.5.3 每一对顶点之间的短路径284
9.6 活动网络286
9.6.1 AOV网络286
9.6.2 AOE网络287
9.7 本章小结288
习题9289
实验训练9290
第10章 查找与散列结构300
10.1 基本概念300
10.2 静态查找表301
10.2.1 顺序表的查找301
10.2.2 有序表的查找303
10.2.3 索引顺序表的查找305
10.3 动态查找表306
10.4 Hash表及其查找307
10.4.1 Hash表307
10.4.2 Hash函数的构造方法309
10.4.3 处理冲突的方法312
10.4.4 Hash表的查找及其分析313
10.5 本章小结315
习题10315
实验训练10316
第11章 排序324
11.1 排序的基本概念324
11.2 插入排序326
11.2.1 直接插入排序326


11.2.2 其他插入排序327
11.2.3 希尔排序330
11.3 快速排序331
11.4 选择排序334
11.4.1 简单选择排序334