第1章 数据结构基础 1
1.1什么是数据结构 1
1.2数据结构的定义 1
1.3数据结构的目的 2
1.4数据结构的种类 3
1.5数据结构与抽象数据类型 5
1.6数据结构的特性 6
1.7数据结构的表现方式 7
1.8数据结构的基本操作 10
1.8.1数据结构操作的成本 10
1.8.2最好、最坏、平均 12
1.8.3 O、Ω、？表示 12
1.9数据结构的哲学 13
1.10为什么学习数据结构 15
思考题 16
第2章 栈结构 17
2.1后进先出即为栈 17
2.2栈的定义 18
2.3栈的实现 19
2.4栈的应用 22
2.4.1应用1：乘坐校园通勤车 22
2.4.2应用2：反转波兰计算器 23
2.4.3表达式的前、中、后缀表示及其转换 30
2.4.4应用3：括号匹配 30
2.5链接栈（栈的链接实现） 32
2.6链接栈存在的问题 35
思考题 39
第3章 队列结构 40
3.1先进先出即为队列 40
3.2队列的实现 41
3.3队列实现的别样问题 44
3.4队列的环形实现 45
3.5基于计数器的循环队列的实现 47
3.6队列应用举例 49
3.6.1应用1：先来先得礼品专送 49
3.6.2应用2：机场模拟程序 50
3.7链接队列 58
3.8链接队列应用举例：多项式算术 62
思考题 70
第4章 表结构 72
4.1表的定义 72
4.2表的实现 73
4.3表结构应用举例：查找特定位置上的乘客编号 77
4.4链表——链接实现的表结构 78
4.4.1链表的插入操作 80
4.4.2链表的删除操作 82
4.4.3链表的其他操作 82
4.4.4链表操作的时间成本 84
4.4.5链表的优化：记住当前位置 84
4.5双链表 86
4.6基于数组和基于链表实现的表结构比较 91
4.7链表的应用举例：字典 92
4.8讨论：栈、队列、表、栈表、队表 96
思考题 98
第5章 查找操作 99
5.1什么是查找 99
5.2查找的实现 100
5.3顺序查找 101
5.4折半查找 102
5.5查找的成本下限 106
5.6常数查找 107
5.6.1直接查找 107
5.6.2间接查找 107
思考题 112
第6章 排序操作 114
6.1什么是排序 114
6.2排序的实现 115
6.3插入排序 116
6.4选择排序 119
6.5冒泡/沉底排序 120
6.6希尔排序 122
6.7归并排序 124
6.7.1归并排序的时间复杂性 126
6.7.2归并排序的链表实现 127
6.8快速排序 131
6.8.1快速排序的过程 131
6.8.2快速排序的时间成本分析 134
思考题 135
第7章 高级表结构 136
7.1穷则思变 136
7.2跳转表 138
7.2.1跳转表的定义 139
7.2.2跳转表操作 140
7.3索引表 146
7.4哈希表（散列表） 148
7.4.1哈希函数 149
7.4.2哈希结构中的碰撞问题 150
7.4.3开放寻址哈希 151
7.4.4封闭寻址哈希 152
7.4.5探寻序列的设计 153
7.4.6哈希结构的查找效率 155
7.4.7哈希表的实现 155
7.4.8哈希表结构的测试 157
7.5讨论：跳转表、哈希表、索引表 159
思考题 160
第8章 树结构 161
8.1树结构的定义 162
8.2二叉树 165
8.2.1二叉树的另一种表示 166
8.2.2二叉树的遍历 166
8.2.3编译器中用到的二叉树结构 169
8.2.4二叉树的基本操作 170
8.3二叉查找树 171
8.3.1二叉查找树的查找操作 173
8.3.2二叉查找树的插入操作 174
8.3.3二叉查找树的删除操作 176
8.3.4构建初始二叉查找树 180
8.3.5二叉查找树结构的测试 181
8.3.6二叉查找树的高度 184
8.4平衡二叉树 187
8.5 AVL高度平衡树 188
8.5.1 AVL树的实现 189
8.5.2 AVL树的插入操作 190
8.5.3 AVL树的节点删除操作 199
8.5.4 AVL树结构的测试 203
8.6满二叉树和完全二叉树 206
思考题 207
第9章 高级树结构 208
9.1仅有二叉树是不够的 208
9.2 B树 209
9.2.1 B树的结构 209
9.2.2 B树的键值 210
9.2.3 B树的优势 210
9.3 B+树和B﹡树 211
9.3.1 B+树的定义 211
9.3.2 B+树的操作 212
9.3.3 B/B+树的代码实现 217
9.3.4 B+树的初始构建 222
9.3.5 B+树结构对磁盘查找的支持 223
9.4伸展树结构 224
9.4.1伸展树的特点 224
9.4.2伸展树的操作 225
9.4.3伸展树的实现 227
9.4.4伸展树结构的测试 232
9.5哈夫曼树 234
9.5.1构造哈夫曼树 235
9.5.2哈夫曼树的应用 236
9.6树的转换 238
9.6.1一般树到二叉树的转换 238
9.6.2森林到二叉树的转换 240
9.7树和森林的遍历 240
9.8其他树结构 242
思考题 243
第10章 堆结构 244
10.1什么是堆结构 244
10.2二叉堆结构 246
10.2.1二叉堆的表示 246
10.2.2二叉堆的实现 246
10.2.3堆的初始化构建 249
10.2.4堆结构的测试——堆排序 252
10.2.5堆的合并 255
10.3幂树 255
10.4幂堆 256
10.4.1幂堆的实现 257
10.4.2幂堆的合并操作 259
10.4.3幂堆的插入操作 260
10.4.4在幂堆里获取最大值 261
10.4.5在幂堆里删除最大值 262
10.5斐波那契堆 263
10.5.1斐波那契堆的定义 263
10.5.2斐波那契堆的操作实现 264
10.5.3斐波那契堆的节点更新操作 265
10.5.4删除任意节点操作 265
思考题 267
第11章 图结构 268
11.1图无处不在 268
11.2图的定义 270
11.3图的表示 272
11.4图的遍历 276
11.5图的最短路径操作 279
11.5.1 Dijkstra方法 280
11.5.2 Dijkstra方法的正确性证明 281
11.5.3最短路径方法的代码实现 282
11.6最小生成树操作 283
11.6.1 Prim方法 284
11.6.2 Prim方法的正确性证明 285
11.6.3 Prim方法的代码实现 286
11.7图的拓扑排序操作 287
11.7.1深度优先的拓扑排序 288
11.7.2广度优先拓扑排序 290
11.8图结构的测试 291
思考题 295
第12章 集合结构 297
12.1什么是集合结构 297
12.2数值集合 298
12.2.1数值集合的实现 298
12.2.2数值集合结构的测试 301
12.3基于动态数组的集合结构 303
12.4基于位矢量的集合结构 304
12.4.1基于位矢量的集合结构定义 304
12.4.2位矢量集合结构的并、交、减操作 306
12.4.3位矢量集合结构的其他操作 307
12.4.4位矢量集合结构的测试 308
12.5基于链表的集合结构 309
思考题 314
第13章 划分结构 315
13.1划分结构 315
13.1.1划分结构的实现 316
13.1.2划分结构的测试 318
13.1.3划分结构的操作成本 321
13.2划分森林结构 322
13.2.1划分森林的实现 323
13.2.2构建与析构 323
13.2.3查找和合并 324
13.3优化的划分结构实现 326
13.3.1路径压缩 326
13.3.2按规模合并 328
13.3.3按秩合并 330
13.3.4划分类结构的测试 331
13.4划分结构的应用 334
思考题 337
附录 338
附录1标准模板结构 338
FL1.1标准模板库数据结构的分类 338
FL1.2迭代器类 339
FL1.3容器类 343
FL1.4容器适配器类 349
FL1.5标准模板类里的通用函数 349
思考题 351
附录2数据结构考研真题解析 352
FL2.1 2009年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题 352
FL2.2 2010年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题 355
结语：数据结构之弦 359
参考文献 362