数据结构与算法经典问题解析

出版者:机械工业出版社

作者:纳拉辛哈·卡鲁曼希

页数:443

译者:骆嘉伟

出版时间:2016-6-1

价格:CNY 79.00

装帧:平装

isbn号码:9787111538455

具体描述

本书是一本数据结构方面的优秀教材，以Java为描述语言，介绍了计算机编程中使用的数据结构和算法。本书强调问题及其分析，而非理论阐述，共分为21章，讲述了基本概念、递归和回溯、链表、栈、队列、树、优先队列和堆、并查集DAT、图算法、排序、查找、选择算法（中位数）、符号表、散列、字符串算法、算法设计技术、贪婪算法、分治算法、动态规划算法、复杂度类型等内容。每章首先阐述必要的理论基础，然后给出问题集。全书中大约有700个算法问题及相应的解法，对于许多问题，本书提供了多个具有不同复杂度的解决方法。

本书可作为高等院校计算机及其相关专业的数据结构课程的教材或教学参考书，同时也可以作为从事计算机研究与开发的技术人员的参考书，特别是对正在准备面试、参加选拔性考试以及校园面试的读者尤为有用。

作者简介

作者:(印)纳拉辛哈·卡鲁曼希 译者:骆嘉伟 译者:李晓鸿 译者:肖正 译者:吴帆

纳拉辛哈·卡鲁曼希，在尼赫鲁科技大学获得计算机科学学士学位，在印度理工学院孟买分校获得计算机科学硕士学位。他是亚马逊印度公司资深的软件开发工程师，之前曾就职于IBM和微软公司。他善于用轻松、浅显的方式编写技术书籍，其作品在亚马逊上深受好评。他曾在各种培训中心和大学教授数据结构和算法课程。

目录信息

