# 数据结构与算法大全（一）数据结构

## 目录

一、数学基础

二、算法分析

三、常见数据结构

四、常见排序算法

五、常见查找算法

六、栈相关算法

七、链表相关算法

八、双指针相关

九、二叉树相关

十、深度优先和广度优先算法

十一、贪心算法

十二、回溯算法

十三、动态规划

## 一、数学基础

### 1. 指数

### 2. 对数

### 3. 级数

### 4. 模运算

### 5. 证明的方法

- 1. 归纳法

- 2. 反证法

### 6. 极限

- 1. 洛必达法则

## 二、算法分析

### 1. 时间复杂度

### 2. 空间复杂度

## 三、常见数据结构

### 1. 数组

- 1. 数组是具有相同类型的数据的集合，也就是说数组的所有元素的类型都是相同的，在所有的数据结构中， 数组算是最常见也是最简单的一种数据结构，我们最常见的也就是一维数组，当然还有二维，三维......， 数组需要先声明才能使用，数组的大小一旦确定就不可以在变了

- 2. 数组的查找是比较方便的，但对数组的增删就没那么方便了，因为数组是一块连续的内存空间， 如果在前面增加和删除，都会导致后面元素位置的变动。

- 3. ArrayList底层实现

- 4. CopyOnWriteArrayList底层实现

### 2. 链表

- 链表是一种物理存储单元上非连续的一种数据结构，看名字我们就知道他是一种链式的结构，就像一群人 手牵着手一样。链表有单向的，双向的，还有环形的。

- 1. 单项链表

- 1. 单向链表的定义

- 这个类非常简单，他只有两个变量，一个是data值，一个是指向下一个结点的指针。

- 2. 单向链表的增删

- 链表不像数组那样，可以通过索引来获取，单向链表查找的时候必须从头开始往后一个个找，而不能从中 间找，也不能从后往前找。

• - 1. 添加到尾结点
• - 添加到尾结点比较简单，我们只需要找到之前链表的尾结点，然后让他的next指针指向新的结点即可。
• - 2. 添加到中间结点
• - 添加到中间结点，分为两步，比如我们要在ab结点之间添加新结点n，第一步让新结点n的指针指向b，然 后再让a的指针指向新结点n即可。
• - 3. 删除链表的尾结点
• - 只需要让尾结点的上一个结点的指针指向null即可。
• - 4. 删除链表的中间结点
• - 只需要把要删除结点的前一个结点的指针指向要删除结点的下一个结点即可，最好还要把要删除结点的数 据清空，并且让他的指针指向null。

- 2. 单向环形链表

- 1. 添加到尾结点

- 2. 删除尾结点

- 3. 使用场景

- 3. 双向链表

- 1. 双向链表的定义类

• - 1. 双向链表不光有指向下一个结点的指针，而且还有指向上一个结点的指针，他比单向链表多了一个指向前 一个结点的指针，单向链表我们只能从前往后找，而双向链表我们不光可以从前往后找，而且还可以从后 往前找
• - 2. 双向链表我们可以从头到尾查找，也可以从尾到头查找，双向链表在代码中最常见的就是LinkedList了 (java语言)，双向链表的增删和单向链表的增删很类似，只不过双向链表不光要调整他指向的下一个结 点，还要调整他指向的上一个结点。

• - 3. LinkedList底层实现

- 2. 双向链表的增删

• - 1. 添加到尾结点
• - 2. 添加到头结点
• - 3. 添加到指定结点之前
• - 4. 删除链表的尾结点
• - 5. 删除链表的头结点
• - 6. 删除链表的中间结点

- 4. 双向环形链表

- 1. LinkedHashMap底层实现

- 2. 使用场景

### 3. 队列

- 队列是一种特殊的线性表，他的特殊性在于我们只能操作他头部和尾部的元素，中间的元素我们操作不了，我们只能在他的头部进行删除，尾部进行添加。就像大家排队到银行取钱一样，先来的肯 定要排到前面，后来的只能排在队尾，所有元素都要遵守这个操作，没有VIP会员，所以走后门插 队的现象是不可能存在的，他是一种先进先出的数据结构。我们来看一下队列的数据结构是什么样 的

- 1. 一般队列

- 1. 一般队列的定义

