《数据结构（C++语言版）》是2012年清华大学出版社出版的图书，作者是邓俊辉。
基本介绍
- 书名：数据结构（C++语言版）
- 作者：邓俊辉
- ISBN：9787302268833
- 定价：39
- 出版社：清华大学出版社
- 出版时间：2012-2-3
- 装帧：平装
内容简介
本书按照面向对象程式设计的思想，根据作者多年的教学积累，系统介绍各类数据结构的功能、表示和实现，对比各类数据结构适用的套用环境；结合实际问题展示算法设计的一般性模式与方法、算法实现的主流技巧，以及算法效率的评判依据和分析方法；以高度概括的体例为线索贯穿全书，并通过对比和类比揭示数据结构与算法的内在联繫，帮助读者形成整体性认识。
书中穿插大量验证型、拓展型和反思型习题，以激发读者的求知慾，培养自学能力和独立思考习惯；近300幅插图结合简练的叙述，200多段代码配合详尽而简洁的注释，使深奥抽象的概念和过程得以具体化并便于理解和记忆。
图书目录
第1章 绪论 1
§1.1计算机与算法 2
1.1.1古埃及人的绳索 2
1.1.2欧几里德的尺规 3
1.1.3起泡排序 4
1.1.4算法 5
1.1.5算法效率 8
§1.2複杂度度量 8
1.2.1问题规模、运行时间及时间
複杂度 9
1.2.2渐进複杂度 9
1.2.3空间複杂度 11
§1.3複杂度分析 12
1.3.1常数複杂度O(1) 12
1.3.2对数複杂度O(logn) 13
1.3.3线性複杂度O(n) 14
1.3.4多项式複杂度O(polynomial(n)) 15
1.3.5指数複杂度O(2n) 15
1.3.6複杂度层次 16
1.3.7输入规模 16
§1.4*递归 17
1.4.1线性递归 17
1.4.2递归分析 18
1.4.3递归模式 20
1.4.4递归消除 22
1.4.5二分递归 24
§1.5抽象数据类型 27
习题 28
第2章 向量 31
§2.1从数组到向量 32
2.1.1数组 32
2.1.2向量 32
§2.2接口 33
2.2.1ADT接口 33
2.2.2操作实例 34
2.2.3Vector模板类 34
§2.3构造与析构 36
2.3.1默认构造方法 36
2.3.2基于複製的构造方法 36
2.3.3析构方法 37
§2.4动态空间管理 37
2.4.1静态空间管理 37
2.4.2可扩充向量 38
2.4.3扩容 38
2.4.4分摊分析 39
2.4.5缩容 40
§2.5向量 41
2.5.1直接引用元素 41
2.5.2置乱器 41
2.5.3判等器与比较器 42
2.5.4无序查找 43
2.5.5插入 44
2.5.6删除 45
2.5.7唯一化 46
2.5.8遍历 47
§2.6有序向量 49
2.6.1比较器 49
2.6.2有序性甄别 49
2.6.3唯一化 49
2.6.4查找 52
2.6.5二分查找（版本A） 53
2.6.6Fibonacci查找 56
2.6.7二分查找（版本B） 59
2.6.8二分查找（版本C） 60
§2.7*排序与下界 61
2.7.1有序性 61
2.7.2排序及其分类 62
2.7.3下界 62
2.7.4比较树 63
2.7.5估计下界 64
§2.8排序器 64
2.8.1统一入口 64
2.8.2起泡排序 65
2.8.3归併排序 66
习题 69
第3章 列表 73
§3.1从向量到列表 74
3.1.1从静态存储到动态存储 74
3.1.2由秩到位置 75
3.1.3列表 75
§3.2接口 75
3.2.1列表节点 75
3.2.2列表 76
§3.3列表 79
3.3.1头、尾节点 79
3.3.2默认构造方法 79
3.3.3由秩到位置的转换 80
3.3.4查找 80
3.3.5插入 81
3.3.6基于複製的构造 83
3.3.7删除 84
3.3.8析构 85
3.3.9唯一化 86
3.3.10遍历 86
§3.4有序列表 87
3.4.1唯一化 87
3.4.2查找 88
§3.5排序器 88
3.5.1统一入口 88
3.5.2插入排序 89
3.5.3选择排序 91
3.5.4归併排序 92
习题 94
第4章 栈与伫列 97
§4.1栈 98
4.1.1概述 98
4.1.2ADT接口 99
4.1.3操作实例 99
4.1.4Stack模板类 99
§4.2栈与递归 100
4.2.1递归的实现 101
4.2.2避免递归 102
§4.3典型套用 103
4.3.1逆序输出 103
4.3.2递归嵌套 105
4.3.3延迟缓冲 108
4.3.4逆波兰表达式 113
§4.4*试探回溯法 116
4.4.1试探与回溯 116
4.4.2八皇后 117
4.4.3迷宫寻径 119
§4.5伫列 122
4.5.1概述 122
4.5.2ADT接口 122
4.5.3操作实例 123
4.5.4Queue模板类 124
§4.6伫列套用 124
4.6.1循环分配器 124
4.6.2银行服务模拟 125
习题 126
第5章 二叉树 129
§5.1二叉树及其表示 130
5.1.1树 130
5.1.2二叉树 131
5.1.3多叉树 132
§5.2编码树 134
5.2.1二进制编码 134
5.2.2二叉编码树 136
§5.3二叉树的实现 137
5.3.1二叉树节点 137
5.3.2二叉树节点操作接口 140
5.3.3二叉树 141
§5.4Huffman编码 146
5.4.1PFC编码 146
5.4.2最优编码树 149
5.4.3Huffman编码树 152
5.4.4Huffman编码算法 154
§5.5遍历 160
5.5.1递归式遍历 161
5.5.2叠代版先序遍历 163
5.5.3叠代版中序遍历 165
5.5.4叠代版后序遍历 169
5.5.5层次遍历 171
习题 172
第6章 图 175
§6.1概述 176
§6.2抽象数据类型 179
6.2.1操作接口 179
6.2.2Graph模板类 180
§6.3邻接矩阵 181
6.3.1原理 181
6.3.2实现 182
6.3.3时间性能 184
6.3.4空间性能 184
§6.4邻接表 184
6.4.1原理 184
6.4.2複杂度 184
§6.5图遍历算法概述 185
§6.6广度优先搜寻 186
6.6.1策略 186
6.6.2实现 186
6.6.3实例 187
6.6.4複杂度 187
6.6.5套用 188
§6.7深度优先搜寻 188
6.7.1策略 188
6.7.2实现 189
6.7.3实例 190
6.7.4複杂度 191
6.7.5套用 192
§6.8拓扑排序 192
6.8.1套用 192
6.8.2有向无环图 193
6.8.3算法 193
6.8.4实现 193
6.8.5实例 194
6.8.6複杂度 194
§6.9*双连通域分解 195
6.9.1关节点与双连通域 195
6.9.2蛮力算法 195
6.9.3算法 196
6.9.4实现 196
6.9.5实例 198
6.9.6複杂度 199
§6.10优先权搜寻 199
6.10.1优先权与优先权数 199
6.10.2基本框架 200
6.10.3複杂度 201
§6.11最小支撑树 201
6.11.1支撑树 201
6.11.2最小支撑树 201
6.11.3歧义性 201
6.11.4蛮力算法 202
6.11.5Prim算法 202
§6.12最短路径 204
6.12.1最短路径树 204
6.12.2歧义性 205
6.12.3Dijkstra算法 205
习题 208
第7章 搜寻树 211
§7.1搜寻 212
7.1.1循关键码访问 212
7.1.2词条 213
7.1.3序与比较器 213
§7.2二叉搜寻树 213
7.2.1顺序性 213
7.2.2中序遍历序列 214
7.2.3BST模板类 214
7.2.4查找算法及其实现 215
7.2.5插入算法及其实现 217
7.2.6删除算法及其实现 218
§7.3平衡二叉搜寻树 220
7.3.1树高与性能 220
7.3.2理想平衡与适度平衡 221
7.3.3等价二叉搜寻树 222
7.3.4等价变换与局部调整 222
§7.4AVL树 223
7.4.1AVL树 223
7.4.2节点插入 225
7.4.3节点删除 228
7.4.4统一重平衡算法 230
习题 232
第8章 高级搜寻树 235
§8.1伸展树 236
8.1.1局部性 236
8.1.2逐层伸展 237
8.1.3双层伸展 238
8.1.4分摊分析 240
8.1.5伸展树的实现 243
§8.2B-树 247
8.2.1多路平衡搜寻 247
8.2.2ADT接口及其实现 249
8.2.3关键码查找 251
8.2.4性能分析 252
8.2.5关键码插入 253
8.2.6上溢与分裂 254
8.2.7关键码删除 257
8.2.8下溢与合併 258
§8.3*红黑树 263
8.3.1概述 263
8.3.2红黑树接口定义 265
8.3.3节点插入算法 266
8.3.4节点删除算法 269
§8.4*kd-树 275
8.4.1範围查询 275
8.4.2kd-树 278
8.4.3基于2d-树的範围查询算法 279
习题 280
第9章 词典 283
§9.1词典 284
9.1.1操作接口 284
9.1.2操作实例 285
9.1.3接口定义 286
9.1.4判等器 286
9.1.5实现方法 287
§9.2*跳转表 287
9.2.1Skiplist模板类 287
9.2.2总体逻辑结构 288
9.2.3四联表 288
9.2.4查找 290
9.2.5空间複杂度 292
9.2.6时间複杂度 292
9.2.7插入 293
9.2.8删除 296
§9.3散列表 298
9.3.1完美散列 298
9.3.2装填因子与空间利用率 299
9.3.3散列函式 300
9.3.4散列表 303
9.3.5冲突及其排解 305
9.3.6开放定址策略 307
9.3.7查找与删除 309
9.3.8插入 310
9.3.9更多开放定址策略 312
9.3.10散列码转换 314
§9.4*散列套用 316
9.4.1桶排序 316
9.4.2最大间隙 317
9.4.3基数排序 318
习题 319
第10章 优先权伫列 323
§10.1优先权伫列 324
10.1.1优先权与优先权伫列 324
10.1.2关键码、比较器与偏序关係 325
10.1.3操作接口 325
10.1.4操作实例：选择排序 325
10.1.5接口定义 326
10.1.6套用实例：Huffman编码树 326
§10.2堆 328
10.2.1完全二叉堆 329
10.2.2元素插入 331
10.2.3元素删除 333
10.2.4建堆 335
10.2.5就地堆排序 338
§10.3*左式堆 341
10.3.1堆合併 341
10.3.2单侧倾斜 341
10.3.3PQ_LeftHeap模板类 342
10.3.4空节点路径长度 342
10.3.5左倾性与左式堆 343
10.3.6右侧链 343
10.3.7合併算法 344
10.3.8合併操作merge()的实现 344
10.3.9实例 345
10.3.10複杂度 345
10.3.11基于合併的插入和删除操作 346
习题 347
第11章 串 349
§11.1串及串匹配 350
11.1.1串 350
11.1.2串匹配 351
11.1.3测评标準与策略 352
§11.2蛮力算法 353
11.2.1算法描述 353
11.2.2算法实现 353
11.2.3时间複杂度 354
§11.3KMP算法 355
11.3.1构思 355
11.3.2next表 356
11.3.3KMP算法 357
11.3.4next[0]=-1 357
11.3.5构造next表 358
11.3.6性能分析 358
11.3.7继续改进 359
§11.4*BM算法 361
11.4.1思路与框架 361
11.4.2坏字元策略 362
11.4.3好后缀策略 364
11.4.4综合性能 368
§11.5*Karp-Rabin算法 369
11.5.1构思 369
11.5.2算法与实现 370
习题 373
第12章 排序 375
§12.1快速排序 376
12.1.1分治策略 376
12.1.2轴点 376
12.1.3快速排序算法 377
12.1.4快速划分算法 377
12.1.5複杂度 379
12.1.6应对退化 381
§12.2*选取与中位数 382
12.2.1概述 382
12.2.2主流数 383
12.2.3归併向量的中位数 385
12.2.4基于优先权伫列的选取 388
12.2.5基于快速划分的选取 389
12.2.6k-选取算法 390
§12.3*希尔排序 392
12.3.1递减增量策略 392
12.3.2增量序列 394
习题 397
附录 399
插图索引 400
表格索引 406
算法索引 407
代码索引 408
关键字索引 414