译者序
前言
第1章绪论1
1.1变量1
1.2数据类型1
1.3数据结构2
1.4抽象数据类型2
1.5什么是算法3
1.6为什么需要算法分析3
1.7算法分析的目的3
1.8什么是运行时间分析4
1.9如何比较算法4
1.10什么是增长率4
1.11常用的增长率4
1.12分析的类型5
1.13渐近表示6
1.14大O表示法6
1.15Ω表示法7
1.16Θ表示法8
1.17重要说明9
1.18为什么称为渐近分析9
1.19渐近分析指南9
1.20渐近表示法的性质11
1.21常用的对数和累加公式11
1.22分治法主定理12
1.23分治法主定理的相关问题12
1.24问题规模减小和递归求解主定理13
1.25问题规模减小和递归求解主定理的变型13
1.26猜测和确认的方法14
1.27平摊分析15
1.28算法分析的相关问题15
第2章递归和回溯28
2.1引言28
2.2什么是递归28
2.3为什么要用递归28
2.4递归函数的格式28
2.5递归和内存（可视化）29
2.6递归与迭代30
2.7递归说明30
2.8递归算法的经典用例30
2.9递归的相关问题31
2.10什么是回溯32
2.11回溯算法的经典用例32
2.12回溯的相关问题32
第3章链表34
3.1什么是链表34
3.2链表抽象数据类型34
3.3为什么要用链表35
3.4数组概述35
3.5链表、数组和动态数组的比较36
3.6单向链表36
3.7双向链表41
3.8循环链表46
3.9一种存储高效的双向链表51
3.10松散链表52
3.11链表的相关问题55
第4章栈72
4.1什么是栈72
4.2如何使用栈72
4.3栈抽象数据类型73
4.4异常73
4.5应用73
4.6实现73
4.7栈的各种实现方法比较77
4.8栈的相关问题78
第5章队列98
5.1什么是队列98
5.2如何使用队列98
5.3队列抽象数据类型99
5.4异常99
5.5应用99
5.6实现99
5.7队列的相关问题104
第6章树110
6.1什么是树110
6.2术语110
6.3二叉树111
6.4二叉树的遍历114
6.5通用树（N叉树）135
6.6线索（无栈或无队列结构）二叉树遍历141
6.7表达式树147
6.8异或树149
6.9二叉搜索树150
6.10平衡二叉搜索树164
6.11AVL树165
6.12树的其他形式178
6.12.1红黑树178
6.12.2伸展树179
6.12.3增强树179
6.12.4替罪羊树179
6.12.5区间树180
第7章优先队列和堆181
7.1什么是优先队列181
7.2优先队列ADT181
7.3优先队列的应用182
7.4优先队列的实现182
7.5堆和二叉堆183
7.6二叉堆184
7.7优先队列（堆）的相关问题190
第8章并查集ADT201
8.1引言201
8.2等价关系和等价类201
8.3并查集ADT202
8.4应用202
8.5并查集ADT实现中的权衡202
8.6快速UNION实现（慢FIND）203
8.7快速UNION实现（快速FIND）206
8.8路径压缩208
8.9小结209
8.10并查集的相关问题209
第9章图算法211
9.1引言211
9.2术语211
9.3图的应用214
9.4图的表示214
9.5图的遍历217
9.6拓扑排序225
9.7最短路径算法226
9.8最小生成树231
9.9图算法的相关问题235
第10章排序256
10.1什么是排序256
10.2为什么需要排序256
10.3排序的分类256
10.4其他分类方法257
10.5冒泡排序257
10.6选择排序258
10.7插入排序259
10.8希尔排序261
10.9归并排序262
10.10堆排序264
10.11快速排序264
10.12树排序266
10.13排序算法比较267
10.14线性排序算法267
10.15计数排序267
10.16桶排序268
10.17基数排序268
10.18拓扑排序269
10.19外部排序269
10.20排序的相关问题270
第11章查找279
11.1什么是查找279
11.2为什么需要查找279
11.3查找的类型279
11.4符号表和散列281
11.5字符串查找算法281
11.6查找的相关问题281
第12章选择算法(中位数)304
12.1什么是选择算法304
12.2基于排序的选择算法304
12.3基于划分的选择算法304
12.4线性选择算法——中位数的中位数算法305
12.5按照排序顺序查找K个最小元素305
12.6选择算法的相关问题305
第13章符号表314
13.1引言314
13.2什么是符号表314
13.3符号表的实现315
13.4符号表实现方法的比较315
第14章散列317
14.1什么是散列317
14.2为什么用散列317
14.3散列表ADT317
14.4散列的例子317
14.5散列的组成部分319
14.6散列表319
14.7散列函数319
14.8负载因子320
14.9冲突320
14.10冲突解决技术320
14.11分离链接法320
14.12开放定址法321
14.13冲突解决技术的比较322
14.14散列如何达到O(1)的时间复杂度322
14.15散列技术323
14.16不适用散列表的问题323
14.17布鲁姆过滤器323
14.18散列的相关问题325
第15章字符串算法335
15.1引言335
15.2字符串匹配算法335
15.3蛮力法336
15.4RobinKarp字符串匹配算法336
15.5基于有限自动机的字符串匹配算法337
15.6KMP算法338
15.7BoyceMoore算法342
15.8存储字符串的数据结构342
15.9字符串的散列表实现342
15.10字符串的二叉搜索树实现343
15.11键树343
15.12三叉搜索树345
15.13二叉搜索树、键树和三叉搜索树的比较349
15.14后缀树349
15.15字符串的相关问题353
第16章算法设计技术361
16.1引言361
16.2分类361
16.3按实现方法分类361
16.4按设计方法分类362
16.5其他分类法363
第17章贪婪算法364
17.1引言364
17.2贪婪策略的定义364
17.3贪婪算法的要素364
17.4贪婪算法的适用范围365
17.5贪婪算法的优缺点365
17.6贪婪算法的应用365
17.7贪婪思想365
17.8贪婪算法的相关问题368
第18章分治算法375
18.1引言375
18.2分治策略的定义375
18.3分治法的适用范围375
18.4分治法的图形化描述375
18.5分治思想376
18.6主定理377
18.7分治法的应用377
18.8分治法的相关问题378
第19章动态规划算法390
19.1引言390
19.2动态规划策略的定义390
19.3动态规划策略的性质390
19.4动态规划的适用范围390
19.5动态规划的实现方法391
19.6动态规划算法的例子391
19.7动态规划思想391
19.8动态规划的相关问题396
第20章复杂度类型425
20.1引言425
20.2多项式/指数时间425
20.3决策问题的定义426
20.4决策过程426
20.5复杂度类型的定义426
20.6复杂度类型426
20.7归约428
20.8复杂度类型的相关问题430
第21章杂谈433
21.1引言433
21.2位运算的使用433
21.2.1按位与操作433
21.2.2按位或操作434
21.2.3按位异或操作434
21.2.4按位左移操作434
21.2.5按位右移操作434
21.2.6按位补操作434
21.2.7检测第K位是否置位434
21.2.8第K位置位435
21.2.9第K位清零435
21.2.10切换第K位435
21.2.11切换值为1的最右位435
21.2.12隔离值为1的最右位435
21.2.13隔离值为0的最右位435
21.2.14检查某个数是否是2的幂436
21.2.15将某个数乘以2的幂436
21.2.16将某个数除以2的幂436
21.2.17找到给定操作数的模436
21.2.18反转二进制数436
21.2.19位值1的计数436
21.2.20创建末尾位为0的掩码437
21.2.21交换奇偶位438
21.2.22不使用除法来计算平均数438
21.3其他编程问题438
参考文献442
· · · · · · (收起)

