具体描述
《数据结构、算法与应用——C++语言描述》是享有盛誉的数据结构教科书的第2版。它完整地包含了基本数据结构的内容，是CS2课程的理想用书。作者Sartaj Sahni通过循循善诱的讲解、直观具体的讨论和基于现实的应用，让读者轻松、愉快地学习。新版书着重利用标准模板库(STL)，把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。
书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例，涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起，使理论与实践统一，从而让概念容易理解，使学生增加学习动力和兴趣。
本书采用的实用教学方法，不仅充实了理论概念，而且大量的习题让学生有了实践机会（书中有800多道练习题，包括理解题和简单的编程题和工程设计题）。除此之外，本书的配套网站上包含书中的所有程序、示例数据、运行结果、部分练习的解答和带有结果的示例测试。
作者简介
Sartaj Sahni在 Cronell大学获得硕士和博士学位。曾任教于明尼苏达大学。目前是佛罗里达大学计逄机与信息科学工程系主任。Sahni教授在数据结构与算法领域的研究和教学方面享有世界声誉，因此当选为IEEE和ACM两会会士以及欧洲科学院院士，并获得IEEE计算机学会的Taylor L.Booth教育奖和W.Wallace-MCDowell奖，2003年更荣获计算机教育最高荣誉ACM Karl V.Karlstrom杰出教育家奖。
目录信息
译者序
前言
第一部分 预备知识
第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 操作符new 9
1.4.2 一维数组 9
1.4.3 异常处理 9
1.4.4 操作符delete 10
1.4.5 二维数组 10
1.5 自有数据类型 12
1.5.1 类currency 12
1.5.2 一种不同的描述方法 18
1.5.3 操作符重载 20
1.5.4 友元和保护性类成员 22
1.5.5 增加#ifndef、#define和#endif语句 23
1.6 异常类illegalParameterValue 24
1.7 递归函数 25
1.7.1 递归的数学函数 25
1.7.2 归纳 25
1.7.3 C++递归函数 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 抽象数据类型linearList 94
5.2.2 抽象类linearList 94
5.3 数组描述 95
5.3.1 描述 95
5.3.2 变长一维数组 96
5.3.3 类arrayList 97
5.3.4 C++迭代器 102
5.3.5 arrayList的一个迭代器 103
5.4 vector的描述 107
5.5 在一个数组中实现的多重表 109
5.6 性能测量 111
5.7 参考及推荐读物 112
第6章 线性表——链式描述 113
6.1 单向链表 113
6.1.1 描述 113
6.1.2 结构chainNode 114
6.1.3 类chain 115
6.1.4 抽象数据类型linearList的扩充 121
6.1.5 类extendedChain 121
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.2 C++数组的索引 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 类matrix 152
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 类arrayStack 179
8.3.3 性能测量 181
8.4 链表描述 182
8.4.1 类derivedLinkedStack 182
8.4.2 类linkedStack 183
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 类arrayQueue 209
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 结构skipNode 242
10.4.5 类skipList 242
10.4.6 skipList方法的复杂度 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.1 LZW压缩 260
10.6.2 LZW压缩的实现 261
10.6.3 LZW解压缩 264
10.6.4 LZW解压缩的实现 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 抽象数据类型BinaryTree 281
11.8 类linkedBinaryTree 282
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 类maxHeap 302
12.4.6 堆和STL 305
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 类maxHblt 310
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 抽象数据类型WinnerTree 326
13.3 赢者树的实现 327
13.3.1 表示 327
13.3.2 赢者树的初始化 328
13.3.3 重新组织比赛 328
13.3.4 类completeWinnerTree 328
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 类binarySearchTree 341
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.1 AVL树 360
15.1.1 定义 360
15.1.2 AVL树的高度 361
15.1.3 AVL树的描述 361
15.1.4 AVL搜索树的搜索 361
15.1.5 AVL搜索树的插入 361
15.1.6 AVL搜索树的删除 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.4 B-树 379
15.4.1 索引顺序访问方法 379
15.4.2 m叉搜索树 380
15.4.3 m阶B-树 381
15.4.4 B-树的高度 382
15.4.5 B-树的搜索 382
15.4.6 B-树的插入 382
15.4.7 B-树的删除 384
15.4.8 节点结构 387
15.5 参考及推荐读物 389
第16章 图 390
16.1 基本概念 390
16.2 应用和更多的概念 391
16.3 特性 394
16.4 抽象数据类型graph 395
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.2 0/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.1 0/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.2 0/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.2 0/1背包问题 535
21.2.3 最大完备子图 536
21.2.4 旅行商问题 538
21.2.5 电路板排列 541
· · · · · · (收起)
读后感
第一部分讲了一些c++的语法，但只是写给学过c++的人看的，比较粗略，简单讲解了本书用到的c++语法，另外性能分析性能测量和渐进记法也花了三个章节的篇幅，讲的比较全面。第二部分的数据结构讲的很全面:线性表，矩阵，栈，队列，跳表，哈希，二叉树，优先级队列，堆，左高树，...
评分讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一...
评分讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一...
评分讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一个错误，我看了一整晚上没看懂，最后把代码敲到我的编译器里，发现果然是错的。日了狗。讲的还行吧，但是345页应该是有一...
评分第一部分讲了一些c++的语法，但只是写给学过c++的人看的，比较粗略，简单讲解了本书用到的c++语法，另外性能分析性能测量和渐进记法也花了三个章节的篇幅，讲的比较全面。第二部分的数据结构讲的很全面:线性表，矩阵，栈，队列，跳表，哈希，二叉树，优先级队列，堆，左高树，...
用户评价
作为一名长期与后端系统打交道的工程师，我发现这本书对“工程实践”的思考也潜移默化地影响了我。它不仅停留在理论层面，很多地方会穿插一些关于内存分配、缓存局部性（Locality of Reference）对算法实际运行时间的影响的讨论。这让我意识到，算法的性能，在真实的硬件环境下，受到的因素远比理论上的 O(N log N) 复杂得多。我尤其欣赏作者对于各种搜索和排序算法的复杂度分析，不仅仅是给出了大 O 标记，还详细探讨了常数因子和算法的稳定性的问题。这种深层次的探讨，让我对“快速排序”这种看似简单的算法，也有了更立体、更成熟的认识。这本书的配图，虽然不是那种花哨的 3D 渲染，但其简洁、精确的流程图和状态图，却能瞬间捕捉到算法的核心运行轨迹，比看一长串代码要有效得多。总而言之，它是一本能提升你对计算本质理解深度的书，读完后，你会不自觉地用更优化的眼光去审视自己写的每一行代码。
评分这本书的装帧和纸张质量给我一种久违的“学术感”，那种厚实的纸张，即便是用荧光笔涂抹标记，墨水也不会洇开，这对于需要反复研读的经典教材来说至关重要。我最看重的部分是它在讨论高级数据结构时所展现的清晰度。拿B树和B+树的章节来说，作者是如何从数据库索引的需求出发，一步步推导出 B 树结构特性的，这个“因果链条”被梳理得极其顺畅，让人感觉这些结构的发明并非偶然，而是解决特定工程问题的必然产物。这种历史和需求的结合，极大地提升了学习的兴趣。另外，书中对各种数据结构在不同场景下的适用性的对比分析，简直是教科书级别的总结。比如，它会清晰地指出在需要频繁删除和插入的场景下，平衡二叉树相对于简单二叉搜索树的巨大优势，并且会用图示展示树的自平衡过程。对于渴望在软件设计中做出明智技术选型的读者，这本书提供的决策依据是无可替代的，它教会你的不是“怎么写”，而是“为什么这么写”。
评分这本书简直是自学数据结构与算法的“圣经”！我拿到实体书的时候就被它厚实的质感震撼到了，感觉手里沉甸甸的，就知道内容肯定够扎实。我之前看过一些网络上的免费教程，东拼西凑的，很多概念总是似懂非懂，尤其是在涉及到复杂算法的推导和证明时，完全跟不上节奏。但这本书不同，它把每一个基础概念，比如链表、栈、队列这些，都讲得非常透彻，配上清晰的图示，简直是手把手教学。最让我印象深刻的是它对递归和分治思想的阐述，作者没有直接丢给你一个复杂的代码实现，而是先从问题的本质入手，一步步引导你去思考如何分解问题，如何设计递归的出口条件。读完关于树和图的部分，我感觉脑子里那些原本盘踞已久的困惑都烟消云散了。这本书的排版也值得称赞，代码块和文字的间距恰到好处，即便是长时间阅读也不会让人感到眼睛疲劳。对于想要系统性掌握计算机核心基础，准备面试，或者想在算法竞赛中有所突破的读者来说，这绝对是一笔超值的投资，它为你打下的基础，比任何速成秘籍都要来得牢靠得多。
评分说实话，这本书的阅读体验，对于我这种已经工作几年，但想重新拾起理论基础的工程师来说，是一种非常愉快的“复古”体验。它不像现在市面上很多新书那样，上来就紧盯着 Python 或 Java 的最新特性猛推，而是采用了更偏向于概念和逻辑描述的方式，这使得它的生命力非常长久。我特别欣赏作者处理复杂算法时的那种严谨态度，比如动态规划的章节，它没有急于给出最优解的代码，而是花了大量篇幅去解释“状态转移方程”是如何构建起来的。这让我明白了，算法不仅仅是记住一套模板，更重要的是理解它背后的数学逻辑和优化思想。我记得我曾经为了一道 LIS（最长递增子序列）问题绞尽脑汁，但在书中看到作者用表格化的方式清晰展示了每一步的状态更新，那种豁然开朗的感觉简直是无法言喻。虽然书中的例子可能看起来稍微传统了一些，但正是这些经典案例，才真正考验你对底层原理的掌握程度。如果你只是想应付面试中那几个高频考点，这本书可能有点“重火力”，但如果你目标是成为一个能够自己设计高效算法的架构师，那么这本书的深度和广度是无可替代的。
评分这本书的书页手感有点像早些年那种精装的技术手册，装订得非常结实，翻阅起来很有信心，不用担心随便翻几下书脊就裂开了。内容方面，它的章节组织逻辑性极强，是那种典型的“自底向上”的教学结构。我最喜欢的地方是它在介绍完抽象数据类型（ADT）之后，紧接着就会用好几种不同的底层实现方式来对比优劣，比如用数组和用链表实现栈在性能上的微妙差异，这种对比分析能力是很多教材所欠缺的。我记得有一次我在处理一个性能瓶颈问题时，就是回翻到关于堆排序的那一章，重新审视了它在最坏情况下的时间复杂度，这才找到了改进方向。这本书的习题设计也很有巧思，它不像有些教科书那样，习题只是对概念的简单重复，而是设置了一些需要结合多个知识点才能解决的综合题，非常考验读者的融会贯通能力。当然，如果说有什么美中不足，可能对于纯粹的初学者来说，一开始接触可能会觉得信息密度稍大，需要沉下心来慢慢啃，但回报绝对是巨大的，它提供的是一套坚不可摧的知识体系。
评分代码风格很奇怪，有待深究。每次实验作业要做4天，翻遍技术博客debug“洗稿”才完善出符合要求的，琢磨最轻便的算法来构造解构真是门艺术。王老师很风趣，助教很友好，转CS的前途一片光明（自我暗示不能停）。
评分不知道是否是翻译问题，总觉得读起来流畅度很低。代码很详细。想学习算法还是推荐《算法导论》《算法》，这本书对比起来差距还是比较大
评分书不错，就是有些错误
评分书不错，就是有些错误
评分正在读，补充了很多缺漏的细节与知识点，面试笔试必看
