0%

关于数据结构的一点浅薄的感悟💡

数据结构课也算是一学期快要上完了,尽管凯哥吹了一学期的牛,似乎并没有讲什么数据结构方面具体的知识,但我感觉一学期下来收获良多。可能是因为凯哥讲课比较注重方法论,许多具体的点,尽管不细讲,但他会跟我们讲明白原理,讲一些计算机的底层的架构,我觉得这些对我思想方面的提升是巨大的。我觉得数据结构这门课在凯哥的引导以及自学下慢慢领悟到了一些思想了。有的时候看凯哥其实更像一个计组老师,我很感激他。

最近在写一个图论的作业,写着写着突然想起来以前和学长的聊天:
还没上大学的时候,根本就不知道数据结构的含义,只知道大学要开这门课,学长对我说以后数据结构一定要好好学,基础打扎实。我那时候还不明白为什么,我问他你们数据结构学了什么呢?他说堆栈、树、图之类的,我说那这不是算法吗?他说还是有一定的区别的。

我觉得把数据结构和算法等同是我以前一个十分幼稚的想法,初中的时候打过oi,那时候学了一大堆算法,分治、贪心、动态规划以及一大堆现在已经叫不上名的算法。但实际上感觉当时自己只是机械地去为了做题学了一堆算法,根本没有对这一门学问进行一个思想方面的总结。

现在回头来看,感觉数据结构和算法最大的区别,就是两者注重的方面不一样。数据结构和算法都是程序员在解决问题中需要用到的技能,不同的数据结构配合着不同的算法。

数据结构,我觉得最重要的是学会面对一个具体的问题时提出一个合适的模型来存储数据。我认为一个模型并不一定要符合问题本身的特征,例如一排小朋友排队,并不一定就要建立一个线性表,用树也是可以的,具体却决于问题。数据结构的建立应当基于自己所需要解决的问题,使得在这一数据结构下算法有着最高效发挥的余地。比如我这几天的作业就是要写图的Dijkstra算法,我一开始想偷懒用二维邻接矩阵来存储边的长度,但如果使用这样的数据结构,每从一个节点出发的时候都得进行O(n)的遍历来判断边是否走得通。因此我选择用邻接链表来存储边,这样在建立数据结构的时候会稍显麻烦,因为每一次都得找到节点的存储边的链表的最后一位。但这样在遍历的时候每一次只需要遍历节点对应的邻接链表就可以了,大大减少了时间开销。

而算法,我觉得是提升效率的一个拓展,但如果没有合适的数据结构,算法也很难有发挥的余地。算法的内容博大精深,但是很多时候的情况并不需要用到一些特别复杂的算法,一些经典的算法已经可以解决绝大多数的问题。而再往后的算法都是一些具体的优化与博弈,是要根据具体问题设计的。总的来说我觉得没有完美的算法,大多数不同的算法的设计其实是在牺牲不必要的变量换取所需的变量,例如时间和空间,根据具体问题选择倾向的对象。但也有些算法,它牺牲的变量对于换取的价值来说几乎不值一提,例如快速排序,因此会显得比原先的算法高效得多。

掌握算法固然重要,但若是想我以前一样罔顾数据结构盲目学算法的话,终究没法领悟算法的精髓,有的时候设计出一个漂亮的数据结构也能带来等同于设计出一个漂亮算法的喜悦。