- 他只能从左边进，右边出，队列实现方式一般有两种，一种是基于数组的，还一种是基于链表的， 如果基于链表的倒还好说，因为链表的长度是随时都可以变的，这个实现起来比较简单。如果是基 于数组的，就会稍微有点不同，因为数组的大小在初始化的时候就已经固定了

- 2. 一般队列的代码实现

- 3. 一般队列的问题

- 2. 双端队列

- 1. 双端队列的定义

- 双端队列也是有两个指针，front指向队首，tail指向队尾的下一个存储单元，并且双端队列的队首 和队尾都可以添加和删除元素

- 2. 双端队列的代码实现

- 3. 优先队列（FIFO）

- 1. 优先队列的定义

- 2. 优先队列的代码实现

### 4. 栈

- 1. 栈的定义

- 栈也是一种特殊的线性表，他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作，他就好 像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的 时候不允许从中间放进去，拿书的时候也是先从最上面开始拿，不允许从下边或中间抽出来。

- 2. 栈的代码实现

### 5. 散列表

- 1. 散列表的定义

- 散列表也叫哈希表，是根据键值对(key，value)进行访问的一种数据结构。他是把一对(key， value)通过key的哈希值来映射到数组中的，也就是说，它通过把关键码值映射到表中一个位置 来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

- 2. HashMap

- 1. 数组的长度必须是2的n次幂

- 2. entry 的个数不能大于数组长度的75%，如果大于就会触发扩容机制进行扩容

- 3. 在java中1.7及以前的版本如果以链表的形式存在，在插入的时候采用的是头插法。

在1.8是尾插法。并且在java1.8中如果链表的长度大于8的时候会转为红黑树。

- 4. 在HashMap中，数组的大小是2^n，无论你初始化的时候传的值是多少，他都会初始化为2^n，并 且这个2^n是大于等于你初始化值的最小值，比如初始化的时候传的值是17，他会计算得到32。

- 3. ArrayMap

- 1. 实现原理

- ArrayMap的实现原理是使用两个数组，一个存放hash值，一个存放key和value，其中存放key和 value的数组长度是存放hash值数组长度的二倍，其中存放hash值的数组必须是排序的。如果 hash值出现了冲突，说明hash值最终的计算是一样的，那么在hash数组中肯定是挨着的，所以查 找的时候如果hash值有重复的就会把重复的也查找一遍。

- 2. 代码实现

- 4. SparseArray

- 在散列表中如果可以确定key值都是int类型，那么又可以简化，直接用key值当hash值存储即可， 和ArrayMap一样只需要两个数组即可，一个是存放key的，一个是存放value的，不同的是这两个 数组的长度都是一样的。这种情况下就不会出现hash值一样的问题了，因为这个时候如果hash值 一样的话，那么他们的key肯定是一样的，而在散列表中是不可能存在了，假如在插入数据的时候 有一样的key，那么他的value是要被替换掉的，所以不会出现两个完全一样的key。

- 5. ThreadLocalMap

- 在java语言中还有一个关于散列表的，那就是ThreadLocalMap，这个类是ThreadLocal的一个静 态内部类，一般我们用不到。如果出现hash冲突的时候他的实现原理和上面的几种也都不太一 样。存储的时候他首先会根据hash值映射到指定的数组，如果当前位置为空就直接存进去，如果 不为空就往后找，找他的下一个

### 6. 树

- 1. 树的定义

- 树是一个有n个有限节点组成一个具有层次关系的集合，每个节点有0个或者多个子节 点，没有父节点的节点称为根节点，也就是说除了根节点以外每个节点都有父节点，并 且有且只有一个。

- 2. 树的种类

- 1. 二叉树

- 2. 红黑树

- 3. AVL树

- 4. B树

- 5. 哈夫曼树

- 带权路径最短的二叉树称为哈夫曼树或最优二叉树;

- 6. 字典树

- 3. 树节点类定义

- 1. 结点的度:一个结点含有的子结点的个数称为该结点的度;

- 2. 叶结点或终端结点:度为0的结点称为叶结点;

- 3. 非终端结点或分支结点:度不为0的结点;

- 4. 双亲结点或父结点:若一个结点含有子结点，则这个结点称为其子结点的父结点;

- 5. 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;

