学习数据结构的框架思维

本文是对整个数据结构及算法的总体框架认识,旨在教会读者从整体到细节,自顶向下,从抽象到具体地认识数据结构,这种思维也是递归思维的精华所在。希望通过本文读者在对数据结构的学习和理解上能有更高层的认识。

点击这里进入公众号平台查看本文,阅读体验可能更好一些。

先声明一下:首先,这里讲的都是普通的数据结构,咱不是搞算法竞赛的,野路子出生,很多厉害的知识我不会,我只会解决常规的问题。另外,以下是我个人的经验的总结,没有哪本算法书会写这些东西,所以请读者试着理解我的角度,如果不是严重的逻辑错误,没必要纠结于细节问题,因为这篇文章就是希望对数据结构和算法建立一个框架性的认识。我有信心大家能从这篇文章里学到点什么。

如果没时间细看,一定不要错过第四点。

一、数据结构千变万化,但不离其宗

最高层的抽象,数据结构只有两种:数组和链表。

这句话怎么理解,不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗?

我们分析问题,一定要有递归的思想,自顶向下,从抽象到具体。你上来就列出这么多,那些都属于「上层建筑」,而数组和链表才是「结构基础」。因为那些多样化的数据结构,究其源头,都是在链表或者数组上的特殊操作,API 不同而已。

比如说「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现,就要处理扩容缩容的问题;用链表实现,没有这个问题,但需要更多的空间存储节点指针。

「图」的两种表示方法,邻接表就是链表,邻接矩阵就是二维数组。邻接矩阵判断连通性迅速,并可以进行矩阵运算解决一些问题,但是一般比较耗费空间。邻接表比较节省空间,但是时间上肯定比不过邻接矩阵。

「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法,拉链法需要链表特性,操作简单,但需要空间;线性探查法就需要数组特性,以便连续寻址,省空间,但操作稍微复杂些。

「树」,用数组实现就是「堆」,因为「堆」是一个完全二叉树,用数组存储不需要节点指针,操作也比较简单;用链表实现就是很常见的那种「树」,因为不一定是完全二叉树,所以不适合用数组存储。为此,在这种链表「树」结构之上,又衍生出各种巧妙的设计,比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等,以应对不同的问题。

二、对数据结构的操作,无非遍历 + 访问

遍历 + 访问,再具体一点就是:增删查改。

数据结构种类很多,但它们存在的目的都是在不同的应用场景,尽可能高效地增删查改。试问,除此之外还有其他吗?

如何遍历 + 访问?我们仍然从最高层来看,各种数据结构的遍历 + 访问无非两种形式,线性的和非线性的。

线性就是 for/while 为代表,非线性就是递归为代表。再具体一步,无非以下两种框架:

数组遍历框架,典型的线性遍历结构:

1
2
3
4
5
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 访问 arr[i]
}
}

二叉树遍历框架,典型的非线性递归遍历结构:

1
2
3
4
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}

以上两个框架可以改造。

链表遍历框架,兼具线性和非线性遍历结构:

1
2
3
4
5
6
7
8
9
10
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 访问 p.val
}
}

void traverse(ListNode head) {
// 访问 head.val
traverse(head.next)
}

二叉树框架又可以具体扩展为 N 叉树的遍历框架:

1
2
3
4
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}

N 叉树的遍历又可以扩展为图的遍历,因为,图就是好几 N 叉棵树的结合体。你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了,就不写代码了。

所谓框架,就是说不管增删查改,这些代码都是永远无法脱离的结构,你可以把这个结构作为大纲,根据具体问题在框架上添加代码就行了。

三、为什么算法总是和数据结构同时出现

数据结构是工具,算法是通过合适的工具解决问题的方法。

拿原始人举例,我们学会了数据结构,就像原始人拥有了石刀,石斧等工具。而根据制造工具的工艺不同,石刀又分尖锐的石刀和锯齿状石刀,前者适合打猎,后者适合切割;就像图这种数据结构通过不同的实现方法(链表、数组),可以表示为邻接表和邻接矩阵,前者适合处理非稠密图,后者适合处理稠密图。原始人想要造一栋房子,就要进行规划,石斧砍树,石刀磨尖角等等;就像我们设计算法,发挥数据结构的特性,去解决实际问题。

算法利用数据结构,可以显式利用,比如说前文单调栈,就是巧妙地直接利用了栈结构先进后出的特性。稍微高级一点的算法设计思路,就是隐式利用数据结构,比如前文讲过的回溯算法、动态规划,以及传说中的的分治算法,都在利用树这种结构来解决问题。

但是,无论怎样利用数据结构,多么高大上的算法,其解法都逃不出第二点中相应的框架,是不是?

四、最后总结(重要)

对于一个初学算法的人来说,一定要学会从框架上看问题,而不要纠结于细节问题。

啥叫细节问题?比如说 i 到底应该加到 n 还是加到 n - 1 ?这个数组的大小到底应该开 n 还是 n + 1 ?

啥叫从框架上看问题?比如说前文动态规划中凑零钱的问题,如果你看了一眼代码就自动忽略细节问题,直接提取出 N 叉树遍历框架,你的框架思维就到位了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 完整代码 */
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
int ans = INT_MAX;
for (int coin : coins) {
// 金额不可达
if (amount - coin < 0) continue;
int subProb = coinChange(coins, amount - coin);
// 子问题无解
if (subProb == -1) continue;
ans = min(ans, subProb + 1);
}
return ans == INT_MAX ? -1 : ans;
}

/* N 叉树遍历框架 */
int coinChange(vector<int>& coins, int amount) {
for (int coin : coins)
coinChange(coins, amount - coin);
}

当然,如果细节出错,你得不到正确的答案,但是只要有框架,你再错也错不到哪去,因为你的方向是对的。

但是,你要是心中没有框架,那么你根本无法解题,给了你答案,你也不会发现这就是个树的遍历问题。

这就是框架的力量,能够保证你在快睡着的时候,依然能写出正确的程序;就算你啥都不会,都能比别人高一个级别。

初学阶段,根本没到纠结细节的地步。细节出错,可以有各种方法查出来,比如到处打 log,没有找不到的 bug 。相比之下,别人还束手无策的时候,你已经做出了一个错误的答案;当别人没有框架的指导,被无限细节劝退数据结构的时候,你已经通过框架理解了数据结构的精髓。这不就是一种巨大的成功吗?真的得给你鼓掌。

欢迎关注我的公众号 labuladong,致力于把算法讲清楚~

公众号二维码

推荐阅读

动态规划详解

双指针技巧汇总

一个通用方法团灭 6 道股票买卖问题