从新视角来看待旧问题，则需要创造性的思维——爱因斯坦
数据结构的教与学经历
六七年前上数据结构课时，驾轻就熟地依然按照一贯的讲法上课。上了几次课后，收到班上一位同学的E-mail，信中说：“我自己是特别热爱写程序的。一方面我很熟悉电脑，软硬件都有涉猎，所以学起来就不缺基础的相关知识（像内存、寄存器、电子电路等等这些都很熟悉）；另一方面我好像很能适应，也很喜欢这种思维方式……但好像班上不少的同学对数据结构的学习理解和接受起来还是比较困难的……”
教授数据结构的课程也有十余年了，一直以来，学生们总是认为数据结构不是一门容易学的课程，“在众多的专业课中，数据结构被很多学生认为是一门很难学习的课程。”[1]虽然我在学校读书时没有学过数据结构的课程，只是因为后来要教书，才自学的数据结构。在自学的过程中，也并没有觉着内容怎么难啊，这是怎么回事呢？
仔细回想一下自己学习与工作的经历过程，或许就是来信的这位同学说的，是因为在学习数据结构书本知识之前，已经有了较强的编程的技能、一些数据结构实际应用的先验知识吧。比如，在研究所工作时首次参加的软件开发项目中，就有多进程、链表、队列、散列等的实际应用，虽然在学校并没有学过这些概念，而是先接触到实际项目中要处理的问题，再看到其他程序员的具体算法处理和程序实现方法，从实际的问题切入，就比较容易理解相应的数据组织形式和对应的算法，等到后来再接触到书本的理论知识，就有一种一通百通，豁然开朗的感觉。还有一个原因是在软件开发过程中逐渐熟悉并掌握了程序调试方法，对例程通过跟踪的方法，很容易弄清执行的路径和结果，对算法的设计和实现的理解也起到了事半功倍的效果。
回头来看学生们学习的教科书，概念的介绍是传统意义上的叙述方式，抽象度很高，但从实际到抽象、从抽象到实际的过程介绍不足，即感性认识不足，抽象就难以理解接受。“现在有一个不好的倾向，就是教材或课堂过于重视抽象化的知识，忽视应用背景。数据结构的教材是这一倾向的代表。这对入门阶段的学生来讲是不适宜的，因为学生难以走进所涉及的抽象世界，最终表现为不知道在讲什么。”[2]
再看我的学生，既没有实际软件开发的经验也没有熟练的编程调试基础，对数据结构结构没有感性认识，先接触的是那些抽象的概念，感到理解和接受困难也就可以理解了。邹恒明在《数据结构：炫动的0、1之弦》一书中指出，对于很多人来说，数据结构的概念并不难，真正的难点是：
（1）如何实现从数据结构概念到程序实现的跨越（即如何实现一个数据结构）；
（2）如何实现从实际应用到数据结构抽象的跨越（即如何利用数据结构解决实际问题）。
对于我来说，仅仅在学校学了一点点程序设计语言（记得所有上机时间加起来不超过20小时），没有任何数据结构的知识，刚出校门就参与了历时三年多后来获得国家科技进步三等奖的大型软件开发工作，以及后续多个电信用户单位的实际软件安装、应用调试和维护工作，亲历了实现了上述两个“跨越”的最实际生动的案例。虽然项目的开发过程非常艰苦，有在用户单位调试现场连续大半年的天天加班到深夜、第二天依然要正点到机房的超负荷工作，有通宵的跟踪调试，有24小时在线系统内存泄漏的巨大压力，有上线后双机备份系统同时崩溃争分夺秒找bug的惊心动魄，等等。应该说自己是很幸运的，虽然在学校仅仅学习了一点点编程的概念，但在工作中根据需要自学和向同事学习了很多新知识、经验和技巧，这样的实践磨练，对后来的程序设计类课程的理解和教授，是非常有益的。
学习数据结构困难的症结所在
回想与总结起来，之所以要有上述两个鸿沟要“跨越”，也是由于学校的传统教科书教法和实际的应用要求脱节造成的。
弗里德里希?威廉?尼采曾写道：“人们无法理解他没有经历过的事情。”[3]换句话来说，我们只接受与过去早已理解的事物相关的信息。这是一种比较学习的过程，在这个过程中，大脑要寻找每条信息之间的联系，借助以往经验来理解新事物[4]。
“欧拉认为，如果不能把解决数学问题背后的思维过程教给学生的话，数学教学就是没有意义的。现代计算机实质上的发明者莱布尼兹也说过：在我看来，没有什么能比探索发明的源头还要重要，它远比发明本身更重要。从小到大，我们看过的数学书几乎无一不是欧几里德式的：从定义到定理，再到推论。这样的书完全而彻底地扭曲了数学发现的真实过程。目前几乎所有的算法书的讲解方式也都是欧几里德式的，每一个推导步骤都是精准制导直接面向数据结构目标的，实际上，这完全把人类大脑创造发明的步骤给反过来了。对读者来说，这就等于直接告诉你答案和做法了，然后让你去验证这个答案和做法是可行或成立的，而关于答案和做法到底是怎么来的，从问题到答案之间经历了怎样的思维过程，却鲜有书能够很好地阐释。对于这类知识讲述（欧几里德方式）方式的批判，西方（尤其是在数学领域）早就有了。”[5]
传统数据结构教科书的一般模式都是给出问题，然后直接给出算法，而实际上要用计算机解决问题，必须要考虑的处理步骤有：如何分析问题中的已知信息，如何提炼数据及数据间的联系（数据的逻辑结构），如何选用合适的存储方式（数据的存储结构）将逻辑结构存到计算机中，然后在存储结构之上按照自顶向下逐步细化的方法给出算法，这才是真正解决实际问题的思维方法和步骤，也是软件开发中实际采用的方法。传统教科书的问题在于没有一个思维过程的引导与分析，致使概念论述、实现细节有余，设计实现过程描述不足，让学生看到的只是一个个问题具体的详解，而把握不住算法设计的总方法和原则。
本书尝试从学以致用的角度，注意给出问题或算法的知识背景或应用背景，增加一些在实际软件开发中的算法应用背景或实例；强调算法的分析方法、设计思路、给出重要算法的测试及调试分析，弥补上述传统教科书中的不足。教学生以“软件开发的方法”处理问题，使学生容易理解并掌握它，在实际的软件开发过程中能灵活地选择适当的逻辑结构、存储结构及相应的算法，设计性能优、效率高、可读性强、易维护的程序，达到数据结构课程最终的目的。
程序设计与数据结构的关系
我们在学习数据结构知识之前要有程序设计的基础，那么我们先来看看与编程相关的问题。
什么是编程？编程不仅仅是对语法的掌握，还涉及下面的诸多方面：
（1）程序的解题思路——算法是基本运算及规定的运算顺序所构成的完整的解题步骤，是程序的灵魂，算法的优劣直接影响程序的效率。本书的算法描述方法见稍后的说明。
（2）程序的运行速度——程序运行的速度受很多因素的影响。用户对程序的运行速度往往是有要求的，如实时响应系统。
（3）程序的运行空间——代码运行需要相应的内存空间及相关运行环境。在有些应用场合，对程序占用空间是有限制的，如嵌入式系统。
（4）代码规范——代码要按照一定的规范格式书写，以保证代码的一致性，便于交流和维护。
（5）程序的结构—— 一个功能复杂的程序由多个功能相对独立的模块组成。模块内高内聚，模块间低耦合，是判断程序结构是否合理的标准。
（6）模块接口——模块间的信息交流通过接口完成，模块间信息传递参数的设置应该合理有效。
（7）程序的测试与调试——要有精心设计的测试样例来测试程序是否正确。调试是高效率完成软件产品的有效方法。一个程序高手，也是调试专家，调试的经验方法多数都是实践中得到的。
我们在学习数据结构知识之前要有程序设计的基础，那么数据结构与程序设计间的关系是怎样的呢？应该说数据结构是编写规模庞大、逻辑复杂的更高级程序所需的基础。表0.1给出了程序设计与高级编程的特点。
表0.1  程序设计与高级编程
	涉及课程	主要内容	课程目标
