前端算法之美-数据结构

前面一篇 前端算法之美-入门篇，讲了一些算法的基础概念。时间复杂度，空间复杂度，大 O 表示法，最坏时间复杂度，最好时间复杂度，平均时间复杂度，均摊时间复杂度。基础算法思想，分治算法，枚举算法，回溯算法，贪心算法，动态规划。还介绍了简单的算法，二分查找。这一篇我们介绍数据结构。

即将上线 前端算法之美-查找算法

即将上线 前端算法之美-进阶篇

数据结构分类

数据结构和算法是密不可分的，再好的算法也是依托于数据结构。我们将数据结构分为 4 个类，线性表，散列表，数，图。数组和链表是最基础的数据结构，所有的复杂的数据结构都是从它两变化而来。

• 链表，单链表，双向链表，循环链表，双向循环链表，静态链表
• 栈，顺序栈，链式栈
• 队列，普通队列，双端队列，阻塞队列，并发队列，阻塞并发队列
• 背包，这是《算法》一书中提供的数据结构，直接将数据塞到一个无需的背包中。

• 线性试探法

无论是那种方式，都需要实现散列表的散列函数，解决 hash 冲突问题，实现动态扩容。

• 普通二叉树
• 平衡二叉树，包括 AVL 树，和红黑树。
• 完全二叉树
• 多路查找树，B 树，B+树（数据库索引），B-树。2-3 树（红黑树的实现基础）
• 堆，小顶堆，大顶堆，优先队列，斐波那契堆，二项堆。堆可以用来解决最大值最小值，最大 Top K 值问题。
• 其他树状结构

二叉树有三种遍历方式，前序遍历，中序遍历，后序遍历。前中后分别对应遍历根节点的顺序。前序会边遍历根节点，再遍历左子树，最后遍历右子树。

• 无向图，无方向的图。
• 有向图，有方向的图。
• 最小生成树，在一张图中找到含有其所有定点的无向连通子图，Prim 算法和 Kruskal 算法
• 最短路径，Dijkstra 算法，比如地图类查找

图有两种方式实现存储，分别是邻接矩阵和邻接表，一般使用邻接表，图大多是很稀疏的，用邻接矩阵浪费空间。图的搜索有两种方式，广度优先搜索和深度优先搜索，合适的场景用合适的算法。

我们将字符串单独作为一项，因为我们大部分时候处理的数据结构都是字符串。

处理字符串算法一般有下面 4 种

• 暴力查找法

暴力查找法有时候可能是最快的算法，需要根据场景区分。KMP 和 BM 算法思想类似，都是模式字符串匹配失败之后，寻找回退节点的算法，BM 是从模式字符串的最后一位开始比较。RK 算法是基于散列表的算法，在每次比较内容和模式字符串时，每次通过移除内容子串首位，再乘以进制，加上新移动的后面一位内容，能有效利用之前计算的结果。

利用正则表达式也可以查找字符串，它是一种 NFA，非确定的有限状态机，和 KMP 相反，它是 DFA。

字符串还有一个大的使用场景，数据压缩。数据的压缩算法，主要是减少字符的占用，以及相同的合并。使用霍夫曼编码，这是霍夫曼在学生时代就研究出来的算法，利用字典表和比特，构造一个含有频率（字符出现次数）和唯一比特标识的 key，压缩的时候需要讲字典表也压缩进去，字符串较多时，基本不影响体积。

每一种算法都需要具体的数据结构，两者相辅相成。当然我们可以使用不同的数据结构实现同一算法，但是它们的时间复杂度和空间复杂度都有所不同，这就需要我们选择最合适的数据结构，才能实现最优的算法。