本书以Java为描述语言，介绍了数据结构与算法的基本知识。书中结合企业界的工程实践提炼教学内容，特别对数据结构中易混淆的问题进行了梳理，对每一个问题提出不同的解决方案。本书是一本优秀的数据结构方面的教材。

本书既是一本优秀的数据结构和算法方面的自学教材，也是正在准备面试、参加选拔性考试以及校园面试的读者的应试指南。全书以Java为描述语言，介绍计算机编程中使用的数据结构和算法，强调问题及其分析，而非理论阐述。
全书共分为21章，分别讲述了基本概念、递归和回溯、简单排序、链表、栈、队列、树、优先队列和堆、并查集DAT、图算法、排序、查找、选择算法（中位数）、符号表、散列、字符串算法、算法设计技术、贪婪算法、分治算法、动态规划算法、复杂度类型等内容。每章首先阐述必要的理论基础，然后给出问题集。书中大约有700个算法问题及相应的解法。对于许多问题，本书提供了多个具有不同复杂度的解决方法。从蛮力法开始，逐步引入问题的最佳解决方法。对于每一个问题，试图知晓算法所需的运行时间和内存空间。注重启发式教学和实际编程能力的培养。
本书由曾供职于多家知名IT企业的资深软件架构师撰写，以Java为描述语言，介绍计算机编程中使用的数据结构和算法，覆盖相应竞争性考试的主题，目的不是提供关于数据结构和算法的定理及证明，而是强调问题及其分析，讲解必备知识和解题技巧。针对不同问题，列举多个具有不同复杂度的解决方法，汇集知名IT企业经典的编程面试题目并给出解题思路，为学生应试和软件开发人员面试提供有益指导。
本书特点：
所有代码用Java实现。
数据结构难点启发思考。
为每个问题列举可能的解决办法。
基于不同复杂度提供多种巧妙的解决方法。
覆盖所有竞争性考试的主题。
囊括数据结构和算法的面试问题。
可作为大学本科生或硕士研究生课程的预习教材。
可为IT顶尖公司（微软、谷歌、亚马逊、雅虎、甲骨文、脸谱、苹果等）的求职者提供指导。
在尼赫鲁科技大学获得计算机科学学士学位，在印度理工学院孟买分校获得计算机科学硕士学位。他是亚马逊印度公司资深的软件开发工程师，之前曾就职于IBM和微软公司。他善于用轻松、浅显的方式编写技术书籍，其作品在亚马逊上深受好评。他曾在各种培训中心和大学教授数据结构和算法。

我知道许多读者往往不读前言，但是强烈建议你至少浏览一下本书前言，因为本书前言与众不同。
本书的主要目的不是提供关于数据结构和算法的定理及证明。本书采用的模式是利用不同的复杂度改善问题的解（对于每个问题，你将发现多个具有不同复杂度及降低复杂度的解法）。基本上，这一思路就是列举某个问题的所有可能解。通过这种方式，即使你遇到一个新问题,它也能够向你指明如何思考该问题所有可能的解。本书对于正在准备面试、参加选拔性考试以及校园面试的读者很有帮助。
作为一个求职者，如果你能完整地阅读本书并且很好地领会书中的内容，相信你会从容地面对面试官，这正是本书的目的所在。若作为一个教师来阅读本书，你将能够用简单的方法来提升授课质量，学生也会为选择攻读计算机科学/信息技术学位而感到欣慰。
作为准备参加计算机科学/信息技术专业选拔考试的学生，本书完整而详细地涵盖了所有必需的主题，在撰写本书时，就着眼于帮助正在准备这些考试的学生。
本书对攻读工程学位的学生和研究生都非常有用。在所有的章节中，你会发现本书更强调问题及其分析，而不是理论的阐述。每一章将首先阐述必要的理论基础，然后再给出问题集。书中大约有700个算法问题及相应的解。
对于许多问题，本书提供了多个具有不同复杂度的解决方法。我们从蛮力法开始，逐步引入问题的最佳解决方法。对于每一个问题，我们试图知晓算法所需的运行时间和内存空间。
建议读者至少完整地阅读本书一遍以便充分理解所有的主题。在随后的阅读中，你可以直接选择任何一章阅读和参考。即便经过足够的校阅，书中出现小纰漏也在所难免。如果发现了任何此类错误，wwwCarrerMonkcom网站将予以更新，请经常关注本网站以便及时了解任何勘误、新问题和解决方法。此外，请提供宝贵建议至Info@CarrerMonkcom。
祝愿你一切顺利。我相信你会发现本书很有用。
致谢
感谢我的父母，他们为我所做的一切无法衡量，是他们给予的无私的爱、提供的安定的成长环境和坚持不懈的传统价值观，教会了我赞美和拥抱生活。他们是这世界上最好的父母和榜样，他们使我明白信念、勤奋和决心能够让任何事成为可能！
本书的撰写得到了许多人的帮助，没有他们的帮助本书不可能完成。感谢他们为改进本书终稿所做出的努力。需要说明的是，我已经尽最大努力纠正了审稿人所指出的错误并准确地对各种协议和机制进行了描述。我个人对书中出现的任何其他错误负责。
首先，感谢那些在本书撰写过程中陪我度过难关的人，感谢所有给予我支持的人，感谢所有参与讨论、阅读、编写和提出宝贵意见的人，感谢所有允许我引用他们的评论并协助我编辑、校对和设计本书的人。特别地，我要感谢如下人员：
●Mohan Mullapudi,印度理工学院孟买分校，架构师,dataRPM PvtLtd
●Navin Kumar Jaiswal,资深咨询师,Juniper Networks Inc
●Kishore Kumar Jinka,印度理工学院孟买分校
●AVamshi Krishna,印度理工学院坎普尔分校,Mentor Graphics Inc
●Hirak Chatterjee,Yahoo Inc
●Kondrakunta Murali Krishna,科技学士,技术主管,HCL
●Chaganti Siva Rama Krishna Prasad,创始人,StockMonks PvtLtd
●Naveen Valsakumar,联合创始人,NotionPress PvtLtd
●Ramanaiah,讲师,龙树科技学院,MLG
最后，感谢Guntur Vikas学院主任YVGopala Krishna Murthy教授、Ayub Khan教授（ACE工程学院）、TRCBose（APTransco前任主任）、ChVenkateswara Rao VNR Vignanajyothi（工程学院,Hyderabad）、ChVenkata Narasaiah（IPS）、Yarapathineni Lakshmaiah （Manchikallu,Gurazala） ，以及所有在本项目期间帮助过我和家人的所有好心人。

