1 绪论 1
1.1 （算法＋数据结构）=程序 1
1.2 数据结构的基本概念 2
1.2.1 两个简单的数据结构实例 2
1.2.2 什么是数据结构 3
1.3 C＋＋语言基础 4
1.3.1 程序结构 5
1.3.2 数据声明和作用域 6
1.3.3 输入/输出 7
1.3.4 函数 9
1.3.5 参数传递 10
1.3.7 动态内存分配 11
1.3.6 函数名重载 11
1.3.8 结构与联合 12
1.4 算法性能与复杂度 16
1.4.1 算法的定义 16
1.4.2 算法的性能标准 17
1.4.3 算法的复杂度 17
习题1 21
2 抽象数据类型和C＋＋类 23
2.1 抽象数据类型 23
2.1.1 从数据类型到抽象数据类型 23
2.1.2 封装和信息隐藏 24
2.1.3 抽象数据类型描法 25
2.2.1 类与对象 26
2.2 类与对象的基本概念 26
2.2.2 消息与合作 28
2.2.3 多态性 28
2.3 面向对象的程序设计方法 28
2.4 C＋＋类与对象 29
2.5 构造函数和析构函数 31
2.6 工具函数 35
2.7 继承 38
2.8 this指针的使用 41
2.9 虚函数、多态性以及动态联编 42
2.9.1 虚函数和多态性 42
2.9.2 动态联编 50
2.10 模板类 52
习题2 54
3 线性表 56
3.1 线性表的定义 56
3.2.1 顺序表的类定义 57
3.2.2 顺序表输入、删除算法的复杂度分析 60
3.2.3 顺序表的应用 61
3.3 线性表的链表表示 62
3.3.1 单链表 62
3.3.2 单循环链表 73
3.3.3 双向循环链表 73
3.3.4 静态链表 79
3.4.2 多项式相加 81
3.4.1 多项式表示 81
3.4 多项式抽象数据类型 81
习题3 83
4 栈、队列和递归 85
4.1 栈 85
4.1.1 顺序栈 86
4.1.2 链式栈 88
4.1.3 表达式的计算 90
4.2 队列 94
4.2.1 循环队列 95
4.2.2 链队列 98
4.3.1 递归的概念 100
4.3 递归 100
4.3.2 递归过程与递归工作栈 101
4.3.3 消除递归 103
4.3.4 迷宫问题 107
习题4 109
5 串、数组和广义表 112
5.1 字符串 112
5.1.1 字符串的定义、存储结构和操作 112
5.1.2 串的操作 113
5.1.3 常用的C＋＋字符串函数 114
5.1.4 串类及其实现 115
5.1.5 模式匹配算法 121
5.2 数组 125
5.2.2 数组的抽象数据类型表示 126
5.2.1 C＋＋中数组的定义 126
5.2.3 数组的顺序存储结构 128
5.3 稀疏矩阵 130
5.3.1 三元组顺序表 131
5.3.2 十字链表 133
5.4 广义表 135
5.4.1 广义表的定义 135
5.4.2 广义表的存储结构 136
5.4.3 n元多项式的表示 139
5.4.4 广义表的递归算法 141
习题5 144
6.1 树的概念 147
6 树和森林 147
6.1.1 树的定义 148
6.1.2 树的术语 148
6.1.3 树的表示形式 149
6.1.4 树的基本操作和抽象数据类型 149
6.2 二叉树 153
6.2.1 二叉树的定义 153
6.2.2 二叉树的性质 153
6.2.3 二叉树的基本操作和抽象数据类型 155
6.3 二叉树的存储结构 158
6.3.1 数组表示法 159
6.3.2 链表表示法 160
6.3.3 二叉树的二叉锭表类声明 160
6.4.1 前序遍历 164
6.4 遍历二叉树 164
6.4.2 中序遍历 165
6.4.3 后序遍历 165
6.4.4 层序遍历 166
6.5 线索二叉树 168
6.5.1 线索二叉树的定义 168
6.5.2 线索二叉树的类定义 170
6.5.3 中序线索二叉树 173
6.6 二叉树的应用 177
6.6.1 堆 177
6.6.2 哈夫曼树 183
6.7 树和森林 187
6.7.1 树的存储结构 187
6.7.2 树、森林和二叉树的转换 190
6.7.3 树的高历 192
6.7.4 森林的遍历 193
6.8 等价类及其表示 194
6.8.1 等价关系与等价类 194
6.8.2 并查集 195
习题6 199
7 图 203
7.1 图的基本概念 203
7.1.1 图的定义 203
7.1.2 图的术语 204
7.1.3 图的基本操作和抽象数据类型 207
7.2.1 邻接矩阵 209
7.2 图的存储结构 209
7.2.2 邻接表 212
7.2.3 邻接多重表 217
7.2.4 十字链表 219
7.3 图的遍历与连通性 220
7.3.1 深度优先遍历 220
7.3.2 广度优先遍历 221
7.3.3 连通分量 223
7.4 最小生成树 224
7.4.1 克鲁斯卡尔算法 225
7.4.2 普里姆算法 228
7.5 最短路径 230
7.5.1 弧上权值为非负情形的单源点最短路径问题 231
7.5.2 弧上权值为任意值的单源点最短路径问题 234
7.5.3 所有顶点之间的最短路径 236
7.6 活动风险 238
7.6.1 用顶点表示活动的网络 238
7.6.2 用边表示活动的网络（AOE网络） 242
习题7 246
8 查找 250
8.1 基本概念 250
8.2 顺序表 251
8.2.1 顺序表的查找 251
8.2.2 有序表的折半查找 252
8.3.1 索引顺序表 256
8.3 索引顺序表 256
8.3.2 倒排表 258
8.4 二叉排序树 260
8.4.1 二叉排序树定义 260
8.4.2 二叉排序树上的查找 262
8.4.3 二叉排序树的插入 263
8.4.4 二叉排序树的删除 265
8.4.5 二叉排序树查找的性能分析 266
8.5 平衡二叉树 266
8.5.1 平衡二叉树的定义 267
8.5.2 平衡旋转 267
8.5.3 平衡二叉树的插入和删除 269
8.6.1 动态的m路查找树 273
8.6 B-树 273
8.6.2 B-树 274
8.6.3 B-树的插入 274
8.6.4 B-树的删除 276
8.6.5 B＋树 278
8.7 散列表查找 279
8.7.1 散列表的基本概念 279
8.7.2 散列函数 281
8.7.3 处理溢出的闭散列方法 282
8.7.4 处理溢出的开散列方法——链地址法 286
8.7.5 散列表分析 287
习题8 288
9.1.1 基本概念 292
9 排序 292
9.1 基础知识 292
9.1.2 排序表的抽象数据类型描述和类定义 293
9.2 交换排序 299
9.2.1 冒泡排序 299
9.2.2 快速排序 300
9.3 插入排序 302
9.3.1 直接插入排序 302
9.3.2 折半插入排序 306
9.3.3 希尔排序 306
9.4 选择排序 308
9.4.1 直接选择排序 308
9.4.2 锦标赛排序 310
9.4.3 堆排序 312
9.5 归并排序 314
9.5.1 归并 314
9.5.2 两路归并排序 315
9.5.3 递归的归并排序 317
9.6 基数排序 319
9.6.1 多关键字排序 319
9.6.2 链式基数排序 320
9.7 各种排序方法的选择和使用 322
习题9 323
主要参考文献 326