“数据结构”课程经典算法的教学探索

鹿旸++刁明光

摘要：分析了“数据结构”课程的特点、经典算法的教学和实践现状，针对存在的问题，以改进经典算法讲解为基础，讨论了如何培养学生的编程思维，并进一步探讨了实践教学的组织和设计。

关键词：数据结构；经典算法；编程思维

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2017）37-0136-02

“数据结构”是计算机专业的一门核心课程。该课程不仅是程序设计的基础，而且是设计和实现编译原理、操作系统、数据库系统等系統程序和大型应用程序的重要基础[1]。数据结构教材以数据的逻辑结构为主线，依次介绍线性结构和非线性结构。在各种数据结构介绍时再讨论其存储结构以及相关算法，最后介绍查找和排序算法，知识框架体系完善清晰[2]。教学的突出难点是知识的抽象性和动态性，尤其涉及大量抽象数据类型及经典算法。本文是作者九年来的授课小结，从教学方法和经典算法的讲解方法入手，进行了教学和实践的探讨。

一、传统教学方法存在的问题

1.缺乏良好的解题习惯。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度决不亚于知识传授。在学习数据结构之前，学生学习了C和C++两门编程语言，但没有进行系统的训练，也没有形成规范的编程习惯。很多同学拿到题目直接编写代码，在写代码的过程中边写边想，然后反复修改代码，造成程序结构混乱、可读性差、调试困难。尤其在解决大规模输入的复杂问题时，更容易造成程序瘫痪。

2.课堂算法讲解不透彻。在课程中，各种数据结构都有相关算法，此外还有查找和排序算法。因此，算法部分占了课程相当大的比例。这其中很多经典算法都极具代表性，使用了大量的编程技巧，这些是算法的精华部分。如果授课教师只对书中的算法进行流程讲解，不揭示编程技巧的话，那么学生也只能死记硬背，学习不到算法的精华，对提高编程能力毫无帮助。而且死记硬背的方式也容易让学生丧失学习的兴趣。

3.缺少综合性实验题目。通常练习册中会按照章节安排实验题目，题目内容针对本章知识点，针对性强，而且和书上的例题有相似之处。因此，学生在做这些分章节的小程序时，过度依赖课本中的范例，甚至不假思索，照搬照抄，编程思维得不到很好的锻炼，而且也体会不到处理大规模输入的复杂问题时，数据结构体现出来的优势。

二、教学方法探索

1.培养良好的分析问题的习惯。如图1所示，遇到问题时，学生习惯性地直接编码，并在代码上不断修改，没有良好的编程习惯，往往解决问题事倍功半。在授课过程中，对每一个问题，教师要严格按照“抽象数据对象→分析逻辑关系→选取物理结构→分析解题思路→画流程图→分析时间复杂度→多种解法比较→确定解题方案→编写代码（可省略）”[3]的思路进行分析和讲解，最终完成算法。其中，在“选取物理结构”环节，要充分分析操作特征，设计合理的存储结构服务于后续算法。在“分析解题思路”和“画流程图”环节，首先提炼解题步骤，形成流程图，然后使用编程技巧优化流程，重点优化循环结构，并逐步修改流程图，最终确定。在分析过程中，应启发学生的解题思路，鼓励大家多角度分析问题，提出不同的解决方案，并应一并列出，逐一分析解题步骤和时间复杂度，最后做一比较。这样，将编程思维从课堂的讲授延伸至实践环节的动手操作，巩固了学习效果。这样学生不仅对算法印象深刻，更能培养良好的思维习惯，从而真正提高解决问题的能力。

2.强调经典算法中的编程技巧。书中选用算法多为经典算法，其中不乏经过多次优化、多次验证的高效率算法。这些算法在优化过程中使用了很多编程技巧。教师在授课过程中，应重点介绍算法的优化方法，并引导学生对程序进行自查和优化，养成良好的习惯[4]。

以冒泡排序经典算法为例，首先讲解算法的思想“依次比较两两相邻记录，若反序，则交换位置，直至有序”。并且举例动态演示。然后让同学尝试将操作流程转换成算法。要求同学设计出流程图，如果课堂上有条件可以编程序实现。然后选取同学的例子做展示，有如图2所示算法。

本算法中有两个循环结构，应逐个解析。第一个循环结构表示算法经过n-1趟完成排序，通过举反例，说明根据输入数列不同，排序趟数也不同，最少一趟就能完成排序，显然第一个循环存在冗余。然后引导学生一起改进算法，此循环要解决的是“结束状态”的判定问题，引出编程技巧“状态判定问题，通过操作特征找条件”。根据算法的“比较”和“交换”操作特征，分析得出“结束条件”为：经过一趟排序，如果没有发生交换操作，就说明已经有序，结束算法。经改进后的第一个循环如图3所示。同样，第二个循环结构也存在冗余。通过分析，引出编程技巧“范围划定问题，通过操作特征找边界”。经编程技巧优化后的程序如图4所示。最后，比较改进前和改进后算法的时间复杂度，然后给定一个输入数列，比较两个算法的实际运行时间。结果显示，虽然没有改变算法的时间复杂度，但通过剔除冗余循环，缩减了算法的运行时间，提高了执行效率。通过对学生程序的优化和实验测试，学生能够直观地认识到使用编程技巧的好处，且印象深刻。

类似的例子还有在顺序查找算法中，通过使用监视哨，简化while循环判定条件的编程技巧；线性表GetElem算法中，合并两个并列循环的编程技巧等等。配合编程技巧的讲解，在实践环节设置题目，进一步强化这些技巧的使用，使学生熟练掌握。学生学习算法的目的是要学会其中的编程技巧，活学活用，这样才能写出高效、优质的算法。

3.设置综合型题目。教师应适当设置包含多个知识点且有多种解法的题目，锻炼学生综合运用知识解决问题的能力，并给学生留出发挥创造力的空间。例如“走迷宫问题”，对已知的二维迷宫求通路。学生可以选择用不同的数据结构表示迷宫作为程序输入，然后选择用深度优先或者广度优先遍历的算法来得到路径，最后用图形界面将迷宫显示出来。再例如“最少换乘次数”问题，已知地点和公交线路，求某两地点间的最少换乘次数。学生需要在问题中抽象出适当的对象和关系，将地点和线路表示在图形结构中，然后可以选择图的广度优先遍历方法，或者改进求单源最短路径的Dijkstra算法，比较它们，选择更优算法。

在实践环节，可以将学生分为若干个团队，团队成员要按照规范的解题思路提出个人的见解，而后互相比较和讨论，最终择优给出完整的解题步骤和算法。这样，学生在充分的讨论过程中，会比较存储结构的差异和不同算法的性能，进一步巩固了书本知识，巩固编程技巧，同时锻炼了团队合作能力。

“数据结构”课程在计算机学科中的地位十分重要，教师在教学过程中应着力培养学生分析和解决问题的能力。这需要教师在授课和实践环节加强编程思维的训练，并不断督促，完善自己的教学方法，以达到更优的教学质量。

参考文献：

[1]陈越，何钦铭，冯雁.“数据结构”综合性课程设计教学探索与实践[J].计算机教育，2008，（08）：54-55.

[2]张铭，赵海燕，王腾蛟.北京大学“数据结构与算法”教学设计[J].计算机教育，2008，（20）：5-11.

[3]孟凡荣，张斌，杨雷.计算思维在数据结构中的实践探索[J].教育教学论坛，2015，（10）：117-120.

[4]张乃孝.数据结构体系分析[J].计算机研究与发展，1988，（05）：36-40.endprint