用户评价

这次有幸拜读了《数据结构与算法经典问题解析》，虽然我原本对这方面了解不多，但这本书简直就是为我量身定制的！首先，我必须说，作者的叙事风格非常引人入胜。他不是那种枯燥乏味的理论灌输，而是像讲故事一样，把一个个抽象的数据结构和算法概念变得生动有趣。我特别喜欢他开篇就举出的几个贴近生活的例子，比如用链表来模拟排队买票，用栈来处理浏览器的“前进”和“后退”功能。这些例子一下子就消除了我对“高深莫测”的算法的恐惧感，让我觉得原来这些东西就在我们身边，并且在解决实际问题。 更让我惊叹的是，书中对每一个经典问题的解析都做得非常透彻。它不会仅仅给出解决方案，而是深入剖析问题的根源，讲解不同方法的优劣，以及在什么情况下选择哪种方法最优。我记得有一章讲解的是图的遍历，作者不仅详细解释了DFS和BFS的原理，还通过一个迷宫寻路的例子，让这两种算法的实现过程一目了然。最关键的是，他还在每个问题的后面，拓展了一些变种和延伸，这对于想要深入学习的读者来说，简直是宝藏。我感觉自己像是在跟着一位经验丰富的老侦探，一步步解开难题，不仅学到了知识，更培养了解决问题的思维方式。 而且，《数据结构与算法经典问题解析》这本书在排版和配图上也做得非常用心。每一个算法的伪代码都清晰易懂，关键步骤都用醒目的颜色标注出来。我尤其喜欢那些由作者亲手绘制的示意图，它们用简洁的线条勾勒出数据结构的变化过程，以及算法的执行流程，大大降低了我的理解难度。很多时候，一张图胜过千言万语。我之前看过的其他一些教材，虽然内容也很好，但往往因为缺乏直观的图示，让我看得云里雾里。这本书在这方面做得非常出色，真正做到了“可视化”教学。 另外，这本书在语言的使用上也非常考究。作者的遣词造句既严谨又不失幽默。我没有感觉到任何学术上的枯燥和生硬，反而像是在和一位博学的老师进行一次轻松愉快的对话。他对每一个概念的解释都力求精确，但又不会使用过多晦涩难懂的术语。即使是一些非常复杂的算法，在他笔下也变得相对容易理解。我记得有一次，我卡在一个动态规划的问题上很久，翻看了这本书，作者用一个非常生动的例子，将问题的状态转移方程解释得明明白白，我立刻就豁然开朗了。 总而言之，《数据结构与算法经典问题解析》是一本我非常推荐的书籍。它不仅适合初学者入门，对于有一定基础的读者，也能从中获得新的启发。它教会我的不仅仅是具体的算法知识，更重要的是一种严谨的逻辑思维和解决问题的策略。我个人认为，这本书的价值远超其售价，它为我的学习之路打开了一扇新的大门，让我对计算机科学有了更深的理解和更浓厚的兴趣。我将会把它作为我未来学习数据结构与算法的常备参考书。

这是一本让我从“看懂”到“悟透”的里程碑式读物。我一直认为，数据结构与算法是计算机科学的基石，但过去的学习经历总是让我觉得隔靴搔痒。直到翻阅《数据结构与算法经典问题解析》，我才真正找到了那种“茅塞顿开”的感觉。作者似乎能够洞察到读者在学习过程中的每一个难点和疑惑，然后用最精妙的方式一一化解。 我非常欣赏书中对于每一个算法“适用场景”的详细分析。它不会简单地说“这个算法好”，而是会深入剖析它在不同数据规模、不同数据分布下的表现，以及它与其他算法的权衡。例如，在讲解哈希表时，作者并没有止步于介绍其O(1)的平均查找时间，而是详细讨论了哈希冲突的发生原因、以及各种解决冲突的方法，并分析了它们对性能的影响。这种深入的剖析，让我能够做出更明智的选择，避免在实际应用中踩坑。 书中对“递归”和“分治”等抽象概念的解释，更是让我印象深刻。作者并没有直接给出一个复杂的递归函数，而是从一个简单的问题入手，一步步地引导读者去理解递归的本质，以及如何将其转化为迭代。我记得在讲解斐波那契数列的递归解法时，作者不仅展示了其简洁性，更重要的是，他还详细分析了其重复计算的问题，然后自然而然地引出了动态规划的优化思路。这种“承上启下”的讲解方式，让知识的学习过程变得非常流畅和连贯。 更值得称赞的是，这本书在案例的选择上非常有代表性。它涵盖了那些在面试中经常出现，同时在实际开发中也极为重要的经典问题。例如，字符串匹配、最短路径、图的遍历等等。作者不仅仅是给出解决方案，更是通过对这些问题的深入剖析，让读者理解这些算法背后的思想和通用性，从而能够触类旁通，解决更多类似的问题。 总而言之，《数据结构与算法经典问题解析》是我近几年来读过的最令人满意的一本技术书籍。它不仅仅是一本知识的传授者，更像是一位经验丰富的导师，引导我深入理解数据结构与算法的本质，培养我解决问题的能力。我强烈推荐这本书给所有想要深入学习数据结构与算法的读者，它一定会给你带来意想不到的收获。

