第1章 基础 1
1.1 什么是数据结构 1
1.2 程序性能分析 2
1.2.1 程序性能的衡量标准 2
1.2.2 程序的事后测试 2
1.2.3 时间复杂性的计算方法 4
1.2.4 空间复杂性的计算方法 4
1.2.5 计算复杂性的表示方法 5
1.2.6 两种代价计算方法的比较 6
1.3 从抽象数据类型到C＋＋语言描述 7
1.4 C＋＋基础知识 7
1.4.1 C＋＋中的类和对象 8
1.4.2 C＋＋的输入和输出 11
1.4.3 C＋＋中的变量和常量 13
1.4.4 C＋＋中的函数 14
1.4.5 C＋＋中的动态存储分配 18
1.4.6 C＋＋中的继承 18
1.4.7 C＋＋中的多态性 20
1.4.8 其他 20
1.5 进阶导读 22
习题 23
第2章 线性表 24
2.1 线性表及其基本运算 24
2.1.1 线性表的定义与特点 24
2.1.2 线性表的基本运算 25
2.2 数组 26
2.2.1 数组的定义和特点 26
2.2.2 数组的类定义 26
2.2.3 数组的顺序存储方式 28
2.2.4 稀疏矩阵 32
2.3 线性表的顺序表示——顺序表 36
2.3.1 顺序表的定义和特点 36
2.3.2 顺序表类定义 36
2.3.3 顺序表的插入 37
2.3.4 顺序表的删除 38
2.3.5 顺序表的应用实例——用顺序存储的线性表表示多项式 39
2.4 线性表的链式表示——链表 44
2.4.1 线性链表的逻辑结构与建立 44
2.4.2 线性链表的类定义 45
2.4.3 线性链表的插入与删除 46
2.4.4 线性链表的应用实例——用线性链表表示多项式 49
2.4.5 几种变形的线性链表 51
2.4.6 双向链表 54
2.5 进阶导读 56
习题 57
第3章 串 59
3.1 串的定义 59
3.2 串的逻辑结构和基本操作 60
3.3 串的存储结构 61
3.3.1 串的数组存储表示 61
3.3.2 串的块链存储表示 61
3.4 串的实现 62
3.4.1 串的自定义类 62
3.4.2 串的实现 63
3.5 串的模式匹配算法 66
3.5.1 BF算法 67
3.5.2 KR算法 68
3.5.3 KMP算法 70
3.5.4 BM算法 72
3.6 进阶导读 76
习题 76
第4章 栈和队列 78
4.1 栈 78
4.1.1 栈的基本操作 78
4.1.2 用数组实现栈 79
4.1.3 用链表实现栈 81
4.1.4 栈的应用实例 82
4.2 队列 92
4.2.1 用数组实现队列 92
4.2.2 循环队列 93
4.2.3 双向队列 95
4.2.4 用链表实现队列 96
4.2.5 队列的应用举例 97
4.3 进阶导读 98
习题 99
第5章 递归和广义表 100
5.1 递归的概念 100
5.2 递归转化为非递归 102
5.3 广义表 106
5.3.1 广义表的概念与存储结构 106
5.3.2 广义表递归算法的实现 108
5.4 进阶导读 110
习题 110
第6章 树、二叉树和森林 111
6.1 基本概念 111
6.2 树的存储结构 113
6.3 树的线性表示 113
6.4 树的遍历 114
6.5 二叉树 116
6.6 二叉树的存储表示 120
6.7 二叉树的各种遍历 121
6.8 线索化二叉树 124
6.9 堆 130
6.10 计算二叉树的数目 133
6.11 二叉树的应用：霍夫曼树和霍夫曼编码 136
6.12 进阶导读 140
习题 140
第7章 查找与索引 142
7.1 查找与索引的概念 142
7.2 基于顺序表的查找 143
7.2.1 顺序表 143
7.2.2 顺序查找 144
7.2.3 有序顺序表上的查找操作 145
7.3 二叉查找树 147
7.3.1 二叉查找树的结构 147
7.3.2 二叉查找树上的查找 149
7.3.3 基于二叉查找树的遍历 150
7.3.4 最优二叉查找树 153
7.3.5 动态二叉查找树 160
7.4 B—树和B＋树 166
7.4.1 B—树的结构 166
7.4.2 B—树的查询 167
7.4.3 B—树的插入 168
7.4.4 B—树的删除 170
7.4.5 B＋树 172
7.5 Trie树 173
7.5.1 Trie树的定义 173
7.5.2 Trie树的查找 174
7.5.3 Trie树的插入和删除 175
7.6 Hash查找 177
7.6.1 Hash函数 177
7.6.2 解决冲突的方法 179
7.6.3 Hash查找的讨论 180
7.7 进阶导读 181
习题 182
第8章 图 184
8.1 图的基本概念 184
8.2 图的存储结构 187
8.2.1 邻接矩阵 187
8.2.2 邻接表 189
8.3 图的遍历与求图的连通分量 194
8.3.1 深度优先查找法 194
8.3.2 广度优先查找法 195
8.3.3 求图的连通分量 197
8.4 生成树与最小（代价）生成树 197
8.4.1 普里姆（Prim）算法 198
8.4.2 克鲁斯卡尔（Kruskal）算法 200
8.5 最短路径 201
8.5.1 求某个顶点到其他顶点的最短路径 202
8.5.2 求一对顶点之间的最短路径 205
8.5.3 传递闭包 207
8.6 拓扑排序 210
8.7 关键路径 213
8.8 进阶导读 219
习题 219
第9章 排序 222
9.1 问题定义 222
9.2 基本排序方法 223
9.2.1 插入排序 223
9.2.2 冒泡排序 224
9.2.3 选择排序 225
9.3 归并排序 226
9.4 快速排序 229
9.4.1 基本算法 229
9.4.2 性能 230
9.4.3 快速排序的一些改进策略 232
9.4.4 重复值 233
9.5 堆排序 235
9.5.1 堆及其基本操作 235
9.5.2 堆排序 238
9.6 希尔排序 241
9.7 基数排序 242
9.8 内部排序方法的比较 245
9.9 进阶导读——〈algorithm〉中的sort（）函数 246
习题 247
第10章 外部排序 249
10.1 外部存储设备 249
10.1.1 磁带存储设备 249
10.1.2 磁盘存储设备 250
10.2 外排序的基本过程 251
10.3 磁盘文件的外排序方法 251
10.4 磁带文件的外排序方法 254
10.4.1 平衡合并排序 256
10.4.2 多阶段合并排序 256
10.5 进阶导读 262
习题 262