结构化程序
设计	程序设计基础类课程	语言语法形式、语句使用规则
模块设计思想	编写简单程序
解决简单问题
高级编程技术	数据结构	数据的抽象思维方法	编写规模庞大、
逻辑复杂的程序
		算法的规范声明、算法的性能分析、算法的性能评价	
	软件工程	部件（模块）设计思想、软件工程思想	
	……		
程序设计的首要问题是模块划分及相关问题，另一个重要方面，是把要解决问题的信息转换成计算机能认识并接收的数据，这一转换过程就是数据的抽象过程。要处理规模庞大的复杂问题，必须掌握数据的抽象思维方法，同时还要熟练掌握算法的规范声明、算法的性能分析、算法的性能评价等诸多技能。
数据结构与其他课程的关系
作为一门重要的专业核心必修课程，“数据结构与算法”课程既是对以往课程的深入和扩展，也为深入学习其他专业课程打下基础。课程中排序问题算法以及基本的树、图等数据结构，是计算机科学的基本功。B+树、散列（Hash）等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等重要专业课程的基础。本课程在计算机学科中与其他课程的关系如图0.1所示。
 
图0.1 “数据结构与算法”课程在计算机学科中的重要地位
数据结构的重要性
商用程序员肖舸在他的博客中写道：“这么多年，我做过游戏、通信、工业控制、教育、VoIP、服务器集群等各个方向的项目，不可谓不宽。
但是我知道的是，其实我都是在用一种方法写程序。那就是从最底层的数据结构和算法开始做起，用最基本的C、C++语言开发。用来用去，还是那么几个数据结构，队列、堆栈，等等。
这好比武侠小说里面的内功，内力修好了，学招式，非常容易。但如果没有内力，练再好的招式，见到高手就软了。一力破十慧，就是这个道理。在绝对的实力面前，任何花招都是没有用的。”[6]
对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之一；数据结构是国内外许多软件开发机构要求考核的基本课程之一；IT业公司面试或笔试考核的绝大部分内容是数据结构或算法；数据结构也是计算机科学与技术、软件工程等专业研究生考试必考科目。
数据结构会过时吗
电子计算机自20世纪四十年代诞生以来硬件上不断更新换代，软件也是同步发展的，作为软件的一个分支程序设计语言也从机器语言发展到了第四代，但无论软件如何发展，无论开发工具如何进步，只要我们的计算机还是基于冯诺依曼体系，数据结构和算法仍然是程序的核心，永远不会被淘汰。
学习数据结构和算法并不仅仅要求我们学会如何使用和实现某种数据结构，更重要的是学会分析解决问题的思想和方法。
本书关于算法与程序实现增加的内容
在基础数据结构——线性表与运算受限的线性表栈与队列章节中，特别增加了下列内容。
1．增加测试样例的设计
从程序健壮性的角度出发，测试样例的设计是开始程序设计就应该考虑的一个重要内容。一般的程序设计与数据结构教科书很少考虑测试样例问题，本书在最初基本的算法设计中，给出了基础程序的测试样例设计，也是让学习者以专业的方法学习程序设计，养成良好的设计习惯。
2．增加函数结构的设计
对初学者而言，在学习数据结构时，程序设计语言基础并不扎实，特别是函数结构的设计不熟练。根据给定的功能、输入输出信息，在调用与被调用的函数关系中，信息是怎样传递的，往往存在多种可能的选择，该怎样确定合适的形参类型、函数类型，初学者经常会无所适从，从而造成编程困难。根据这种情况，本书特别给出了典型数据结构运算的多种方案实现，在同一问题不同函数结构设计的比较中，让读者发现各种信息传递的方式和特点，巩固和熟练编程知识和技巧，达到理论与实践的统一。
函数结构样例分别见表0.2和表0.3。
表0.2  函数结构样例1
功能描述	输入	输出
顺序表中查找给定的值
LocateElem_Sq	顺序表地址SequenList *	正常：下标值int
	结点值 ElemType	异常：?1