作为一名在编程道路上摸索了几年的人，我一直觉得自己对数据结构和算法的理解有些停留在表面。直到读到《数据结构与算法经典问题解析》，我才真正体会到“精髓”二字。这本书最让我印象深刻的是，它没有使用那种僵硬的、按部就班的教学模式，而是以一种非常灵活和富有洞察力的方式，去剖析每一个“经典问题”。作者仿佛是一位经验丰富的医生，能够准确地诊断出问题的“病灶”，然后给出最精准的“药方”。 我特别欣赏书中对于每一个算法的“动机”和“演进”的探讨。作者不会直接跳到最终的解决方案，而是会先描述一个问题的原始状态，然后一步步地去探索可能存在的不足，再引出改进的思路，最终形成一个相对完善的算法。这种“追根溯源”的讲解方式，让我对算法的产生和发展有了更深刻的认识。我记得在讲到链表和数组的区别时，作者并没有简单地罗列两者的优缺点，而是通过一个频繁插入和删除元素的场景，让读者直观地感受到使用数组可能带来的性能瓶颈，从而引出链表的优势。 而且，书中对每一个算法的“可视化”处理也非常出色。作者不仅仅是提供了文字描述和代码实现，更重要的是，他利用大量的图示来辅助理解。这些图示非常巧妙，能够清晰地展示出数据结构的变化过程，以及算法在不同阶段的状态。我经常会在阅读代码的同时，对照图示进行理解，感觉自己就像是在观看一场生动的数据流动的动画片。这极大地减轻了我的学习负担，也让抽象的概念变得触手可及。 更重要的是，《数据结构与算法经典问题解析》在语言的运用上，展现了一种独特的魅力。它既有严谨的学术性，又不失轻松的阅读体验。作者善于运用类比和比喻，将复杂的概念用通俗易懂的语言表达出来。我没有感觉到任何“劝退”的生涩感，反而有一种循循善诱的引导。即使是像递归、分治这样的概念，在作者的笔下也变得清晰明了，让我能够真正理解其背后的逻辑。 总而言之，这是一本让我醍醐灌顶的书。它不仅仅是传授知识，更是培养我的逻辑思维能力和解决问题的能力。我从中学到的，远不止是数据结构和算法本身，更是一种对计算机科学的深刻理解和热爱。这本书对我而言，是一次非常有价值的投资，它为我未来的学习和职业发展奠定了坚实的基础。

这本《数据结构与算法经典问题解析》给我的最大感受就是“通透”。作者似乎有一种神奇的能力，能够将那些曾经让我头疼不已的复杂概念，一一化解，变得清晰明了。我之前看过的很多书籍，往往停留在“知其然”，而这本书则让我做到了“知其所以然”。它不仅仅是告诉你怎么做，更是告诉你为什么这么做，以及这样做的好处和潜在的弊端。 我尤其喜欢书中对于“时间效率”和“空间效率”的深入探讨。作者不仅仅是给出了一个Big O的符号，而是用非常直观的方式，去解释这个符号背后的含义。比如，在讲解冒泡排序时，他会形象地描述，当数据量增大时，冒泡排序会变得多么“缓慢”，然后通过与快速排序的对比，让读者深刻理解不同算法在效率上的巨大差异。这种对“效率”的深刻理解，让我开始审视自己过去的一些粗糙的代码实现。 书中的每一个“经典问题”都被作者拆解得非常细致。它不像一些书籍那样，直接丢给你一个问题然后给出一个标准答案。而是会引导你一步步地去思考，去尝试，去发现问题的症结所在。这种“循循善诱”的教学方式，让我感觉自己更像是在参与一个智力挑战，而不是被动地学习。我记得在讲解动态规划的背包问题时，作者并没有直接给出递推公式，而是通过一个生活中的例子，层层递进地引导出状态的定义和转移方程，这个过程让我记忆犹新。 而且，这本书的语言风格也非常独特。它既有技术书籍应有的严谨性，又不失趣味性。作者的笔触非常生动，读起来一点也不枯燥。他善于运用各种生动的比喻，将抽象的算法概念变得形象化。我尤其喜欢他的一些“俏皮话”，在不影响严肃讨论的前提下，为阅读增添了不少乐趣。这种将学术与人文相结合的风格，是许多技术书籍所缺乏的。 总而言之，《数据结构与算法经典问题解析》是一本真正能够提升个人技术内涵的书籍。它不仅仅教会了我数据结构和算法的知识，更重要的是，它教会了我如何去思考，如何去分析问题，以及如何去设计出更加优雅、高效的解决方案。我感觉自己在这本书的帮助下，对编程的理解又上升了一个层次，对未来的学习充满了信心。

