震惊！阿里3-1级别大佬把《数据结构与算法》讲透了（源码笔记）

迈不过友情╰ 2023-10-14 17:14 12阅读 0赞

### 开篇 ###

数据结构是计算机科学与技术专业非常重要的一门核心基础课，计算机科学各个领域以及各种应用软件都要使用相关的数据结构和算法。

本篇的主要目的不是提供关于数据结构和算法的定理及证明。本书采用的模式是利用不同的复杂度改善问题的解决(对于每个问题，你将发现多个具有不同复杂度及降低复杂度的解法)。基本上，这一思路就是列举某个问题的所有可能性。通过这种方式，即使你遇到一个新问题，它也能够向你指明如何思考该问题所有可能的结果。对于正在准备面试、参加选拔性考试以及校园面试的读者很有帮助。

### 一、递归和回溯 ###

**什么是递归**

任何调用自身的函数称为递归。用递归方法求解问题，要点在于递归函数调用自身去解决一个规模比原始问题小-些的问题。这个过程称为递归步骤。递归步骤会导致更多的递归调用。因此，保证递归过程能够终止是很重要的。每次函数都会用比原问题规模更小的问题来调用自身。问题是随着规模不断变小必须能最终收敛到基本情形。

![format_png][]

### 二、链表 ###

**什么是链表**

链表是一种用于存储数据集合的数据结构。

![format_png 1][]

### 三、栈 ###

**什么是栈**

栈是一种用于存储数据的简单数据结构(与链表类似)。数据入栈的次序是栈的关键。可以把自助餐厅中的一-堆盘子看作-一个栈的例子。当盘子洗干净后，它们会添加到栈的顶端。当需要盘子时，也是从栈的顶端拿取。所以第一个放人栈中的盘子最后才能被拿取。

![format_png 2][]

### 四、列队 ###

**什么是列队**

队列是一种用于存储数据的数据结构(与链表和栈类似)。数据到达的次序是队列的关键。在日常生活中队列是指从序列的开始按照顺序排列等待服务的一队人或物。

![format_png 3][]

### 五、数 ###

**什么是数**

树是一种类似于链表的数据结构，不过链表的结点是以线性方式简单地指向其后继结点，而树的一个结点可以指向许多个结点。树是一种典型的非线性结构。树结构是表达具有层次特性的图结构的一种方法。对于树ADT(抽象数据类型)，元素的顺序不是考虑的重点。如果需要用到元素的顺序信息，那么可以使用链表、栈、队列等线性数据结构。

![format_png 4][]

### 六、优先队列和堆 ###

**什么是优先队列**

在有些情况下，可能需要找到元素集合中的最小或最大的元素。可以利用优先队列ADT来完成该操作。优先队列ADT是一-种数据结构，它支持插入(Insert)和删除最小值(DeleteMin)操作(返回并删除最小元素)或删除最大值(DeleteMax)操作(返回并删除最大元素)。

这些操作等价于队列的EnQueue和DnQueue操作。区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同。作业调度是优先队列的一一个应用实例，它根据优先级高低而不是先到先服务的方式来进行调度。

![format_png 5][]

### 七、并查集ADT ###

![format_png 6][]

### 八、图算法 ###

在现实世界中，许多问题是由对象以及它们之间的联系所描述的。例如，在航空地图中，我们可能对这样的问题感兴趣:“从海 德拉巴去纽约，哪种方式最快?”或者“哪种方式价格最便宜?”为了回答这些问题，需要关于对象(城镇)之间的联系(飞行路线)信息。图就是用来解决这类问题的数据结构。

![format_png 7][]

### 九、排序 ###

**什么是排序**

排序是按照某种顺序(升序或降序)排列序列元素的一种算法。排序的输出是输入的排列或重新排序。

![format_png 8][]

### 十、查找 ###

**什么是查找**

在计算机科学中，查找(或称为搜索)就是从一个项目的集合中寻找某个具有特定属性的项目的过程。项目可以是存储在数据库中的记录、数组中的简单数据元素、文件中的文本、树中的结点、图中的顶点和边，或者其他搜索空间的元素。

![format_png 9][]

### 十一、选择算法( 中位数 ) ###

**什么是选择算法**

选择算法是在某个列表中寻找第k个最小/最大数字(也称为第k个顺序统计量)的算法法。这包括查找最小值、最大值和中位数。对于查找第k个顺序统计量，有多种不同的复杂的解决方案，本章将列举所有这些可能的解决方案。

