目录 1
第1章 面向对象程序设计基础 1
1.1 C＋＋基本特征 1
1.1.1 重载 1
1.1.2 缺省参数函数与内置函数 3
1.1.3 引用及其使用 3
1.1.4 动态内存分配 7
1.2 类和对象 8
1.2.1 声明类和对象 9
1.2.2 在类外定义成员函数 10
1.2.3 类数组、类指针与函数的类参数 11
1.2.4 this指针 14
1.3 构造函数与析构函数 15
1.3.1 构造函数 15
1.3.2 析构函数 16
1.4 继承与派生 17
1.4.1 建立派生类 18
1.4.2 公用派生类与私有派生类 19
1.4.3 保护成员 20
1.4.4 友元函数与友元类 20
1.5 C＋＋模板 23
1.5.1 函数模板 23
1.5.2 类模板 25
习题 26
第2章 数据结构导论 31
2.1 数据结构的基本概念 31
2.1.1 几个实例 31
2.1.2 数据结构的术语 33
2.1.3 抽象数据类型及其实现 34
2.2 算法描述 35
2.2.1 算法的特性 35
2.2.2 算法描述与通用性 35
2.2.3 类和算法的测试 38
2.3 C＋＋标准模板库简介 38
2.4 算法分析初步 41
习题 44
第3章 向量 47
3.1 向量的基本知识 47
3.1.1 线性表的定义 47
3.1.2 向量的存储结构 47
3.2 向量运算 48
3.2.1 向量运算简介 48
3.2.2 插入算法与删除算法 49
3.3 简易向量类 52
3.3.1 简易向量类及其实现 52
3.3.2 简易向量类的测试 54
3.4 标准模板向量类 55
3.4.1 模板向量类的构造器及下标运算符 55
3.4.2 模板向量类的迭代器 56
3.4.3 模板向量类的成员函数 58
3.4.4 insert类算法和erase类算法分析 58
3.4.5 模板向量类的一般表示 61
3.5 模板向量容器的测试类 62
3.5.1 模板向量测试类的数据输入 62
3.5.2 模板向量测试类的源代码 63
3.5.3 模板向量测试类的使用 66
3.6 矩阵类 67
3.6.1 矩阵容器的描述 68
3.6.2 模板矩阵类的使用 69
习题 71
第4章 链表 73
4.1 链表存储结构的基本知识 73
4.1.1 单链表与指针 73
4.1.2 单链表的基本运算 75
4.2 简易的单链表类 79
4.2.1 单链表类源代码 79
4.2.2 单链表类的测试 80
4.3 循环链表和双向链表 82
4.3.1 循环链表 82
4.3.2 双向链表 82
4.4 标准模板双向链表类 83
4.4.2 构造器 84
4.4.1 模板链表类的一般表示 84
4.4.3 模板链表类的迭代器 85
4.4.4 模板链表类的成员函数 87
4.5 模板链表容器的测试类 89
4.5.1 模板链表测试类的数据输入 89
4.5.2 模板链表测试类的源代码 89
4.5.3 模板链表测试类的使用 93
习题 95
第5章 栈和队列 97
5.1 栈 97
5.1.1 栈的定义及运算 97
5.1.3 简易向量栈类 98
5.1.2 栈的向量存储结构 98
5.1.4 栈的链表存储结构 102
5.1.5 简易链表栈类 103
5.2 模板栈容器 108
5.2.1 模板栈容器的实现 108
5.2.2 栈的接口 109
5.2.3 使用栈容器 110
5.3 队列的基本知识 115
5.3.1 队列的定义及运算 115
5.3.2 队列的向量存储结构 116
5.3.3 简易的循环队列类 117
5.3.4 队列的链表存储结构 120
5.4.1 deque容器 124
5.4 模板队列容器 124
5.4.2 queue容器 125
习题 128
第6章 字符串 133
6.1 字符与字符串的概念 133
6.2 C风格字符串的存储结构与运算 134
6.2.1 C风格字符串的顺序存储结构 134
6.2.2 C风格字符串的链表存储结构 135
6.2.3 C风格字符串的运算 136
6.3 字符串类 138
6.3.1 字符串类对象的声明 139
6.3.2 字符串类的构造器 140
6.3.3 字符串类的运算 141
6.4 模板容器与字符串类 144
习题 148
第7章 查找 151
7.1 查找方法概述 151
7.2 顺序查找 152
7.2.1 简单顺序查找方法 152
7.2.2 一般线性表的顺序查找 153
7.3 有序表的查找 156
7.3.1 有序表的建立 156
7.3.2 有序表的折半查找法 157
7.3.3 折半查找法的应用 161
7.4.1 STL迭代器 164
7.4 标准模板库的查找算法 164
7.4.2 STL查找运算 165
7.5 哈希表及其查找 169
7.5.1 哈希表与哈希函数 169
7.5.2 设计哈希函数 171
7.5.3 闭散列方法 173
7.5.4 哈希类的向量版本 176
7.5.5 开散列方法与哈希类的链表版本 179
习题 183
第8章 排序 187
8.1 排序基本概念 187
8.2.1 直接插入排序 188
8.2 3种基本的排序方法 188
8.2.2 冒泡排序 189
8.2.3 选择排序 191
8.2.4 基本排序方法的向量版本 192
8.3 高级排序方法 194
8.3.1 希尔排序 194
8.3.2 快速排序 195
8.3.3 归并排序 198
8.3.4 基数排序 200
8.4 标准模板库的通用排序方法 202
习题 209
9.1.1 树的常用术语 212
第9章 树 212
9.1 二叉树 212
9.1.2 二叉树的定义 213
9.1.3 二叉树的重要性质 213
9.1.4 二叉树的存储结构 214
9.2 遍历二叉树 215
9.2.1 先根遍历 216
9.2.2 中根遍历 217
9.2.3 后根遍历 218
9.2.4 按层遍历 219
9.2.5 二叉树遍历算法的应用 220
9.3 二叉链表模板类 221
9.3.2 二叉链表类的模板结点类 222
9.3.1 二叉链表类的输入类 222
9.3.3 二叉链表基类 223
9.3.4 二叉链表类派生的应用类 228
9.4 二叉搜索树模板类 231
9.4.1 二叉搜索树的基本知识 231
9.4.2 定位函数与查找算法的实现 235
9.4.3 二叉搜索树类及其测试 237
9.4.4 二叉搜索树插入算法与删除算法的实现 240
9.4.5 输出二叉树结点表算法的实现 245
习题 248
10.1.1 图的概念 250
10.1 图的基本概念和术语 250
第10章 图 250
10.1.2 路径和回路 251
10.1.3 连通图 251
10.1.4 顶点的度 252
10.2 图的存储结构 252
10.2.1 邻接矩阵 252
10.2.2 基于邻接矩阵的模板图类 253
10.2.3 邻接链表 258
10.2.4 基于邻接链表的模板图类 259
10.3 图的遍历及其应用 264
10.3.1 图的深度优先搜索遍历 265
10.3.2 图的广度优先搜索遍历 268
10.3.3 图遍历的应用 269
10.3.4 图的遍历类 272
10.4 图的生成树 276
10.4.1 生成树的概念 276
10.4.2 最小生成树 277
10.4.3 Prim算法 280
10.4.4 Kruskal算法 284
10.5 最短路径 288
10.5.1 单源顶点最短路径问题求解 289
10.5.2 关于源点最短路径的讨论 292
习题 294