函数名	形参	函数类型
表0.3  函数结构样例2
功能描述	输入	输出
顺序表中取给定下标的元素值
GetElem_Sq	顺序表地址SequenList *	返回	正常：1
	下标int		异常：0
	（结点值 ElemType）	结点值ElemType
函数名	形参	函数类型
说明：当函数中的输入和输出项中的内容一样时，表示函数的返回信息是通过形参的址传递方式，而非return方式。如表0.3中函数结构样例2中，输入输出都有“结点值ElemType”项，表示是形参采用“地址传递”方式。
3．增加重要程序的调试
程序设计的过程也是一个测试与调试的过程，程序的编与调是密不可分的。对于初学者而言，若调试不熟练，容易丧失继续学习的信心。根据多年的教学经验，若有程序调试演示，则相关程序比较容易掌握，特别是在学习链表等内容时，光是解释数据结构、结点联系，学生总觉得抽象难懂，若通过演示调试，观察各结点间的联系如何动态建立、消除等，则生动直观，一目了然。由于调试过程步骤较多，学生看过了明白了，但要再回想并模拟跟踪过程，则是不容易的事情，所以本书把一些重点例子的程序跟踪过程记录下来，以便学生学习。本书所有的源码均以C语言编制，并在VS IDE环境下通过调试和测试。
4．算法描述方法
算法描述按照下面的顺序给出（主要用于编程最基础的线性表部分），内容详见1.5.3节。
1）测试用例设计。
2）数据结构描述。
3）函数结构设计。
4）算法伪代码描述。
5）程序实现。
6）算法效率分析：
注：#define TRUE 1
    #define FALSE 0