![format_png 10][]

### 十二、符号表 ###

**符号表是关联值和键值的一种数据结构**

![format_png 11][]

### 十三、散列 ###

**什么是散列**

散列是一种用以实现信息存储和快速检索的技术。它常用于执行优化搜索和符号表的实现。

![format_png 12][]

### 十四、字符串算法 ###

![format_png 13][]

### 十五、算法设计技术 ###

前面的章节针对不同的问题介绍了各种算法。在求解一个新问题时，通常的思路是寻找当前问题与已解决问题之间的相似之处，从而轻松找到新问题的求解方法。

![format_png 14][]

### 十六、贪婪算法 ###

首先通过对一个简单理论的讨论，初步理解贪婪的思想。以下棋为例，每一步都有决策都需要考虑对后续棋局的影响。而在网球(或排球)比赛中，选手的行为仅取决于当前的状况，选择当下最为正确的动作，而不关心后续的影响。这说明在某些情况下选择当下最佳行为的决策，可以得到一个最优解(贪婪)，但并非所有情况都如此，贪婪策略适用于上述第二类问题。

![format_png 15][]

### 十七、分治算法 ###

对于第17章列举的许多问题，贪婪策略不能提供最优解。而其中的某些问题可通过分治(Divid and Conquer, D&.C)法来轻松求解。分治法是一种重要的基于递归的算法设计技术，分治算法递归地将问题分解为两个或多个同类型的子问题，直至这些子问题简.单到能够直接求解，然后再将这些子问题的解合成为原始问题的解。

![format_png 16][]

### 十八、动态规划算法 ###

![format_png 17][]

### 十九、复杂度类型 ###

在前面的各章中，描述了不同问题求解的复杂度。某些算法随着问题规模的增加其复杂度的增长速率较低，而另一些则有比较高的增长速率。对于具有较低增长率的问题，称为简单问题(或易求解问题);对于具有较高复杂度的问题，称为难问题(或难求解的问题)。该分类是基于求解某个问题时算法的运行时间(或者占用内存)决定的。

![format_png 18][]

### 总结（特点） ###

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

![format_png 19][]

[format_png]: https://img-blog.csdnimg.cn/img_convert/1c314c7627bc69df738ebbfcea6ef17d.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/86b75adb469e613fdeb86523efda795c.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/6373d0885bdeacdd89aaf464bd82d186.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/c99e8d94cab6f9641404e7e8d50ca1e4.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/5d653f7c3a6f99dda1d5e76cfdd4369f.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/af057a0fbb1e9a3e43519d98cf9612d8.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/0d46e359cc00092e45c051e344eeccee.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/13da056058c7b5544dbe2f7f30670e7b.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/c107fad8bf8b0d1ae73f546ca678ab1f.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/59bd5554ec4344e1279c3543346e1d6e.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/f73a78954e4a3fd8af37a0e2d637c1cb.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/c0fab8532a983c70761d28621d4c58d8.webp?x-oss-process=image/format,png
[format_png 12]: https://img-blog.csdnimg.cn/img_convert/817b1b55c758670e379453403a6a9e75.webp?x-oss-process=image/format,png
[format_png 13]: https://img-blog.csdnimg.cn/img_convert/07e4570b7a66c19bbe7c79a43670b93e.webp?x-oss-process=image/format,png
[format_png 14]: https://img-blog.csdnimg.cn/img_convert/cb1f866f2b074207be8997767ab31ac0.webp?x-oss-process=image/format,png
[format_png 15]: https://img-blog.csdnimg.cn/img_convert/b7e7019fe6635d0d0f16dd3fbfcabb9b.webp?x-oss-process=image/format,png
[format_png 16]: https://img-blog.csdnimg.cn/img_convert/6ae9078f284ad0928806ff1b31656d97.webp?x-oss-process=image/format,png
[format_png 17]: https://img-blog.csdnimg.cn/img_convert/6ce159307c4059b4ddeaa28ae1390922.webp?x-oss-process=image/format,png
[format_png 18]: https://img-blog.csdnimg.cn/img_convert/f53aa517a05d6fa4b00fbe0ea6010837.webp?x-oss-process=image/format,png
[format_png 19]: https://img-blog.csdnimg.cn/img_convert/e3a46e5ae5491b25c83234acf552093f.webp?x-oss-process=image/format,png