数据结构、算法与应用:C++语言描述(原书第2版)

本书共分三个部分。第一部分从第1章到第4章，旨在复习C++程序设计的概念以及程序性能的分析和测量方法。第二部分从第5章到第16章，研究数据结构，包括线性表、数组和矩阵、栈、队列、字典、二叉树、优先级队列、竞赛树、搜索树和图等。第三部分从第17章到第21章，研究常用算法，包括贪婪算法、分而治之算法、动态规划、回溯算法和分枝定界算法。本书有800多道练习题和50多个应用实例。内容广博，组织合理，论述清晰，循序渐进，而且对程序性能的分析和测量系统入微。本书不仅是数据结构和算法的经典教材，而且是计算机科学与工程领域的理想参考书。

萨特吉·萨尼Sartaj Sahni，佛罗里达大学计算机与信息科学工程系杰出教授，欧洲科学院院士，美国电气和电子工程师协会（IEEE）、美国计算机协会（ACM）、美国科学促进会（AAAS）和明尼苏达超级计算机研究所的成员，坎普尔印度理工学院（ lIT）的杰出校友。Sahni博士获得1997年IEEE计算机分会的Taylor L.Booth教育奖，2003年IEEE计算机分会的W.Wallace McDowell奖和2003年ACM的Karl Karlstrom杰出教育家奖。他目前还担任ACM《Computing Surveys》期刊的总编辑，还是17个期刊编委会成员。他在坎普尔印度理工学院获得电子工程学士学位，在康奈尔大学获得计算机科学硕士和博士学位，发表过250多篇论文，编写了15本教科书，研究成果所涉及的领域包括有效算法的设计与分析、并行计算、互联网、自动化设计和医用算法。

