数据结构学习（C++）——线性链式结构总结

 

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

我把以前的代码总结一下，列表如下（因为我画不好图）：

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

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

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

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

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

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

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

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

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

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

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