数据结构课程简介
用计算机解决实际问题，首先要做的事情就是要把涉及问题的相关信息存储到计算机中，也就是需要把问题的信息表示为计算机可接收的数据形式，然后根据问题处理功能的要求，对存储到计算机中的数据进行处理。归结为一句话，可以这样说，用计算机解题首先要用合理的结构表示数据，然后才能根据相应的算法处理数据，而数据表示和数据处理正是数据结构学科要研究的内容。
“数据结构”主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。
通过本课程的学习，学生能深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便在实际的软件开发过程中灵活的选择适当的逻辑结构、存储结构及相应的算法，设计性能优、效率高、可读性强、易维护的程序，解决实际问题。
数据结构是实践性很强的一门课程，本课程的特色就是注重实践活动。通过大量上机实验，能加深对课程理论知识的理解，增强学习的兴趣，提高计算计算法思维逻辑能力，为以后的学习和工作打下坚实的基础。
本课程的基本要求如下：
?  了解数据结构及其分类、数据结构与算法的密切关系。
?  熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
?  掌握设计算法的步骤和算法分析方法。
?  掌握数据结构在排序和查找等常用算法中的应用。
?  初步掌握索引技术。
?  了解经典算法。
本书的组织结构
本书共分9章。第1章介绍数据结构和算法的基本概念和算法分析方法。第2章至第6章从软件开发的角度，通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、调试等环节，分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行分析和讨论。第7章排序技术介绍常见的数据排序方法，第8章索引查找技术介绍数据的查找方法，第7、8章的内容是对数据的典型操作方法的介绍。第9章经典算法，介绍一些常见的如递归、分治法、动态规划、贪心法等经典算法。
前言、第1章至第6章由周幸妮老师完成；第7、9章由任智源老师完成；第8章由马彦卓老师完成；樊凯老师提供了通信等方面的部分专业应用案例；周幸妮对全书进行了统稿。
书中设有“思考与讨论”、“知识ABC”等栏目。在“思考与讨论”栏目中提出问题，引起读者思考，并对提出的问题进行探讨，帮助读者加深对相关概念等的理解，以期活跃思路扩展思维。“知识ABC”栏目主要介绍相应概念的知识、知识背景、算法的发明背景或故事等，以扩大读者的知识面和了解数据结构的应用背景等。有些知识可能专业性比较强，对此可以“不求甚解”，大致了解即可，感兴趣了可以再去查相关资料。
致谢
本书的写作动力，依然是源自于我的学生，起因是09级教改班同学的提议，认为我的授课方式、思路都不错，写出来会别具一格，让大家学习这个课程时能更好理解一些，这部分内容在我的《C语言程序设计新视角》一书中有所提及。
我的动力亦源于父亲的鼓励、家人的支持。感谢铁满霞教授、陈慧婵教授的指点；感谢屈宇澄同学自始而至终的支持和帮助；感谢孙蒙、丁煜、孙舒、孙亚萍、张柯、杨恒杰、吴伟基、黄超、张平等同学的热心帮助；感谢通信工程学院13级教改班、14级卓越班，空间科学与技术学院13级实验班同学们对本书初稿讲义提出的各种有益的意见和建议。
所有和同学们、同事们的讨论都让人受益匪浅，这些讨论或开拓了视野，或引起了深入思考，所有的一切都是一种成长与完善的历程。
感谢曾经给予我很多帮助、一起辛苦工作的同事们；感谢我有趣的人生经历；感谢我可爱的学生们；感谢所有关心和帮助我的人们。
感谢Bandari的April，每天伊始，美妙的乐曲让人在纯净、安定、温暖的情绪中开始一天的写作。
感恩一切。

周幸妮         
xnzhou@xidian.edu.cm  
2015年春于长安