这是一本让我重新认识“学习”这件事的书。以往我学习技术类书籍，总会感到一种机械式的输入，大量的名词、公式堆砌，然后是机械式的记忆和套用。但《数据结构与算法经典问题解析》完全颠覆了我的这种体验。作者似乎非常懂得如何激发读者的好奇心，他会将每一个算法的出现都置于一个具体的、有挑战性的问题背景之下。比如，在介绍二分查找时，他没有直接讲“折半查找”，而是先抛出一个“在有序的字典里快速找到一个单词”的场景，然后引导读者去思考如何才能最高效地完成这个任务。 这种“问题驱动”的学习方式，让我感到非常投入。我不再是被动地接受知识，而是主动地去思考，去猜测，去寻找答案。书中的每一个章节都仿佛是一个精心设计的迷宫，而算法就是解锁迷宫的钥匙。作者会一步步地引导我们，从简单的尝试到更精妙的设计，最终揭示出最优解的诞生过程。我特别欣赏他在讲解贪心算法时，没有直接给出“局部最优推导全局最优”的结论，而是通过一系列的活动选择问题，让我们亲身感受到为什么有些情况下贪心策略是有效的，以及它的局限性在哪里。 这本书的另一个亮点在于其内容的深度和广度。它并没有止步于讲解最基础的几个数据结构和算法，而是深入探讨了许多在实际工程中非常常见的变体和应用。例如，在讲解排序算法时，作者不仅详细分析了冒泡、选择、插入等基础排序，还对快速排序、归并排序等分治思想的应用进行了深入剖析，并特别强调了它们在时间复杂度和稳定性上的差异。甚至还涉及到了堆排序和基数排序这些相对进阶的算法。这种由浅入深、由易到难的编排方式，让我在掌握基础的同时，也能够窥探到更广阔的算法世界。 值得一提的是，作者在文中对每一个算法的“时间复杂度”和“空间复杂度”的分析都非常到位。他不仅仅是给出一个Big O表示法，而是会用非常形象的比喻来解释它的含义。比如，他会用“随着输入规模的增长，算法执行时间的增长速度有多快”来比喻时间复杂度，用“算法运行时占用的内存空间有多大”来比喻空间复杂度。这种接地气的讲解，让我这个对数学符号不太敏感的读者，也能够深刻理解算法的效率问题，并学会如何根据实际需求来权衡和选择合适的算法。 总而言之，《数据结构与算法经典问题解析》为我打开了一扇通往算法世界的大门，它不仅仅是一本教材，更像是一位循循善诱的导师。它教会了我如何去思考，如何去分析问题，以及如何去设计高效的解决方案。我从中获得的，不仅仅是知识，更是一种宝贵的学习方法和解决问题的能力。我已经迫不及待地想将书中的知识应用到我的实际项目中，去解决更复杂、更有趣的问题。

看理论会觉得晦涩难懂，直接看这个学的快。理论介绍的非常简短，然后用代码展示如何使用，用代码说话。里面的例题很有代表性，学习了可以开发智力，对面试也有好处。

我觉得对于应付面试来说还是值得一看的，写的很有条理性，很多经典的面试问题这里面都会用循序渐进的方式进行讲解。但是我必须指出，这本书存在着大量代码错误，我看了书籍的原版后发现错误不是翻译的锅，而是原版就存在这样的问题。所以请读者务必擦亮眼睛。

真的很不错

写得真的很不错，如果想看算法和数据相关的知识，推荐这本书。

看理论会觉得晦涩难懂，直接看这个学的快。理论介绍的非常简短，然后用代码展示如何使用，用代码说话。里面的例题很有代表性，学习了可以开发智力，对面试也有好处。