本书以简明易懂的方式介绍了数据结构与算法的基本知识，内容全面、系统。描述方式基于C/C++语言，对数据结构中容易混淆的问题进行了透彻的阐述，对每一个问题均给出了不同的解决方案。涵盖入职面试中常见的数据结构与算法方面的问题，既可以作为数据结构课程的教材，也可以作为研究生考试的参考以及程序员的参考手册。
涵盖世界知名IT公司技术面试的程序设计问题及其解题思路
针对不同问题提供不同复杂度的解决方法，兼顾自学教材和面试辅导的不同需求
我知道很多人不会阅读前言。但我强烈建议你至少浏览一遍本书的前言，因为你会发现一些与众不同的东西。
本书不是展示数据结构和算法的定理和证明，而是另辟蹊径，通过改进不同复杂度问题的解决方案来讲解数据结构和算法的相关内容（对于每一个问题，都有复杂度由大到小的多种解决方案）。这些方法基本上涵盖了所有可能的问题解决之道。这种讲解模式可以让你在遇到新问题时，获得思考所有可能解决方案的思维方式。本书也可以让你在准备面试、考试和升学面试时收益良多。
作为一名求职者，如果透彻理解了本书的内容，那么在面对面试官时将会从容不迫，甚至感到绰绰有余。作为一名教师，如果通读了本书，我相信你自然会提升教学质量，最终会让你的学生对选择了计算机科学/信息技术专业而感到庆幸。
对工程专业的本科生和研究生来说，本书在他们的学术准备中非常有用。本书每章都把重点放在问题和对问题的分析上，而不是单纯的理论。每章都是先介绍必需的基础理论，然后是问题集。本书大约有700个算法问题，并且给出了解决方法。
如果你是一名正在为参加计算机科学/信息技术竞赛考试做准备的学生，你会发现这本书涵盖了你所需要的所有主题，并且给出了详细的阐述。在写这本书的时候，我的关注点就已经放在了帮助参加这些考试的学生上。
对许多问题，本书给出了多种不同复杂度级别的解决方案。我们以蛮力法解决方案开始，慢慢地向可能的最优方案靠近。对每个问题，我们将设法弄清楚算法花费的时间和占用的内存空间。
本书建议的阅读方式是，先至少通读一遍以获得对所有主题的全面了解，随后读者可以按需跳到感兴趣的章节。尽管我们做了足够多的校验，书中难免还会存在一些不足。我们将在www.careerMonk.com网站上更新发现的任何错误。请读者关注该网站，后续任何错误修正、新问题和解决方案都会在该网站上更新。此外，请将你的宝贵意见发到下面的邮箱：Info@CareerMonk.com。
献上最美好的祝福。我相信你会发现此书物有所值。
Narasimha Karumanchi
计算机\数据结构
数据结构和算法是计算机科学的核心内容之一，是计算机专业学生的重要专业课程，对培养计算机专业设计与创新型人才起着关键作用。它具有概念多、内容广、抽象性强、需要的数学基础多等特点，学习难度较大。
本书由曾供职于多家知名IT企业的资深软件架构师撰写，是面向数据结构和算法初学者的入门书籍。全书介绍计算机编程中使用的数据结构和算法，覆盖相应入学考试和企业面试的主题，目的不是提供关于数据结构和算法的定理及证明，而是强调问题及其分析，讲解必备知识和解题技巧。针对不同问题，列举多个具有不同复杂度的解决方法，汇集知名IT企业经典的编程面试题目并给出解题思路，可作为大学本科生数据结构与算法课程的参考教材，也可为学生应试和软件开发人员求职面试提供有益指导。
主要特点：
语言通俗、内容实用，和现实中的问题紧密相连，并且没有使用非常复杂的数学知识，非常适合数据结构和算法的初学者。
为每个经典的应用问题给出基于不同数据结构的多种算法的求解方案，让读者充分了解和感受相同问题的不同算法在时间开销、空间开销和编程难度上的不同。
提供丰富的题目及解析，每一章都有包含大量习题的问题集，针对每个问题，都结合本章知识点或综合本章和其他章节的知识点给出分析和求解方案。
涵盖各大IT公司面试中涉及的数据结构和算法题目，覆盖所有常见主题，帮助学生准备各类笔试和面试。
作者简介：
纳拉辛哈·卡鲁曼希（Narasimha Karumanchi） CareerMonk创始人，亚马逊印度公司资深软件开发工程师，之前曾就职于IBM和微软公司。他是数据结构、算法及设计方面的畅销书作家，善于用轻松、浅显的方式编写技术书籍，其作品在亚马逊上深受好评，翻译为中文、韩文和日文等。
[印度]纳拉辛哈·卡鲁曼希（Narasimha Karumanchi）著：纳拉辛哈•卡鲁曼希（Narasimha Karumanchi）在尼赫鲁科技大学获得计算机科学科技学士学位，在印度理工学院孟买分校获得计算机科学科技硕士学位。他是亚马逊印度公司资深的软件开发工程师，之前曾就职于IBM和微软公司。他善于用轻松、浅显的方式编写技术书籍，出版了多部著作，其作品在亚马逊上深受好评，目前已被翻译为中文、韩文和日文等。他在各种培训中心和大学教授过数据结构和算法。
数据结构和算法是计算机科学的核心内容之一， 是计算机专业学生的重要专业课程，对培养计算机专业设计与创新型人才起着关键作用。它具有概念多、内容广、抽象性强、需要一定的数学基础等特点，学习难度较大，对刚刚开始学习的学生来说更是如此。
在翻译Narasimha Karumanchi博士撰写的这本数据结构和算法入门书的过程中，我们发现该书有以下特点：
第一，语言通俗，与现实中的问题紧密相连，并且没有使用非常复杂的数学知识，非常适合数据结构和算法的初学者。
第二，对于经典的应用问题，常常给出基于不同数据结构的多种算法的求解方案，让读者充分了解和感受相同问题的不同算法在时间开销、空间开销和编程难度上的不同。
第三，习题丰富。本书的每一章都有包含大量习题的问题集，其中的每道题，作者均结合本章知识点或综合本章和其他章的知识点给出了分析和求解方案。
非常有幸得到机械工业出版社的信任参与了该书的翻译工作。由于水平有限，译文中表达不准确之处在所难免，还请业内专家和广大读者包涵，在此也敬请各位专家、学者和读者批评指正。欢迎各位读者将发现的错误或提出的任何意见和建议发送到邮箱nancy78733@126.com。
最后，我要感谢湖北工业大学数据安全与隐私保护技术研究所、湖北工业大学工业大数据协同创新中心的诸位同事、同学的建议和帮助。在翻译过程中，张明武教授提出了很多有益的意见，在此表示诚挚的感谢。非常感谢机械工业出版社朱劼编辑对我的包容、理解、帮助和支持，也非常感谢机械工业出版社其他工作人员的辛勤付出。
沈 华
2018年3月于武汉南湖
译者序
前言
第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 什么是运行时间分析3
1.9 如何比较算法4
1.10 什么是增长率4
1.11 常用的增长率4
1.12 算法分析的类型5
1.13 渐近符号5
1.14 O符号6
1.15 Ω符号7
1.16 Θ符号8
1.17 为什么称为渐近分析9
1.18 渐近分析的准则9
1.19 渐近符号的性质11
1.20 常用的对数公式和求和公式11
1.21 分治法的主定理11
1.22 与分治法主定理相关的问题12
1.23 减治递推的主定理13
1.24 减治主定理的另一种形式13
1.25 猜测与确认的方法13
1.26 平摊分析15
1.27 关于算法分析的问题集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章 链表35
3.1 什么是链表35
3.2 链表的抽象数据类型35
3.3 为什么需要链表35
3.4 数组回顾35
3.5 链表与数组、动态数组的比较37
3.6 单链表37
3.7 双链表43
3.8 循环链表48
3.9 一种存储高效的双链表54
3.10 松散链表55
3.11 跳表61
3.12 关于链表的问题集64
第4章 栈87
4.1 什么是栈87
4.2 如何使用栈87
4.3 栈的抽象数据类型87
4.4 栈的应用88
4.5 栈的实现88
4.6 栈实现的比较94
4.7 关于栈的问题集94
第5章 队列114
5.1 什么是队列114
5.2 如何使用队列114
5.3 队列的抽象数据类型114
5.4 操作异常115
5.5 队列的应用115
5.6 队列的实现115
5.7 关于队列的问题集121
第6章 树127
6.1 什么是树127
6.2 相关术语127
6.3 二叉树128
6.4 几种特殊的二叉树128
6.5 二叉树的性质129
6.6 二叉树的遍历131
6.7 一般的树(N叉树)153
6.8 线索二叉树的遍历(与栈/队列无关的遍历)159
6.9 表达树166
6.10 XOR树168
6.11 二叉搜索树169
6.12 平衡二叉搜索树184
6.13 AVL树184
6.14 其他形式的树200
第7章 优先队列和堆204
7.1 什么是优先队列204
7.2 优先队列的抽象数据类型204
7.3 优先队列的应用205
7.4 优先队列的实现205
7.5 堆和二项堆206
7.6 二项堆207
7.7 堆排序213
7.8 关于优先队列(堆)的问题集214
第8章 不相交集226
8.1 引言226
8.2 等价关系和等价类226
8.3 不相交集的抽象数据类型227
8.4 不相交集的应用227
8.5 不相交集实现的折中方案227
8.6 快速查找Fast FIND的实现(Quick FIND)227
8.7 快速合并Fast UNION的实现(Quick UNION)228
8.8 快速合并Fast UNION的实现(Slow FIND)228
8.9 快速合并Fast UNION的实现(Quick FIND)231
8.10 小结234
8.11 关于不相交集的问题集234
第9章 图算法235
9.1 引言235
9.2 相关术语235
9.3 图的应用238
9.4 图的表示238
9.5 图的遍历242
9.6 拓扑排序249
9.7 最短路径算法250
9.8 最小生成树256
9.9 关于图算法的问题集259
第10章 排序280
10.1 什么是排序280
10.2 为什么需要排序280
10.3 排序算法的分类280
10.4 其他分类方式281
10.5 冒泡排序281
10.6 选择排序282
10.7 插入排序283
10.8 希尔排序285
10.9 归并排序287
10.10 堆排序289
10.11 快速排序289
10.12 树排序292
10.13 排序算法的比较292
10.14 线性排序算法292
10.15 计数排序293
10.16 桶排序(或箱排序)293
10.17 基数排序294
10.18 拓扑排序295
10.19 外部排序295
10.20 关于排序的问题集296
第11章 搜索306
11.1 什么是搜索306
11.2 为什么需要搜索306
11.3 搜索的类型306
11.4 无序线性搜索306
11.5 排序/有序线性搜索307
11.6 二分搜索307
11.7 基本搜索算法的比较308
11.8 符号表和散列308
11.9 字符串搜索算法308
11.10 关于搜索的问题集308
第12章 选择算法(中位数)333
12.1 什么是选择算法333
12.2 基于排序的选择333
12.3 基于划分的选择算法333
12.4 线性选择算法——Median of Median算法333
12.5 按序寻找第k小元素333
12.6 关于选择算法的问题集334
第13章 符号表343
13.1 引言343
13.2 什么是符号表343
13.3 符号表的实现343
13.4 符号表实现的比较344
第14章 散列法346
14.1 什么是散列法346
14.2 为什么需要散列法346
14.3 散列表的抽象数据类型346
14.4 理解散列法346
14.5 散列法的构成要素347
14.6 散列表348
14.7 散列函数348
14.8 装填因子348
14.9 冲突349
14.10 解决冲突的方法349
14.11 拉链法349
14.12 开放地址法349
14.13 冲突解决方法的比较351
14.14 如何得到复杂度为O(1)的散列法352
14.15 散列技术352
14.16 不合适构造散列表的问题352
14.17 Bloom过滤器353
14.18 关于散列法的问题集355
第15章 字符串算法366
15.1 引言366
15.2 字符串匹配算法366
15.3 蛮力法366
15.4 Robin-Karp字符串匹配算法367
15.5 基于有限自动机的字符串匹配368
15.6 KMP算法370
15.7 Boyce-Moore算法373
15.8 字符串的存储结构373
15.9 字符串的散列表374
15.10 字符串的二叉搜索树374
15.11 字典树374
15.12 三叉搜索树377
15.13 二叉搜索树、字典树和三叉搜索树的比较380
15.14 后缀树380
15.15 关于字符串的问题集384
第16章 算法设计技巧393
16.1 引言393
16.2 算法的分类393
16.3 基于实现方法的算法分类393
16.4 基于设计方法的算法分类394
16.5 其他方式的算法分类395
第17章 贪婪算法396
17.1 引言396
17.2 贪婪策略396
17.3 贪婪算法的要素396
17.4 贪婪技术总是奏效吗396
17.5 贪婪方法的优缺点396
17.6 贪婪技术的应用397
17.7 理解贪婪技术397
17.8 关于贪婪算法的问题集400
第18章 分治算法407
18.1 引言407
18.2 什么是分治策略407
18.3 分治法总是奏效吗407
18.4 分治法原理的图形化演示407
18.5 理解分治法408
18.6 分治法的优点408
18.7 分治法的缺点409
18.8 主定理409
18.9 分治法的应用409
18.10 关于分治法的问题集409
第19章 动态规划422
19.1 引言422
19.2 什么是动态规划策略422
19.3 动态规划策略的性质422
19.4 动态规划可以求解所有的问题吗422
19.5 动态规划方法422
19.6 动态规划算法举例423
19.7 理解动态规划423
19.8 最长公共子序列426
19.9 关于动态规划的问题集429
第20章 复杂性类461
20.1 引言461
20.2 多项式/指数时间461
20.3 什么是判定性问题461
20.4 判定性过程462
20.5 什么是复杂性类462
20.6 复杂性类的类型462
20.7 归约464
20.8 关于复杂性类的问题集466
第21章 其他主题469
21.1 引言469
21.2 位编程的技巧469
21.3 其他编程问题474
参考文献481
