关于数据结构的一些想法

毛线球上的喵星人 497 2021-07-19

前言

写这篇文章的动机呢,其实是洗澡的时候突然想到,并结合平时中的一些感受所产生的:大多数学数据结构的人,总是给我一种为了学数据结构而学的感觉。

问题

数据结构和算法,这两个好兄弟不论是在本科的课程里还是在面试中,都是最基础的考察项目。但是大多数人,在刚刚入门的时候,比如刚学习完一门语言的语法,准备深入学习的时候,就会有人告诉说:该学数据结构了。然后从天而降一个链表让你学,学会了用就完事了,迷迷糊糊学完之后,又塞来一个二叉树...

关系

一般在教材中,每个不同的结构都是分成不同的章节进行讲解的,通常是列表、树、图...这样的顺序展开。从分类和学习进度上,这样并没有问题,但是在学习的时候,由于每个部分被分成不同的章节,而在表面上看起来没有关联。
这就是问题所在,每一种数据结构都是层层递进的。

开始

每一个数据结构和算法都是根据需要而被一个个发明创造出来的。链表、栈、树、图...这些东西不是一开始就存在,而是根据需要而被前辈发明出来,并且经过抽象和提炼后,总结出最基础、最常用的这几种结构作为入门。但是我们在学习的时候,不是为了学习掌握这种结构,而是需要掌握如何创造结构。
数组不够灵活,所以有了能够灵活分配空间的单链表;单链表只能向后不能往前,所以就有了前后指针的双向链表;数组和链表的操作太多了,我只需要排队或者做一个桶的功能,所以屏蔽了多余的功能,有了以数组或链表为基础的栈和队列;链表是一维的线性结构,查找只能从头或尾巴依次遍历,效率太低怎么办?把一维的线性结构转换为非线性的,把单链表的next指针拆分成两个(left和right)并规定比我小的在左边,大的在右边,于是便有了二叉排序树;排序树依赖插入顺序,最差情况(左斜树或右斜树)还是退化成一个链表,那就规定左右子树的高度差不能超过1,不平衡的时候需要通过左右旋的操作保持平衡,这就成了AVL平衡树。在此基础上,对条件、性能的不同要求,从而不断的改造出了B树、红黑树等等亚种。
那图呢?一样的,链表和数组既然只能存储一维的信息,那用两个链表或者数组套起来,不就是二维的吗?链表的每个节点保存每个子链表的头结点,每个一级数组保存子数组的起点,不就是二维的吗?此上结合数论,将图拆分成点和边分别存储,于是就有了以数组为基础的邻接表,以链表为基础的十字链两种存储图的方式,甚至还有结合数组和链表的多重邻接表。

结论

说了这么多,其实总结就一些。学数据结构学的不是结构本身,而是研究结构是如何被创造出来的,如何根据需要 去创造新的高效的方案。换句话说,就是无招胜有招,在掌握本质之后,就可以根据需要直接创造出需要的结构。


# 程序 # 代码 # 数据结构