beginning

栈、队列、数组、链表、树、图…这些东西感觉有些没听过。但实际上,我们每天都在使用它们。

从栈开始

根据《算法导论》所说:

栈是一种后进先出的动态集合

但我们与其尝试理解这么晦涩的文字,不如打开你家的碗橱看看。
这是你家的碗。为了节省空间,它们被堆了起来。
此时,我们想要放入一个碗,就只能在最上面放;同样的,拿出一个碗,也只能从最上面拿。如果你想拿一个碗,但它的上面还有碗,你就必须将它上面的碗全部拿开。
最先放进去的,最后才能被拿出来。这就叫先进后出。那换一种说法,就是后进先出。
你家的碗堆,就是一个栈。

队列

队列是一种先进先出的动态集合

有了栈,这句话就应该很好理解了。
如果还是不太明白,那就去热门景点排下队吧。

数组

我们来画一张表格。这张表格就是一个数组。表中存着物体。
根据表的不同,数组的类型也不同。
只有一列的是一维数组,和一张正常的表一样的是二维数组,变成一排排柜子的就是三维数组。\r\n四维及以上的…尝试去类比一下吧。

链表

链表是一种各对象按线性性序排列的,由对象指针决定的数据结构

链表,不是一张表,而是一条链。
既然如此,那我们就来创建一条铁链。
只不过,这条铁链有些特殊——它上面的每一条铁环后面,都有一个钩子。
这个铁环,就是存储的对象。而那个钩子,就是指针。但“指针”这个东西,听起来有点不那么平易近人,我们把它理解为一个“向导”好了。
当两个铁环钩在一起时,我们就可以通过前面铁环的钩子,找到下一个铁环。要注意的是,我们只能往有钩子的那边找。
要向里面插入或取出一个铁环都很容易:从钩子处打开,放入或取出铁环,再钩回去。
根据钩子设计的不同,链表还可以继续分类。
前后都有钩子的叫双向链表,首尾钩在一起的叫循环链表。

图和树

打开你手机上的地图,你就获得了图。
但这幅图好像有点太复杂了,我们来简化一下。去除路两边的所有建筑物,把路变成一根线,十字路口变成一个节点。这就是图。
存图有两种方式:邻接表和邻接矩阵。

邻接矩阵

我们创建一张表,上面横、竖标上每一个节点。如果两个节点间有路可以走,那我们就将表中对应的值设为一个非零的数。
这个数可以什么意义也没有,也可以表示它们之间的距离、路的权重等。就是这么简单。
但是,如果路比较少,节点比较多的时候,这种方法就太占空间了。一张纸上几乎全是0,什么作用也没有。

邻接表

这种时候,我们就要用到邻接表。
还记得上面讲过的链表吗?它最大的好处就是可以有多少要多少,节省空间。
这个时候,我们就在每一个节点上都挂一串链表,链表中就存储着从它能走到的节点。
但是,它虽然省空间,找起路来却很麻烦。毕竟,你要一条链走到底,才能知道某个节点在不在这条链上。

如果我们规定,在一幅图中,两个节点间只能有一条通路(注意,是通路,间接能到达就算),那它就变成了一棵树。
为啥叫树?我们把它倒过来,像不像校门外那棵掉光叶子的树?
(反正我觉得不像)
但树有一点不同:它有先后次序。从上到下,和下面那一层某个节点连着的,上面一层的节点,便是它的“父亲”。
一般来说,我们通常采用链表存树,单独存父亲。

end

当然,这些只是最基础的数据结构。从它们衍生出的,还有:红黑树、B树、链式前向星、斐波那契堆、van Emde Boas树……
而今后,还会出现为解决其他问题而诞生数据结构,等着我们去探索。