出版者的话
译者序
前言
第一部分预备知识
第1章C++回顾2
1.1引言2
1.2函数与参数3
1.2.1传值参数3
1.2.2模板函数4
1.2.3引用参数4
1.2.4常量引用参数5
1.2.5返回值5
1.2.6重载函数6
1.3异常7
1.3.1抛出异常7
1.3.2处理异常7
1.4动态存储空间分配9
1.4.1操作符new9
1.4.2一维数组9
1.4.3异常处理9
1.4.4操作符delete10
1.4.5二维数组10
1.5自有数据类型12
1.5.1类currency12
1.5.2一种不同的描述方法18
1.5.3操作符重载20
1.5.4友元和保护性类成员22
1.5.5增加#ifndef、#define和#endif语句23
1.6异常类illegalParameterValue24
1.7递归函数25
1.7.1递归的数学函数25
1.7.2归纳25
1.7.3C++递归函数26
1.8标准模板库30
1.9测试与调试32
1.9.1什么是测试32
1.9.2测试数据的设计34
1.9.3调试36
1.10参考及推荐读物37
第2章程序性能分析38
2.1什么是程序性能38
2.2空间复杂度39
2.2.1空间复杂度的组成39
2.2.2举例42
2.3时间复杂度44
2.3.1时间复杂度的组成44
2.3.2操作计数45
2.3.3最好、最坏和平均操作计数48
2.3.4步数53
第3章渐近记法64
3.1引言64
3.2渐近记法65
3.2.1大Ο记法65
3.2.2渐近记法Ω和Θ67
3.3渐近数学（可选）69
3.3.1大O记法69
3.3.2Ω记法71
3.3.3Θ记法72
3.3.4小ο记法73
3.3.5特性73
3.4复杂度分析举例75
3.5实际复杂度78
3.6参考及推荐读物80
第4章性能测量81
4.1引言81
4.2选择实例的大小82
4.3设计测试数据82
4.4实验设计82
4.5高速缓存87
4.5.1简单计算机模型87
4.5.2缓存未命中对运行时间的影响87
4.5.3矩阵乘法88
4.6参考及推荐读物90
第二部分数据结构
第5章线性表——数组描述92
5.1数据对象和数据结构92
5.2线性表数据结构93
5.2.1抽象数据类型linearList94
5.2.2抽象类linearList94
5.3数组描述95
5.3.1描述95
5.3.2变长一维数组96
5.3.3类arrayList97
5.3.4C++迭代器102
5.3.5arrayList的一个迭代器103
5.4vector的描述107
5.5在一个数组中实现的多重表109
5.6性能测量111
5.7参考及推荐读物112
第6章线性表——链式描述113
6.1单向链表113
6.1.1描述113
6.1.2结构chainNode114
6.1.3类chain115
6.1.4抽象数据类型linearList的扩充121
6.1.5类extendedChain121
6.1.6性能测量122
6.2循环链表和头节点126
6.3双向链表128
6.4链表用到的词汇表129
6.5应用130
6.5.1箱子排序130
6.5.2基数排序134
6.5.3凸包135
6.5.4并查集137
第7章数组和矩阵146
7.1数组146
7.1.1抽象数据类型146
7.1.2C++数组的索引147
7.1.3行主映射和列主映射147
7.1.4用数组的数组来描述148
7.1.5行主描述和列主描述149
7.1.6不规则二维数组149
7.2矩阵151
7.2.1定义和操作151
7.2.2类matrix152
7.3特殊矩阵157
7.3.1定义和应用157
7.3.2对角矩阵158
7.3.3三对角矩阵159
7.3.4三角矩阵160
7.3.5对称矩阵161
7.4稀疏矩阵164
7.4.1基本概念164
7.4.2用单个线性表描述165
7.4.3用多个线性表描述170
7.4.4性能测量172
第8章栈175
8.1定义和应用175
8.2抽象数据类型177
8.3数组描述178
8.3.1作为一个派生类实现178
8.3.2类arrayStack179
8.3.3性能测量181
8.4链表描述182
8.4.1类derivedLinkedStack182
8.4.2类linkedStack183
8.4.3性能测量184
8.5应用184
8.5.1括号匹配184
8.5.2汉诺塔185
8.5.3列车车厢重排187
8.5.4开关盒布线191
8.5.5离线等价类问题193
8.5.6迷宫老鼠196
8.6参考及推荐读物204
第9章队列205
9.1定义和应用205
9.2抽象数据类型206
9.3数组描述207
9.3.1描述207
9.3.2类arrayQueue209
9.4链表描述212
9.5应用214
9.5.1列车车厢重排214
9.5.2电路布线217
9.5.3图元识别219
9.5.4工厂仿真222
9.6参考及推荐读物234
第10章跳表和散列235
10.1字典235
10.2抽象数据类型236
10.3线性表描述237
10.4跳表表示（可选）239
10.4.1理想情况239
10.4.2插入和删除241
10.4.3级的分配241
10.4.4结构skipNode242
10.4.5类skipList242
10.4.6skipList方法的复杂度246
10.5散列表描述246
10.5.1理想散列246
10.5.2散列函数和散列表248
10.5.3线性探查250
10.5.4链式散列255
10.6一个应用——文本压缩260
10.6.1LZW压缩260
10.6.2LZW压缩的实现261
10.6.3LZW解压缩264
10.6.4LZW解压缩的实现265
10.6.5性能评价268
10.7参考及推荐读物269
第11章二叉树和其他树270
11.1树270
11.2二叉树273
11.3二叉树的特性274
11.4二叉树的描述275
11.4.1数组描述275
11.4.2链表描述276
11.5二叉树常用操作277
11.6二叉树遍历277
11.7抽象数据类型BinaryTree281
11.8类linkedBinaryTree282
11.9应用285
11.9.1设置信号放大器285
11.9.2并查集288
11.10参考及推荐读物296
第12章优先级队列297
12.1定义和应用297
12.2抽象数据类型298
12.3线性表299
12.4堆299
12.4.1定义299
12.4.2大根堆的插入300
12.4.3大根堆的删除301
12.4.4大根堆的初始化301
12.4.5类maxHeap302
12.4.6堆和STL305
12.5左高树306
12.5.1高度优先与宽度优先的最大及最小左高树306
12.5.2最大HBLT的插入308
12.5.3最大HBLT的删除308
12.5.4两棵最大HBLT的合并308
12.5.5初始化309
12.5.6类maxHblt310
12.6应用313
12.6.1堆排序313
12.6.2机器调度314
12.6.3霍夫曼编码317
12.7参考及推荐读物322
第13章竞赛树323
13.1赢者树和应用323
13.2抽象数据类型WinnerTree326
13.3赢者树的实现327
13.3.1表示327
13.3.2赢者树的初始化328
13.3.3重新组织比赛328
13.3.4类completeWinnerTree328
13.4输者树329
13.5应用331
13.5.1用最先适配法求解箱子装载问题331
13.5.2用相邻适配法求解箱子装载问题335
13.6参考及推荐读物337
第14章搜索树338
14.1定义338
14.1.1二叉搜索树338
14.1.2索引二叉搜索树340
14.2抽象数据类型340
14.3二叉搜索树的操作和实现341
14.3.1类binarySearchTree341
14.3.2搜索342
14.3.3插入342
14.3.4删除343
14.3.5二叉搜索树的高度346
14.4带有相同关键字元素的二叉搜索树347
14.5索引二叉搜索树348
14.6应用349
14.6.1直方图349
14.6.2箱子装载问题的最优匹配法351
14.6.3交叉分布353
第15章平衡搜索树359
15.1AVL树360
15.1.1定义360
15.1.2AVL树的高度361
15.1.3AVL树的描述361
15.1.4AVL搜索树的搜索361
15.1.5AVL搜索树的插入361
15.1.6AVL搜索树的删除364
15.2红-黑树367
15.2.1基本概念367
15.2.2红-黑树的描述368
15.2.3红-黑树的搜索368
15.2.4红-黑树的插入368
15.2.5红-黑树的删除371
15.2.6实现细节的考虑及复杂性分析374
15.3分裂树376
15.3.1介绍376
15.3.2分裂树的操作376
15.3.3折算复杂性378
15.4B-树379
15.4.1索引顺序访问方法379
15.4.2m叉搜索树380
15.4.3m阶B-树381
15.4.4B-树的高度382
15.4.5B-树的搜索382
15.4.6B-树的插入382
15.4.7B-树的删除384
15.4.8节点结构387
15.5参考及推荐读物389
第16章图390
16.1基本概念390
16.2应用和更多的概念391
16.3特性394
16.4抽象数据类型graph395
16.5无权图的描述396
16.5.1邻接矩阵396
16.5.2邻接链表397
16.5.3邻接数组398
16.6加权图的描述400
16.7类实现400
16.7.1不同的类400
16.7.2邻接矩阵类401
16.7.3扩充chain类405
16.7.4链表类405
16.8图的遍历407
16.8.1广度优先搜索407
16.8.2广度优先搜索的实现408
16.8.3方法graph::bfs的复杂性分析409
16.8.4深度优先搜索410
16.8.5深度优先搜索的实现411
16.8.6方法graph::dfs的复杂性分析412
16.9应用412
16.9.1寻找一条路径412
16.9.2连通图及其构成414
16.9.3生成树415
第三部分算法设计方法
第17章贪婪算法420
17.1最优化问题420
17.2贪婪算法思想421
17.3应用424
17.3.1货箱装载424
17.3.20/1背包问题425
17.3.3拓扑排序427
17.3.4二分覆盖430
17.3.5单源最短路径433
17.3.6最小成本生成树436
17.4参考及推荐读物445
第18章分而治之446
18.1算法思想446
18.2应用453
18.2.1残缺棋盘453
18.2.2归并排序455
18.2.3快速排序459
18.2.4选择464
18.2.5相距最近的点对466
18.3解递归方程474
18.4复杂度的下限475
18.4.1最小最大问题的下限476
18.4.2排序算法的下限477
第19章动态规划479
19.1算法思想479
19.2应用481
19.2.10/1背包问题481
19.2.2矩阵乘法链484
19.2.3所有顶点对之间的最短路径489
19.2.4带有负值的单源最短路径492
19.2.5网组的无交叉子集496
19.3参考及推荐读物501
第20章回溯法502
20.1算法思想502
20.2应用506
20.2.1货箱装载506
20.2.20/1背包问题512
20.2.3最大完备子图515
20.2.4旅行商问题517
20.2.5电路板排列519
第21章分支定界525
21.1算法思想525
21.2应用528
21.2.1货箱装载528
21.2.20/1背包问题535
21.2.3最大完备子图536
21.2.4旅行商问题538
21.2.5电路板排列541