论文部分内容阅读
摘要：在大学计算机专业课程中，“数据结构”被学生广泛认为是一门难学、难懂、难实践的课程。造成这种现象的原因很多，除了数据结构本身抽象，有一定的难度外，其与“算法”内容的混杂是一个重要原因。众所周知，数据结构常与算法混在一起进行讲授，有的学校的课程名就叫“数据结构与算法”。数据结构这种与算法的缠绕由于时间已久，大家已习以为常，并没有细想其合理性。但我们经过多年的实践发现，此种缠绕带来的利益十分有限，却给数据结构课程的教学带来了障碍。本文详细分析了这些缺陷并提出了分而治之的解决之道。
关键词：数据结构；算法；缠绕；分而治之
一、问题陈述
“数据结构”是计算机专业的基础课程，一些与计算机联系较紧密的专业也将其列为必修或选修课。该门课程由于涉及学生人数多和在程序设计中的基础地位，受到了各方重视。
但与其他课程都具有相对独立性不同，“数据结构”与另外一门课程之间有着紧密的缠绕关系，这另外一门课程就是“算法”。大部分学校都将算法设计与分析的部分内容纳入数据结构课程里，有的学校在课程名上就注明是“数据结构与算法”。在此模式下，这门课的一部分内容为数据结构，一部分为算法；或者某部分内容既讲数据结构也讲算法。国内外的数据结构教材大多包含部分算法的内容[1，2]，而算法书籍也用大篇幅来论述数据结构的内容。例如《算法导论》和《计算机算法》就有专门的篇幅用来讲数据结构[3，4]。
数据结构这种与算法缠绕的做法由于时代久远，人们已习以为常，并不觉得有什么问题。相反，很多人觉得这种缠绕很有道理：算法与数据结构联系紧密，讲数据结构离不开对算法的讨论，讨论算法的时候又经常牵扯到数据结构。因此，将算法的部分内容放在数据结构课程里面似乎顺理成章。自然，算法课程里面讨论数据结构也合情合理。甚至有人认为，数据结构离开了算法将无法讲解，而算法在离开数据结构时也难以为继。
但这种缠绕真的明智吗？数据结构离开算法真的不能讲解吗？既然计算机专业的其他课程都相互独立，这两门课程的缠绕怎么都显得有点奇怪。如果缠绕在一起有利于学生学习掌握这两门课程，那么缠绕当然可以。不过，我们多年从事数据结构和算法课程的教学实践表明，这种缠绕对学生的理解并没起到什么特别有益的帮助，却给数据结构和算法的教学带来了如下五个方面的负面影响：逻辑混乱、内容残缺、衔接困难、阐述肤浅、心理误导。
1．逻辑混乱
首先，缠绕让学生觉得二者不可分割，甚至是一回事情（的两个方面）。可事实并非如此。诚然，数据结构总归要支持某些运算，但算法却并不一定要运行在某种数据结构上。其实，在人类发明数据结构甚至计算机以前，算法就已经存在了。如果因为数据结构支持某些运算或者算法在实现时需要用到数据结构来为缠绕辩护，那么操作系统用到很多算法，是不是也要将算法和操作系统合并为一门课而称为“算法与操作系统”呢？编译器用到更多的算法，并且在实现时大量使用数据结构，是否要将编译器、算法、数据结构合并为一门课呢？显然，这种因为关联就要合并的观点是值得商酌的。退一步说，如果真要缠绕，数据结构的缠绕对象应该是程序设计，因为数据结构是程序设计的一种必备工具，它就是为程序设计而出现的。
因此，将数据结构与算法缠绕并没有逻辑或历史依据，也不是学习关联知识的必由之路。缠绕导致的结果就是逻辑混乱：让人将本来是相对独立的知识领域理解为无法分割的同一领域。
2．内容残缺
缠绕的另一个缺点是导致数据结构课程的内容出现缺陷。由于要花时间讲述部分算法内容，很多重要的数据结构就没有时间覆盖。例如，跳转表、费波拉契树、费波拉契堆、幂堆、分离划分集、数据结构扩展技术等内容在绝大部分的数据结构课里并不涉及。这些知识的缺乏对后续课程的开展或学生将来的工作有着不利的影响。比如，由于通常的数据结构课程并不讨论幂堆及菲波拉契堆，导致在其他领域讨论最小生成树、最短路径等问题时出现基础不够的情况。对于从事存储技术的学生来说，数据结构如果没有覆盖B树、K树、最优树的话，则其在理解存储系统设计的时候将面临困难。在今天存储技术日益重要且热门的情况下，不少学生都希望能够成为存储领域的人才。而数据结构的这种缺陷不得不说是一大遗憾。
3．衔接困难
鉴于定位（并非专业的算法课）和时间原因，数据结构课程对算法内容的讲解浅显残缺。这样，绝大部分学校在开设数据结构课的同时还通常开设算法课。此种情况下，数据结构与算法的缠绕导致两门课程的内容衔接出现混乱。例如，排序到底是应该在数据结构课讲，还是应该在专门的算法课讲？还是两门课都讲呢？查找与搜索呢？图的算法呢？由于没有一个众所公认的统一指导原则，两门课程的教师和教材作者都根据自己的爱好随意安排内容，导致很多内容或重复或遗漏。其中，排序、查找、图成为两门课程重复最多的部分。
当然，重复本身并不一定产生问题，只要侧重点、角度、深度不同。问题是，由于缺乏统一安排，现实中两门课之间并不存在默契。有的数据结构教师在讲算法时会偏重实现，有的会偏重理论，讲解同一个算法的深度因教师个人素养、性格不同而不同。这使得后面的算法课在内容安排上无所适从：如果数据结构对算法讲解得浅，算法课就需要从深度上重复讲解前面的内容；如果数据结构对算法内容讲解得很深入，则算法课就不需要重复讲解同样的算法。但由于数据结构教师和算法教师通常不是同一个人，这种默契与合作往往不能实现。
4．阐述肤浅
缠绕除了对夹塞进来的算法内容讲解肤浅外，对数据结构本身内容的讲解深度也受到很大影响。原因很简单：学时只有这么多，又讲数据结构、又讲算法分析，两部分内容都没有时间深入讲解，因而经常是蜻蜓点水，浅尝辄止。一般认为，算法高度抽象且令人生畏，数据结构则高度依赖程序实现且让人反感，将这样两门课程的内容糅合在一起大大增加了对此门课程的逆反程度。而且，缠绕要求教师对两门课程的内容都要熟悉，这无疑增大了培训教师的难度。在缺乏精通这两门课程内容的师资情况下，只能是不断降低讲解深度，仅从表面上阐述，形成一种头痛医头、脚痛医脚的肤浅讲解范式，从而进一步加深了本课程的枯燥与浅薄。
5．心理误导
虽然数据结构课对算法内容的讲解只是皮毛，但大部分教师对这一点并没有进行强调，从而给学生形成心理误导，让学生觉得这就是算法设计与分析。很多学完数据结构的学生认为自己已经学过了算法，导致在后面的算法课上不认真对待，或根本就不再选修算法课。例如，数据结构课程一般会讲解搜索（查找）和哈希（散列），但讲解深度有限：数据结构课程通常不覆盖全域和完美哈希算法，就是讲了，也不太可能会将它们完全阐述清楚。这样，如果学生在后面的算法课里不认真对待，则有可能不会掌握重要的全域和完美哈希算法。
二、应对策略
根据上面的分析，数据结构与算法的缠绕导致了数据结构课程在教学内容和课程设计上的种种缺陷，这些缺陷不利于教学的安排，不利于教材的出版，也不利于学生的学习。我们的调查发现，这些缺陷是导致学生反感数据结构课程的一个重要因素（当然还有其他因素，需另外论述）。因此，对当前的“数据结构”课程进行调整就显得颇为必要。我们的调整方案是采用由来已久的分治战略，正所谓分而治之为上策。
这里的分治就是打破缠绕，将算法内容剔除，集中精力讲解数据结构及其实现。在分治模式下，数据结构覆盖各种结构本身的构造、实现及程序设计应用，而对算法设计与分析不做涉及。当然，由于数据结构总是支持某些操作的，它不可能一点都不涉及算法。例如表结构上的查找操作就与算法里的查找算法关系密切，但这种密切关系并不妨碍二者的分离。数据结构里的算法是就事论事的具体算法及其实现，并不详细或系统论述算法的原则或原理。
三、分而治之为上策
实行分治后，数据结构课程教学所面临的问题都被化解。首先，分治后数据结构与算法课之间的关系清楚，学生不会将它们混为一谈。其次，分治后两门课程内容没有重复，内容安排困难的情况也被化解。再次，课程分解后所产生的额外时间让数据结构课程可以覆盖几乎所有的重要数据结构，内容上的缺陷也不复存在。最后，由于两门课都摆脱了需要讲解对方内容的负担，从而可以更加深入地讲解自身内容，讲解肤浅的问题也迎刃而解。
当然，分而治之也不是说分解得没有半点关系。事实上，在数据结构课程中可以附带提到算法，但只需要提到即可，无需仔细讲解。例如，在讲解数据结构的时候，我们会对不同数据结构的优劣进行比较，而此时可能需要对它们所支持的操作的复杂性进行分析，也就是可能需要算法分析的知识。但我们在这里可以只提供一些感性的分析，即大概论述一下某个数据结构的操作可能时间较长或空间较大，而不用对它们进行精确或渐近分析。这样，就可以在避免论述算法的情况下对数据结构之间的优劣进行比较。
当然，分治策略的实现是有代价的：需要重新编写教材、制订新的教学大纲、教师的水平可能需要提高等。但这些代价是值得的，一旦做到位，以后就顺心应手了。而且，进行此种改革对于所有相关的教师和学生都是一次提升，可以说非常值得。
四、改革的实施及效果
自2008年开始，我们在上海交通大学-密歇根联合学院、上海交通大学软件学院启动了本文提出的分治改革，将数据结构从与算法缠绕的状态下独立出来，并从程序设计的角度重新定位了数据结构课程。这种变革的结果是设立了“程序设计与数据结构Ⅲ”课程，其立足点是与算法分离，围绕程序设计，以程序师的角度看待讨论数据结构。为此我们制订了新的大纲，编写了新的讲义，采用了新的教学方法，并在两年后对实施情况进行了评估。
1．新的教学目标
变革后的数据结构教学目标定为从新的角度阐述和分析数据结构，以一种更为容易接受和理解的“问题驱动”方式进行讲解。通过与算法的适度分离和与程序设计的更加靠近，将数据结构的功能、程序设计实现和具体应用植入学生的头脑中，以使学生能够使用各种数据结构来编写出真实有用的程序和软件。具体目标包括如下一些方面：
训练学生的数据结构思维，使其认识到数据结构的内在优雅和能力；
教授结构化问题解决技术和数据抽象原则；
从架构师和设计师两个角度跨越具体与抽象之间的鸿沟；
帮助学生发觉精巧数据结构给程序所带来的巨大改善；
教授学生如何概括性地评价一个数据结构和程序的成本；
教授学生如何应用数据结构来解决实际问题。
2．新的教学大纲内容
在内容方面，我们将数据结构分为三大类：线性结构、非线性结构、扩展数据结构。线性和非线性结构的含义不言自明，扩展数据结构指的是基于基本数据结构而扩展或构造的结构。这种结构的特点是对某种经典数据结构进行修改或改进，从而能够支持新的实际问题的解决。对与数据结构联系紧密的查找与排序操作，我们将其定位为数据结构上的通用操作。这种定位注重的是操作作为数据结构的自然属性，而不是操作本身背后算法设计的原则和思维。有鉴于此，我们对查找和排序操作的讨论更注重实际实现和各种实现方案对相关数据结构产生及发展的影响，而不在算法战略的设计与分析上花费精力。此外，考虑到现在编程环境的演变，我们留出一章讨论标准模板数据结构。这样就形成了如下所述的教学大纲的六篇内容。
第一篇为结构基础篇，讨论数据结构的背景、来源及基础知识。第二篇讨论时空关系为线性的数据结构，内容包括栈结构、队结构和表结构三章。第三篇讨论数据结构上的通用操作，内容包括查找操作和排序操作两章。第四篇讨论非线性结构，内容包括高级表结构、树形结构、高级树形结构和堆结构四章。第五篇讨论扩展数据结构，内容包括图结构、集合结构和划分结构三章。第六篇讨论标准模板结构。整个大纲不涉及算法设计与分析，不过，需要的时候会向学生提到，对某些结构上面的操作进行精确分析和改进将由后续的算法课程负责。
3．新的教学方法
我们新的教学方法是从（程序）设计师的角度来展开对数据结构的讨论，以“问题”为驱动，以“使用”为轴线，对每一种数据结构的出现动机、发展逻辑、表示方式进行演绎，生动形象地再现了其内在的优雅和哲学。我们注重阐述如何从一种想法转换为一种设计，又如何从设计转化为具体程序，对每种数据结构都辅以程序设计中的实际应用，从而化抽象为具体，帮助学生跨越横亘在高度抽象与高度具体之间的鸿沟。同时我们讨论了所有数据结构的代码实现。这些代码不是伪代码，而是可以直接编译执行的真实代码，进一步帮助学生理解抽象。
例如，我们以现在非常普遍的搜索引擎问题为引导，询问学生通过程序设计来实现搜索引擎会用到哪些数据结构，或者说应该使用何种数据结构才好。立足于由简单到精密的思路，我们先尝试不用任何数据结构，发现无法构建搜索引擎；在用了人人都能想到的数组结构后，虽然可以构建搜索引擎，但效率非常低；我们需要一步步引入构建更为精巧的矢量结构、树结构、索引表、哈希表结构等。这样，通过一个问题，围绕程序设计的实现，我们串起一系列的数据结构，让学生看到了各种数据结构不是凭空出现，而是因问题驱动、经过逻辑上的逐次演进推理而出现，从而帮助学生更加深入并饶有趣味地把握数据结构。
4．新的教材
我们按照新的思路，编写了新的数据结构讲义。该讲义体现的就是本文的中心思想：通过将算法内容剥离，以问题为驱动，从程序设计师的角度对数据结构的来龙去脉和背后原理进行深入、独到的阐述，使数据结构的讨论清晰、实用，并充满趣味和吸引力。
该讲义在经过三届数据结构教学的实践、改善和整理后，已正式定型为教材，取名《数据结构之弦》，将由高等教育出版社于2011年出版。
5．实施效果评估
在改革实践2年后的2010年上半年，我们在软件学院二年级成绩为好、中、差的学生里各随机抽取了5名学生，总计15人，布置了3道程序设计与数据结构编程题对他们进行考核。实际考核中有1名好生因故放弃。在综合了5名教师对14名学生的评价后，学生答题情况被评为好的5人、中的8人、差的2人。与样本选取的好4人、中5人、差5人的情况相比较优，说明课程改革效果明显。
同时，通过对上海交通大学-密歇根联合学院学生的问卷调查表明，学生对数据结构学习的兴趣明显提升，以往的那种反感和腻味已经不复存在。
用分而治之的策略来化解“数据结构”课程与算法内容的缠绕，降低了教学难度，改善了教学效果。通过将算法内容剥离，以问题为驱动，以程序设计为轴线，从程序设计师的角度对数据结构的产生和原理进行深入独到的阐述，使数据结构的讨论清晰、实用，并充满了趣味和吸引力。实践表明，这种改革取得了良好的效果。
参考文献：
[1] Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithms Analysis[M]. 北京：电子工业出版社，2002.
[2] Bruno R. Preiss. Data Structures and Algorithms with Object-Oriented Design Patterns in C++[M]. John Wiley & Sons, Inc, 1999.
[3] Thomas H. Cormen, etc. Introduction to Algorithms (2nd edition)[M]. 北京：高等教育出版社，2005.
[4] Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran.Computer Algorithms (Paperback)(2nd edition)[M]. Silicon Press, 2008: 773.
[责任编辑：余大品]
关键词：数据结构；算法；缠绕；分而治之
一、问题陈述
“数据结构”是计算机专业的基础课程，一些与计算机联系较紧密的专业也将其列为必修或选修课。该门课程由于涉及学生人数多和在程序设计中的基础地位，受到了各方重视。
但与其他课程都具有相对独立性不同，“数据结构”与另外一门课程之间有着紧密的缠绕关系，这另外一门课程就是“算法”。大部分学校都将算法设计与分析的部分内容纳入数据结构课程里，有的学校在课程名上就注明是“数据结构与算法”。在此模式下，这门课的一部分内容为数据结构，一部分为算法；或者某部分内容既讲数据结构也讲算法。国内外的数据结构教材大多包含部分算法的内容[1，2]，而算法书籍也用大篇幅来论述数据结构的内容。例如《算法导论》和《计算机算法》就有专门的篇幅用来讲数据结构[3，4]。
数据结构这种与算法缠绕的做法由于时代久远，人们已习以为常，并不觉得有什么问题。相反，很多人觉得这种缠绕很有道理：算法与数据结构联系紧密，讲数据结构离不开对算法的讨论，讨论算法的时候又经常牵扯到数据结构。因此，将算法的部分内容放在数据结构课程里面似乎顺理成章。自然，算法课程里面讨论数据结构也合情合理。甚至有人认为，数据结构离开了算法将无法讲解，而算法在离开数据结构时也难以为继。
但这种缠绕真的明智吗？数据结构离开算法真的不能讲解吗？既然计算机专业的其他课程都相互独立，这两门课程的缠绕怎么都显得有点奇怪。如果缠绕在一起有利于学生学习掌握这两门课程，那么缠绕当然可以。不过，我们多年从事数据结构和算法课程的教学实践表明，这种缠绕对学生的理解并没起到什么特别有益的帮助，却给数据结构和算法的教学带来了如下五个方面的负面影响：逻辑混乱、内容残缺、衔接困难、阐述肤浅、心理误导。
1．逻辑混乱
首先，缠绕让学生觉得二者不可分割，甚至是一回事情（的两个方面）。可事实并非如此。诚然，数据结构总归要支持某些运算，但算法却并不一定要运行在某种数据结构上。其实，在人类发明数据结构甚至计算机以前，算法就已经存在了。如果因为数据结构支持某些运算或者算法在实现时需要用到数据结构来为缠绕辩护，那么操作系统用到很多算法，是不是也要将算法和操作系统合并为一门课而称为“算法与操作系统”呢？编译器用到更多的算法，并且在实现时大量使用数据结构，是否要将编译器、算法、数据结构合并为一门课呢？显然，这种因为关联就要合并的观点是值得商酌的。退一步说，如果真要缠绕，数据结构的缠绕对象应该是程序设计，因为数据结构是程序设计的一种必备工具，它就是为程序设计而出现的。
因此，将数据结构与算法缠绕并没有逻辑或历史依据，也不是学习关联知识的必由之路。缠绕导致的结果就是逻辑混乱：让人将本来是相对独立的知识领域理解为无法分割的同一领域。
2．内容残缺
缠绕的另一个缺点是导致数据结构课程的内容出现缺陷。由于要花时间讲述部分算法内容，很多重要的数据结构就没有时间覆盖。例如，跳转表、费波拉契树、费波拉契堆、幂堆、分离划分集、数据结构扩展技术等内容在绝大部分的数据结构课里并不涉及。这些知识的缺乏对后续课程的开展或学生将来的工作有着不利的影响。比如，由于通常的数据结构课程并不讨论幂堆及菲波拉契堆，导致在其他领域讨论最小生成树、最短路径等问题时出现基础不够的情况。对于从事存储技术的学生来说，数据结构如果没有覆盖B树、K树、最优树的话，则其在理解存储系统设计的时候将面临困难。在今天存储技术日益重要且热门的情况下，不少学生都希望能够成为存储领域的人才。而数据结构的这种缺陷不得不说是一大遗憾。
3．衔接困难
鉴于定位（并非专业的算法课）和时间原因，数据结构课程对算法内容的讲解浅显残缺。这样，绝大部分学校在开设数据结构课的同时还通常开设算法课。此种情况下，数据结构与算法的缠绕导致两门课程的内容衔接出现混乱。例如，排序到底是应该在数据结构课讲，还是应该在专门的算法课讲？还是两门课都讲呢？查找与搜索呢？图的算法呢？由于没有一个众所公认的统一指导原则，两门课程的教师和教材作者都根据自己的爱好随意安排内容，导致很多内容或重复或遗漏。其中，排序、查找、图成为两门课程重复最多的部分。
当然，重复本身并不一定产生问题，只要侧重点、角度、深度不同。问题是，由于缺乏统一安排，现实中两门课之间并不存在默契。有的数据结构教师在讲算法时会偏重实现，有的会偏重理论，讲解同一个算法的深度因教师个人素养、性格不同而不同。这使得后面的算法课在内容安排上无所适从：如果数据结构对算法讲解得浅，算法课就需要从深度上重复讲解前面的内容；如果数据结构对算法内容讲解得很深入，则算法课就不需要重复讲解同样的算法。但由于数据结构教师和算法教师通常不是同一个人，这种默契与合作往往不能实现。
4．阐述肤浅
缠绕除了对夹塞进来的算法内容讲解肤浅外，对数据结构本身内容的讲解深度也受到很大影响。原因很简单：学时只有这么多，又讲数据结构、又讲算法分析，两部分内容都没有时间深入讲解，因而经常是蜻蜓点水，浅尝辄止。一般认为，算法高度抽象且令人生畏，数据结构则高度依赖程序实现且让人反感，将这样两门课程的内容糅合在一起大大增加了对此门课程的逆反程度。而且，缠绕要求教师对两门课程的内容都要熟悉，这无疑增大了培训教师的难度。在缺乏精通这两门课程内容的师资情况下，只能是不断降低讲解深度，仅从表面上阐述，形成一种头痛医头、脚痛医脚的肤浅讲解范式，从而进一步加深了本课程的枯燥与浅薄。
5．心理误导
虽然数据结构课对算法内容的讲解只是皮毛，但大部分教师对这一点并没有进行强调，从而给学生形成心理误导，让学生觉得这就是算法设计与分析。很多学完数据结构的学生认为自己已经学过了算法，导致在后面的算法课上不认真对待，或根本就不再选修算法课。例如，数据结构课程一般会讲解搜索（查找）和哈希（散列），但讲解深度有限：数据结构课程通常不覆盖全域和完美哈希算法，就是讲了，也不太可能会将它们完全阐述清楚。这样，如果学生在后面的算法课里不认真对待，则有可能不会掌握重要的全域和完美哈希算法。
二、应对策略
根据上面的分析，数据结构与算法的缠绕导致了数据结构课程在教学内容和课程设计上的种种缺陷，这些缺陷不利于教学的安排，不利于教材的出版，也不利于学生的学习。我们的调查发现，这些缺陷是导致学生反感数据结构课程的一个重要因素（当然还有其他因素，需另外论述）。因此，对当前的“数据结构”课程进行调整就显得颇为必要。我们的调整方案是采用由来已久的分治战略，正所谓分而治之为上策。
这里的分治就是打破缠绕，将算法内容剔除，集中精力讲解数据结构及其实现。在分治模式下，数据结构覆盖各种结构本身的构造、实现及程序设计应用，而对算法设计与分析不做涉及。当然，由于数据结构总是支持某些操作的，它不可能一点都不涉及算法。例如表结构上的查找操作就与算法里的查找算法关系密切，但这种密切关系并不妨碍二者的分离。数据结构里的算法是就事论事的具体算法及其实现，并不详细或系统论述算法的原则或原理。
三、分而治之为上策
实行分治后，数据结构课程教学所面临的问题都被化解。首先，分治后数据结构与算法课之间的关系清楚，学生不会将它们混为一谈。其次，分治后两门课程内容没有重复，内容安排困难的情况也被化解。再次，课程分解后所产生的额外时间让数据结构课程可以覆盖几乎所有的重要数据结构，内容上的缺陷也不复存在。最后，由于两门课都摆脱了需要讲解对方内容的负担，从而可以更加深入地讲解自身内容，讲解肤浅的问题也迎刃而解。
当然，分而治之也不是说分解得没有半点关系。事实上，在数据结构课程中可以附带提到算法，但只需要提到即可，无需仔细讲解。例如，在讲解数据结构的时候，我们会对不同数据结构的优劣进行比较，而此时可能需要对它们所支持的操作的复杂性进行分析，也就是可能需要算法分析的知识。但我们在这里可以只提供一些感性的分析，即大概论述一下某个数据结构的操作可能时间较长或空间较大，而不用对它们进行精确或渐近分析。这样，就可以在避免论述算法的情况下对数据结构之间的优劣进行比较。
当然，分治策略的实现是有代价的：需要重新编写教材、制订新的教学大纲、教师的水平可能需要提高等。但这些代价是值得的，一旦做到位，以后就顺心应手了。而且，进行此种改革对于所有相关的教师和学生都是一次提升，可以说非常值得。
四、改革的实施及效果
自2008年开始，我们在上海交通大学-密歇根联合学院、上海交通大学软件学院启动了本文提出的分治改革，将数据结构从与算法缠绕的状态下独立出来，并从程序设计的角度重新定位了数据结构课程。这种变革的结果是设立了“程序设计与数据结构Ⅲ”课程，其立足点是与算法分离，围绕程序设计，以程序师的角度看待讨论数据结构。为此我们制订了新的大纲，编写了新的讲义，采用了新的教学方法，并在两年后对实施情况进行了评估。
1．新的教学目标
变革后的数据结构教学目标定为从新的角度阐述和分析数据结构，以一种更为容易接受和理解的“问题驱动”方式进行讲解。通过与算法的适度分离和与程序设计的更加靠近，将数据结构的功能、程序设计实现和具体应用植入学生的头脑中，以使学生能够使用各种数据结构来编写出真实有用的程序和软件。具体目标包括如下一些方面：
训练学生的数据结构思维，使其认识到数据结构的内在优雅和能力；
教授结构化问题解决技术和数据抽象原则；
从架构师和设计师两个角度跨越具体与抽象之间的鸿沟；
帮助学生发觉精巧数据结构给程序所带来的巨大改善；
教授学生如何概括性地评价一个数据结构和程序的成本；
教授学生如何应用数据结构来解决实际问题。
2．新的教学大纲内容
在内容方面，我们将数据结构分为三大类：线性结构、非线性结构、扩展数据结构。线性和非线性结构的含义不言自明，扩展数据结构指的是基于基本数据结构而扩展或构造的结构。这种结构的特点是对某种经典数据结构进行修改或改进，从而能够支持新的实际问题的解决。对与数据结构联系紧密的查找与排序操作，我们将其定位为数据结构上的通用操作。这种定位注重的是操作作为数据结构的自然属性，而不是操作本身背后算法设计的原则和思维。有鉴于此，我们对查找和排序操作的讨论更注重实际实现和各种实现方案对相关数据结构产生及发展的影响，而不在算法战略的设计与分析上花费精力。此外，考虑到现在编程环境的演变，我们留出一章讨论标准模板数据结构。这样就形成了如下所述的教学大纲的六篇内容。
第一篇为结构基础篇，讨论数据结构的背景、来源及基础知识。第二篇讨论时空关系为线性的数据结构，内容包括栈结构、队结构和表结构三章。第三篇讨论数据结构上的通用操作，内容包括查找操作和排序操作两章。第四篇讨论非线性结构，内容包括高级表结构、树形结构、高级树形结构和堆结构四章。第五篇讨论扩展数据结构，内容包括图结构、集合结构和划分结构三章。第六篇讨论标准模板结构。整个大纲不涉及算法设计与分析，不过，需要的时候会向学生提到，对某些结构上面的操作进行精确分析和改进将由后续的算法课程负责。
3．新的教学方法
我们新的教学方法是从（程序）设计师的角度来展开对数据结构的讨论，以“问题”为驱动，以“使用”为轴线，对每一种数据结构的出现动机、发展逻辑、表示方式进行演绎，生动形象地再现了其内在的优雅和哲学。我们注重阐述如何从一种想法转换为一种设计，又如何从设计转化为具体程序，对每种数据结构都辅以程序设计中的实际应用，从而化抽象为具体，帮助学生跨越横亘在高度抽象与高度具体之间的鸿沟。同时我们讨论了所有数据结构的代码实现。这些代码不是伪代码，而是可以直接编译执行的真实代码，进一步帮助学生理解抽象。
例如，我们以现在非常普遍的搜索引擎问题为引导，询问学生通过程序设计来实现搜索引擎会用到哪些数据结构，或者说应该使用何种数据结构才好。立足于由简单到精密的思路，我们先尝试不用任何数据结构，发现无法构建搜索引擎；在用了人人都能想到的数组结构后，虽然可以构建搜索引擎，但效率非常低；我们需要一步步引入构建更为精巧的矢量结构、树结构、索引表、哈希表结构等。这样，通过一个问题，围绕程序设计的实现，我们串起一系列的数据结构，让学生看到了各种数据结构不是凭空出现，而是因问题驱动、经过逻辑上的逐次演进推理而出现，从而帮助学生更加深入并饶有趣味地把握数据结构。
4．新的教材
我们按照新的思路，编写了新的数据结构讲义。该讲义体现的就是本文的中心思想：通过将算法内容剥离，以问题为驱动，从程序设计师的角度对数据结构的来龙去脉和背后原理进行深入、独到的阐述，使数据结构的讨论清晰、实用，并充满趣味和吸引力。
该讲义在经过三届数据结构教学的实践、改善和整理后，已正式定型为教材，取名《数据结构之弦》，将由高等教育出版社于2011年出版。
5．实施效果评估
在改革实践2年后的2010年上半年，我们在软件学院二年级成绩为好、中、差的学生里各随机抽取了5名学生，总计15人，布置了3道程序设计与数据结构编程题对他们进行考核。实际考核中有1名好生因故放弃。在综合了5名教师对14名学生的评价后，学生答题情况被评为好的5人、中的8人、差的2人。与样本选取的好4人、中5人、差5人的情况相比较优，说明课程改革效果明显。
同时，通过对上海交通大学-密歇根联合学院学生的问卷调查表明，学生对数据结构学习的兴趣明显提升，以往的那种反感和腻味已经不复存在。
用分而治之的策略来化解“数据结构”课程与算法内容的缠绕，降低了教学难度，改善了教学效果。通过将算法内容剥离，以问题为驱动，以程序设计为轴线，从程序设计师的角度对数据结构的产生和原理进行深入独到的阐述，使数据结构的讨论清晰、实用，并充满了趣味和吸引力。实践表明，这种改革取得了良好的效果。
参考文献：
[1] Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithms Analysis[M]. 北京：电子工业出版社，2002.
[2] Bruno R. Preiss. Data Structures and Algorithms with Object-Oriented Design Patterns in C++[M]. John Wiley & Sons, Inc, 1999.
[3] Thomas H. Cormen, etc. Introduction to Algorithms (2nd edition)[M]. 北京：高等教育出版社，2005.
[4] Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran.Computer Algorithms (Paperback)(2nd edition)[M]. Silicon Press, 2008: 773.
[责任编辑：余大品]