首页 > C/C++语言 > C/C++数据结构 > 数据结构学习(C++)——线性链式结构总结
2006
12-08

数据结构学习(C++)——线性链式结构总结

 

在开始写这些文章之前,我曾经有个想法,能不能以单链表为基础,完成所有的线性链式结构?实践证明,是可以的,就像你看到的这样。我做这个尝试的起因是,看不惯现在教科书凌乱的结构:罗列了一大堆ADT或者是templat class,好像这些都要你去记似的。殊不知,只有提取共性,突出个性,才能更明显的表现出各种数据结构的差异,显示数据结构的进化发展的过程,看出变化的内在需求。借用《C++沉思录》作者的一句话,“避免重复”。在以后的应用中,你可能需要单独的写出一个class——打个比方,为了实现栈,你没有必要先写一个线性表,然后再继承得到栈;但假如你已经有了一个线性表了,你还需要另起炉灶再重写一个栈吗?对于一本书来说,本来就是假定读者在看后面的章节的时候,已经对前面的章节有所了解;即使象《C++沉思录》这样的从以前发表在杂志上的文章整理出的书,也能看到循序渐进的影子。如果在后面的章节又把前面的东西重复一遍,我只能认为他是在骗稿费。


我把以前的代码总结一下,列表如下(因为我画不好图):



















单链表(List<Type>


多项式节点


表达式节点


修改部分操作


添加向前指针域


限制操作


多项式


表达式


循环链表


双向链表


栈和队列


我们从单链表出发,通过对应的变化,得到了绿色的一行。突然之间我觉得自己很可悲,看了100多页书,最后得到竟然只是这么一个表。不管怎么说,这也是我看了这么多页书的结晶,让我们看看能从这表里得到什么。


首先,单链表是一个容器,他是为了存取数据而存在的。如果里面存的是多项式的节点,那么他就是一个多项式;如果里面存的是表达式节点,那么他就是一个表达式。这让我想起了以前曾经困扰我的语义问题:多项式究竟是一个存了多项式节点的单链表呢,还是包含了一个存了多项式节点的单链表?现在我的想法是,这并不重要,怎么理解都行。


其次,循环链表、双向链表、栈和队列也是容器,只是具体的操作实现或者对外的行为和单链表有所差别。但是内在的存取机制是相同的,或者还有更多的地方相同,我们应当最大限度的利用这些相同之处。


上面的提法好像很无聊——他们当然是容器,还用你小子废话吗——请注意我下面的问题:数组是容器吗?你做过仅针对数组里的元素操作的练习吗?你做过数组应用的练习吗?现在请你把数组换成单链表,检查一下有没有答案变化了。这真是对大学教育的一个讽刺,我们学完单链表,竟然只会插入删除节点,合并两个链表,将一个单链表逆序,等等;我们居然不知道为什么要学这个,怎样用他。最终的结果就是,当我们走向工作岗位后,又如获至宝的捧起这本书,然后用语重心长的口气对学弟们说:“数据结构很重要,你一定要好好学”。


或许你说这没什么,大学里许多的功课不都是这样的吗——临到用时才发现重要。是的,习惯成自然,但是习惯并不都是好的,我们也并不是一定要“书到用时方恨少”,然而,这并不只是取决于我们的年少“不”轻狂。让我们回想一下我们的教科书,一章一节,井井有条,丝丝入扣,当然这是写的好的,其他的就是追求这个目标,画虎不成反类犬。前面的章节为后面的章节铺垫,逻辑推理性极强,请不要认为我这是夸那些书,你不觉得和看那些论文一个感觉?你所得到的仅仅是“是什么”,“我说的是有道理的”;你能看到“为什么有这些”吗?


对于论文,我不能要求作者给出他的思维过程,而他写论文的目的也仅仅是为了告诉别人:“我研究出这个了,你们看,我说的是有道理的”,并且,看他的论文的人也有和他相当的知识构成,我想,现在看我文章的人也不会对哲学论文感兴趣(即使你可能会看黑格尔的书,你也决不会对现在那群玄人的梦呓感兴趣;正如那群人虽然用电脑写文章,你想要跟他们说内存管理,他们也会把耳朵塞起来)。


对于教科书,仅仅用论文的要求来要求,显然是太低了。首先,书所面对的读者都是对这门课程一无所知的人——你假设和论文一样,都有一个基本认识了,我还学你这门课干什么,我直接看最新的论文好不好。其次,写作目的是让读者了解这门学科,认识这门学科的规律,最终能够运用这门学科,甚至有所发展。正如学写字先描红,不先模仿,怎么创新呢?如果连现有的结论和成果都不知道来龙去脉,谈何再有新的突破呢?


教科书不是论文,当然不能象写论文那样来写,但现在国内的作者好像乐此不疲,就好像不写得层次严谨就不能体现自己功力扎实似的。这也是为什么越来越多的人选用国外的教科书,即使他们的英文并不好——当然,不少人是借此学习英文。


正如哲学上讲的,只有遵从人类的认知规律,人们才能更容易的认识新事物。但论文的写作,恰恰是对这个过程的逆向总结——他是和人类的认识过程相反的。而教科书为了达到他传授知识的目的,就必须遵从人的认知规律,而决不是象论文那样反其道而行之。


这样看来,数据结构的书决不应该象现在这样来写。从数据结构的发展来看,他是应问题的需要而出现的,并为解决问题而服务。换而言之,对于数据结构的讲解,应当把重点放在算法上面,在各种典型问题上提出新的数据结构;最终得出的认识是,为了特定的问题和算法,而选用特定的数据结构;为了改进算法而改进数据结构;为了新的问题和算法而创造出新的数据结构。而决不是象现在这样能得出的认识:我学了数据结构能解决什么问题。乍一看,好像没什么差别,但现在这个认识,你不是数据结构的主人,你只是数据结构的奴隶。


最后举个讽刺性的例子。我最初知道数据结构的时候是高中,那时我只会BASIC,数据结构的概念源自一本名叫《中小学生电脑操作与程序设计》的书。那本书使用的是GWBASIC,实现了大学教科书里的数据结构:链表、栈、树、图。来看看他的目录:八皇后、迷宫、骑马游世界、链表和约瑟夫、树和背包、一笔画、追捕罪犯、四种颜色就够了。——我们甚至在中小学时,用BASIC就可以清楚的有趣的讲解数据结构;现在居然让大学生学完之后,甚至连中小学生的水平都不如。我不知道你怎么看,但我觉得,至少,我们的教科书应该改变一下写作的风格了。


留下一个回复