——Narasimha Karumanchi
印度理工学院孟买分校理科硕士
CareerMonk.com创始人

计算机\数据结构

本书由曾供职于多家知名IT企业的资深软件架构师撰写，以Java为描述语言，介绍计算机编程中使用的数据结构和算法，覆盖相应竞争性考试的主题，目的不是提供关于数据结构和算法的定理及证明，而是强调问题及其分析，讲解必备知识和解题技巧。针对不同问题，列举多个具有不同复杂度的解决方法，汇集知名IT企业经典的编程面试题目并给出解题思路，为学生应试和软件开发人员面试提供有益指导。

本书主要特点：
　 所有代码用Java实现。
　 数据结构难点启发思考。
　 为每个问题列举可能的解决办法。
　 基于不同复杂度提供多种巧妙的解决方法。
　 覆盖所有竞争性考试的主题。
　 囊括数据结构和算法的面试问题。
　 可作为相关工作人员的参考手册。
　 作为大学本科生或硕士研究生课程的预习教材。
　 可为IT顶尖公司（微软、谷歌、亚马逊、雅虎、甲骨文、脸谱、苹果等）的求职者提供指导。

[印]纳拉辛哈·卡鲁曼希(Narasimha Karumanchi) 著：纳拉辛哈•卡鲁曼希（Narasimha Karumanchi）在尼赫鲁科技大学获得计算机科学科技学士学位，在印度理工学院孟买分校获得计算机科学科技硕士学位。他是亚马逊印度公司资深的软件开发工程师，之前曾就职于IBM和微软公司。他善于用轻松、浅显的方式编写技术书籍，出版了多部著作，其作品在亚马逊上深受好评，目前已被翻译为中文、韩文和日文等。他在各种培训中心和大学教授过数据结构和算法。

骆嘉伟 李晓鸿 肖正 吴帆 等译：暂无简介

数据结构是计算机科学与技术专业非常重要的一门核心基础课，计算机科学各个领域及各种应用软件都要使用相关的数据结构和算法。
作者编著本书的目的是使读者知晓数据结构和算法的设计原理和实现，而并非单纯地讲述定理及证明。为此，本书利用不同的复杂度来改善问题的解。对于许多问题，从穷举解法开始，逐步引入问题的最佳解，并给出算法所需的运行时间和空间。
全书包含4个部分，第一部分（第1~2章）主要描述抽象数据类型，给出算法的基本概念和复杂度分析与评价方法，并讨论几乎每章都要用到的递归和回溯技术。第二部分（第3~9章）介绍基本数据结构，包括链表、栈、队列、树、优先队列、堆、并查集和图，对于每一种数据结构分别采用多个实例进行具体的演示。第三部分（第10~15章）介绍数据处理的技术，包括排序、查找、选择、符号表、散列和字符串算法。第四部分（第16~21章）重点介绍一些常用的算法设计技术及应用，包括贪婪算法、分治算法、动态规划算法、复杂度类型，并讨论对于面试和考试的一些有用话题。本书强调问题及分析，而不侧重于理论。本书可作为高等院校计算机及其相关专业的数据结构课程的教材或教学参考书，同时也可以作为从事计算机研究与开发的技术人员的参考书，特别是对正在准备面试、参加选拔性考试以及校园面试的读者尤为有用。
本书的前言、第9～13章由骆嘉伟翻译，第2～5章、第15章由李晓鸿翻译，第16～21章由肖正翻译，第1章、第6～8章由吴帆翻译，第14章由朱宁波翻译。此外，梁成、夏艳、罗洪、张天伍、杨亦、齐逸也参与了部分翻译工作。
尽管我们从事数据结构和算法的教学和科研工作多年，在翻译过程中本着认真负责、力求精准的精神，但错误难免，希望广大读者批评指正。

译者
2015年12月于长沙

译者序
前言
第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