第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
· · · · · · (
收起)
0 有用 CarboNado 2017-05-17 21:51:58
好书，而且不厚