第一章 面向对象的程序设计与C++ 1
1.1 什么是面向对象的程序设计 1
1.2 面向对象的程序设计与C++ 1
1.3 C++类与对象设计 2
1.4 继承性 3
1.5 多态性、虚函数和纯虚函数 6
1.6 generic类、函数模板和模板类 8
1.7 友元函数 9
1.8 引用 10
习题 14
第二章 数据结构概述 15
2.1 基本概念 15
2.1.1 数据、数据元素、数据对象 15
2.1.2 数据结构 16
2.2 数据结构的分类 17
2.3 抽象数据类型 19
2.3.1 两种软件设计方法 19
2.3.2 数据类型 19
2.3.3 抽象数据类型 20
2.4.1 算法概念 22
2.4 算法和算法分析 22
2.4.2 算法分析 24
习题 26
第三章 向量、栈和队列 29
3.1 线性表 29
3.1.1 线性表的抽象数据类型 29
3.1.2 线性表的类表示 31
3.2 向量 35
3.2.1 向量的抽象数据类型 35
3.2.2 向量的插入和删除 38
3.2.3 向量的应用 40
3.3 栈 44
3.3.1 栈的抽象数据类型及其实现 44
3.3.2 栈的应用 46
3.4 队列 56
3.4.1 队列的抽象数据类型及其实现 57
3.4.2 队列的应用 61
习题 69
4.1 动态数据结构 70
第四章 链表 70
4.2 单链表 71
4.2.1 基本概念 72
4.2.2 结点类 73
4.2.3 链表类 75
4.2.4 栈的链表实现 86
4.2.5 队列的链表实现 89
4.2.6 链表的应用举例 91
4.3 循环链表 97
4.4 双链表 100
习题 104
第五章 排序 107
5.1 基本概念 107
5.2 插入排序 108
5.2.1 直接插入排序 108
5.2.2 折半插入排序 110
5.2.3 Shell排序 112
5.3 交换排序 114
5.3.1 起泡排序 114
5.3.2 快速排序 116
5.4.1 基本思想 120
5.4 分配排序 120
5.4.2 基数排序 121
5.5 归并排序 124
5.6 外部排序 128
5.6.1 2路合并排序 128
5.6.2 多路替代选择合并排序 129
5.6.3 最佳合并排序 131
习题 132
6.2 顺序查找 133
第六章 查找 133
6.1 基本概念 133
6.3 折半查找 134
6.4 分块查找 136
6.5 散列查找 138
6.5.1 概述 138
6.5.2 散列函数 139
6.5.3 冲突的处理 142
习题 146
6.5.4 散列查找的效率 146
第七章 树和二叉树 148
7.1 树的概念 148
7.2 二叉树 149
7.2.1 二叉树的概念 149
7.2.2 二叉树的性质 150
7.2.3 二叉树的存储方式 152
7.2.4 树(树林)与二叉树的相互转换 154
7.3.1 树(树林)的遍历 155
7.3 树(树林)、二叉树的遍历 155
7.3.2 二叉树的遍历 156
7.4 抽象数据类型BinaryTree以及类BinaryTree 157
7.4.1 抽象数据类型BinaryTree 157
7.4.2 一个完整的包含类BinaryTreeNode、类BinaryTree实现的例子 157
7.5 二叉树的遍历算法 162
7.5.1 非递归(使用栈)的遍历算法 162
7.5.2 线索化二叉树的遍历 164
习题 169
8.1 二叉排序树 171
8.1.1 二叉排序树与类BinarySTree 171
第八章 树形结构的应用 171
8.1.2 二叉排序树的检索、插入、删除运算 172
8.1.3 等概率查找对应的最佳二叉排序树 176
8.2 平衡的二叉排序树 179
8.2.1 平衡的二叉排序树与类AVLTree 179
8.2.2 平衡的二叉排序树的插入、删除 181
8.2.3 类AVLTree与AVL树高度 190
8.3 B-树、B+-树 191
8.4.1 键树 196
8.4 键树和2-3树 196
8.4.2 2-3树 198
8.5 Huffman最优树 200
8.5.1 Huffman最优树 200
8.5.2 树编码 204
8.6 堆排序 205
8.7 判定树 214
习题 215
第九章 图 217
9.1 基本概念 217
9.2.1 相邻矩阵表示图 220
9.2 图的存储表示 220
9.2.2 图的邻接表表示 221
9.2.3 邻接多重表、十字链表 221
9.3 构造Graph类 224
9.3.1 基于邻接表表示的Graph类 224
9.3.2 Graph类的实现 226
9.4 图的遍历 231
9.4.1 深度优先遍历 232
9.5 最小代价生成树 234
9.4.2 广度优先遍历 234
9.6 单源最短路径问题 239
9.7 每一对顶点间的最短路径问题 242
9.8 有向无回路图 244
9.8.1 DAG图和AOV、AOE网 244
9.8.2 AOV网的拓扑排序 246
9.8.3 AOE网的关键路径 248
习题 250
10.1 多维数组 253
10.1.1 多维数组的顺序存储 253
第十章 多维数组和广义表 253
10.1.2 特殊矩阵的顺序存储 254
10.1.3 稀疏矩阵的存储 256
10.1.4 抽象数据类型稀疏矩阵与class SparseMatrix 258
10.2 广义表 265
10.2.1 广义表的概念 265
10.2.2 广义表的存储方式 266
10.2.3 广义表结点类和抽象类class List 269
习题 272
11.1 外部存储设备简介 273
第十一章 文件 273
11.2 有关文件的基本概念 275
11.3 顺序文件 277
11.4 索引文件 277
11.5 ISAM文件和VSAM文件 279
11.6 倒排文件和多重表文件 283
11.7 散列文件 284
习题 285
参考文献 286