为什么我们需要数据结构


最近在学习各种数据结构,于是就在想,为什么我们需要数据结构呢? 为什么要设计这么多数据结构?数据结构到底解决了我们什么样的问题?

我们提到 数据结构 时,一般是指计算机科学中的一个概念, 但是从本质上讲,数据结构应该是指对数据的一种组织方式。既然如此,我们没必要非在计算机科学领域中讨论 概念本身,把它放在其它领域中,可能更能加强我们的理解。

就说图书管吧,假如你是一名很久很久以前的图书馆管理员,那时候根本没什么计算机。数据结构?那是什么?

你的任务就是看着图书馆里的一堆书。于是,有一天,图书馆来了一堆书,你把他们堆成一堆,放在馆里。 这时候,有人来借书了,他只能在那一堆书里乱翻,翻来翻去也找不到自己想要的书,因为那是一堆书, 有的书他检查了很多次,有的一次也没检查。

这时候这堆书是一个集合,不方便遍历。

时间长了,抱怨的人很多。

作为一个怕麻烦的管理员,你忍受不了别人的抱怨,于是,你把那 一堆书 变成了 一排书

这下好了,来找书的人,只要从书架左边走到右边,按顺序找就好了。只要书在图书馆里,慢慢找总是可以找到。 但是,随着图书馆的书越来越多,这样找实在是太慢了,因为每次都要从第一本书找到最后一本书。

这时候这堆书是一个列表,方便遍历,但是不方便查找。

时间长了,抱怨的人很多。

作为一个怕麻烦的管理员,你忍受不了别人的抱怨,于是,你把那 一排书 变成了 很多类书

那么,按什么分类呢?按书的大小么?颜色么?退一步讲,分类的依据是什么?

分类是为了加快读者查找书的速度,那么读者查找书的时候,是按什么查找呢?是按书名。所以,我们对书名分类。 按书名分类也有许多种,按书名读音么?按书名笔画吗?按书名字数么?我们很容易想到,按读音分类给读者的压力最小, 也就是查找前的开销最小。否则每次找书之前还要数一下笔画,读者一定又会抱怨。

这时候,我们按读音把书分类,书名第一个字是A的在A书架,是B的在B书架。这下读者查找书的速度大大加快了, 因为一下子就能排除那么多类书,而代价仅仅是想一下书名第一个字的读音。不过,我们马上又发现,有的书架上书实在太多了, 那有什么关系?这个问题我们解决过啊,只要再分类就好了,书名第一个字我们用过了,现在用第二个字。

读者终于大致可以满意了。

这时候这些书架构成了一个查找树,方便查找。

另外,我们注意到,其实对于管理员来说,他的负担是增加了的,比如新来了一本书,如果图书馆是一堆书, 只要把新书扔在那一堆里就好了,如果是一排书,要把新书放在这排书的最后,而如果是分好类的书架, 管理员就要先找到这本书的位置,再把新书放在那儿,而不能随便放。好在分类后,我们找新书位置不会花多久, 假如分好类后,读者查找书方便了,但是管理员要把新书放在合适的位置,需要花一年时间, 那这个分类的方法肯定不是一个好方法。

这告诉我们

维护数据结构很重要。

这时候,我们在不知不觉间居然

设计了一个数据结构

这时候,我们回到开始时的问题,为什么我们需要数据结构?对应上面的故事, 为什么我们要把一堆书变成多类书?简单地说,这样可以使找书的过程变快。 这正印证了维基百科词条中的那句话。

数据结构是计算机中存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来最优效率的算法。

回头想想,从一堆书变成多类书的过程,其实就是数据的组织方式发生了变化。我们来抽象一下整个过程。

那么,关键的地方就在于:

根据操作O,找到性质P,设计数据结构S,使S有性质P,同时使额外信息EI,额外操作EO尽量小。

所以,无论是设计数据结构还是学习数据结构,都要弄清楚,

下面我们探讨一些基本数据结构的特点

数组:数组的关键性质在于元素位置可以通过简单计算马上得到,这个关键性质为随机访问提供了很大的 便利。如果数据大小需要动态扩展,那么使用数组是不方便的,因为动态扩展难以维护数组的关键性质。

数组之所以拥有“元素位置可以通过简单计算得到”这个性质,在于数组在内存中是一片连续的区域,这样 知道数组第一个元素位置,知道每个元素大小,通过一次加法,一次乘法,就可以知道第N个元素的位置。 如果数组需要动态扩展,如果这片连续区域相邻的地方有可用内存,那么额外操作是分配这块区域给数组, 如果相邻位置没有可用内存,需要另找一片足够大的连续区域,作为新数组的位置,同时还要把已有数据 复制过去。

链表:链表的关键性质在于元素之间的连续关系使用数据保存起来,这个关键性质为动态扩展提供了很大 方便,新添加元素只需要分配一个结点,然后存储一下表头结点的位置,就维持了链表的关键性质。链表 不利于随机访问,因为元素位置无法通过简单计算得到。

链表的结点在内存中的位置是不连续的,结点之间的关系用数据来存储,所以不能通过简单计算得到第N 个元素位置,只能从表头开始,一直走到第N个元素,才找到位置,这样的额外操作花费太大,所以如果 算法需要随机访问,那么使用链表是不合适的。链表唯一可以直接访问的就是表头了,所以链表适合实现 后进先出队列。

如果需要根据结点内容查找一个结点的位置,那么数组和链表都不太合适,因为他们的关键性质中没有包含结点 内容与位置的关系,所以你根据结点内容很难查找到结点位置。在二分查找中,算法需要一个已经排好序的 数组,原因就在于,排序之后,元素的内容与元素位置之间建立了关系,另外,二分查找需要有随机访问某一 位置元素,所以已经排序的数组就非常适合作为二分查找算法的数据结构。

但是,数组不利用动态扩展,链表利于动态扩展,但是又不能随机访问。我们仔细想想,二分查找的关键思想 在于每次比较一个元素后,就可以排除一部分元素。所以,问题的关键不在于能不能随机访问,而在于比较 一次后,能不能排除一部分元素。我们来看下一个数据结构:二叉查找树。

二叉查找树:二叉查找树的关键性质在于:比根结点小的元素都在左子树中,比根结点大的元素都在右子树中。 它的关键性质体现了内容与位置的关系,并且每次与根结点比较后,我们就排除了一个子树, 所以它方便查找。另一方面,元素之间的关系是用存储的数据来表示的,所以,利于动态扩展。

在添加新元素时,二叉查找树需要的额外操作来保持它的关键性质,这个额外操作其实和查找元素的代价是一样的, 它比数组添加元素容易,比链表添加元素困难。

故事,有些讲不下去了,感觉还是理解的不够,就到这里吧。今后又了新的感受,再补充。

comments powered by Disqus