- 6. 兄弟结点:具有相同父结点的结点互称为兄弟结点;

- 7. 树的度:一棵树中，最大的结点的度称为树的度;

- 8. 结点的层次:从根开始定义起，根为第1层，根的子结点为第2层，以此类推;

- 9. 树的高度或深度:树中结点的最大层次;

- 10. 堂兄弟结点:双亲在同一层的结点互为堂兄弟;

- 11. 结点的祖先:从根到该结点所经分支上的所有结点;

- 12. 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。

- 13. 森林:由m(m>=0)棵互不相交的树的集合称为森林;

- 14. 无序树:树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;

- 15. 有序树:树中任意节点的子结点之间有顺序关系，这种树称为有序树;

- 16. 二叉树:每个节点最多含有两个子树的树称为二叉树;

- 17. 完全二叉树:若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1)的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这 就是完全二叉树

- 18. 满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个 子结点的二叉树。

- 19. 哈夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;

- 4. 树的遍历

- 1. 前序遍历

- 1. 他的访问顺序是:根节点→左子树→右子树

- 2. 代码实现

- 2. 中序遍历

- 1. 他的访问顺序是:左子树→根节点→右子树

- 2. 代码实现

- 3. 后续遍历

- 1. 他的访问顺序是:左子树→右子树→根节点

- 2. 代码实现

- 4. BFS(宽度优先搜索(又称广度优先搜索))

- 1. 他的访问顺序是:先访问上一层，在访问下一层，一层一层的往下访问

- 2. 代码实现

- 5. DFS(深度优先搜索)

- 1. 他的访问顺序是:先访根节点，然后左结点，一直往下，直到最左结点没有子节点 的时候然后往上退一步到父节点，然后父节点的右子节点在重复上面步骤......

- 2. 代码实现

### 7. 堆

- 1. 堆的定义

- 通常情况下我们把堆看成是一棵完全二叉树。堆一般分为两种，一种是最大堆，一 种是最小堆。最大堆要求根节点的值即大于左子树的值，又大于右子树的值。也就 是说最大堆根节点的值是堆中最大的。最小堆根节点的值是堆中最小的

- 2. 堆的创建

- 把元素加入到堆中的时候，都要和父节点进行比对，在最小堆 中，如果比父节点小，就要和父节点交换，交换之后还要继续和再和新的父节点对 比......。同理在最大堆中，如果比父节点大，就要和父节点交换

- 3. 堆的删除

- 堆的添加会往上调整，堆的删除不仅会往下调整而且还有可能往上调整。堆中元素 的删除我们可以从堆顶删除，也可以从中间某个位置删除，如果从堆顶删除的话我 们只需要往下调整即可，因为堆顶没有父节点，不需要往上调整。如果从中间删除 的话，我们先要往下调整，如果往下调整没有成功(比如在最小堆中，他比两个子 节点都小)，我们还要进行往上的调整。调整的原理就是把数组最后一个元素放到 要删除的元素位置上，然后在删除元素的位置上进行上下调整，原理其实都差不 多，我们来看一下最小堆顶部元素删除之后的调整。

- 4. 堆的代码实现

- 5. 堆排序

- 我们知道最大堆就是堆顶元素始终保持的是最大值，最小堆就是 堆顶元素始终保持的是最小值，假如在最小堆中我们把堆顶元素一个个给移除不就 相当于排序了吗。

## 四、常见排序算法

### 1. 冒泡排序

### 2. 选择排序

### 3. 插入排序

### 4. 快速排序

### 5. 归并排序

### 6. 堆排序

### 7. 桶排序

### 8. 基尔排序

### 9. 希尔排序

### 10. 计数排序

### 11. 位图排序

## 五、常见查找算法

### 1. 顺序查找

### 2. 二分法查找

### 3. 插值查找

### 4. 斐波那契查找

### 5. 分块查找

### 6. 哈希查找

## 六、栈相关算法

## 七、链表相关算法

## 八、双指针相关

## 九、二叉树相关

## 十、深度优先和广度优先算法

## 十一、贪心算法

## 十二、回溯算法

## 十三、动态规划

## 参考资料

- [数据结构和算法试题大全](
https://www.toutiao.com/i6903421300237353476)

- 《数据结构与算法分析Java语言描述 原书第3版 》