数据结构拾遗
一 序
常感喟大二的日子,初学数据结构的时候,曾有个念头萦绕于心:既然成熟的数据结构,便都如此(诸如线性表、树等),已经定型,为何不送入工具词典,就当工具一般需要时查一查如何写,却还要单独开一门课?
时光流逝,大四了,几经回首,刹那间觉得往日的错误的会意,故准备小加整理,送我天下朋友,认真体会数据结构的精要,为此行业,为你我之事业尽力耳。
数据结构为何重要?
为什么不把它送工具词典?为什么,众多网友谈起,都一致认为它是计算机专业与非专业的一个很好的分水岭?学习它,当报何种态度?乃至成什么状态?
若干年前,流行一个公式:
程序=算法+数据结构
我想大家都是熟悉的。这是一个基本的视角,来看待我们的程序。程序是我们计算机专业人员面对现实问题给出的一个模型,一种解决方案。在这个模型中,数据结构是基本因素之一。
这不是偶然的。数据结构,研究的是数据的存储与组织形式,计算机即使为巧妇,也绝对离不开它要处理的数据。数据组织,将深刻的影响你的解题思路,这是上述公式的意义。
如果你看一看现在的大学计算机专业的教学计划,你就会发现这个公式的烙印,还是相当明显的。记得去年还与人争论,大学应该以什么语言为教学语言,结果我是c++的卫道者,现在看来,一门计算机语言,目的不在于让你学结构化程序设计而自卑,也不在于让你学面向对象程序设计而自傲,目的只有一个:让你在与计算机交流的过程,体会计算机解决问题的方式!
当你意识到这一点,以后的路,其实你就可以慢慢的自己走了。
这“以后的路”,比较关键的两点就是算法与数据结构了。数据结构,是让你体会计算机解决问题的方式之途中又一关键站,深化理解计算机解决问题的方式与其中的艺术性,是我们学习这门课程的根本目的。可惜,当年身在庐山中啊。
以此态度,学习数据结构,学习数据组织对问题的解决之深刻影响,为你我之责任。
举例说明。
例1, 排序问题。大家都知道,基于关键码直接比较的排序算法中,平均效率比较好的一个是快速排序。然而对于下面的数据,存储若干String的数组,要求对所有的String进行排序,应该如何做?
在此基础上排序,问题在于移动String,会对排序的效率有很大影响;估计时,除了N,还得考虑String的平均长度M,读者可以做一做这项工作。
但是,我们可以考虑改变数据的组织形式,采用更有效的数据结构,比如对本问题,如果要建 立在已给的数据结构上,我们可以加入一个数组索引,形成如下数据结构:
仅对作为访问String之根据的指针进行排序,String的移动问题不是给解决了吗?
例2, 排序二叉树的不平衡问题与Trie结构。
显然大家知道,排序二叉树的深度,与建立它的序列中的序有很大关系。比如你拿序列
2,7,24,33,36,47,125,324
来建立一个排序二叉树,它的深度竟成了序列的长度。毫无疑问这是个问题。
为何如此,如何解决?数据结构课程告诉我们,原因是排序二叉树是一种基于对象空间分解而组织的数据结构,关键码范围的分解由对象来驱动的。解决方案之一,就是另一种数据结构,避免对象空间分解,改为基于关键码空间分解,则为Trie结构。由后者组织的数据形式,就可以一定程度上避免上述问题。
你现在是否有认同感?
当然,认识、理解计算机解决问题的方式,绝没有就此停止。后面的路还很长。但学习数据结构,就要抱着这样的态度,认识到它的根本性,以及灵活性,去深入的学习,深入的思考。这是一个应有的状态。
网友happycock 曾经深入的讨论过数据结构(大家可以参看他的专栏),自然我也就没有必要详细的去重复。所以我的简短的总结,便叫“数据结构拾遗”,与大家讨论一些普通教材所忽略的,或我认为需要强调的观点,并尽力使它们有趣、有用。
但因个人时间问题,前后或许会有延迟,还请见谅。同样的原因,我不再以程序实现为主,而是尽量的多使用图示说明。当然,也不那么成体系的。
总而言之,我们都承担一份自己的责任,共同进步。由此,或许我有很多考虑不周的地方,间或错误的观点,请大家不要吝啬,指出以免误人。先行谢过。
是为序。