Total.416
March 2018（B
）
The Science Education Article Collects
总第416期2018年3月（中）
摘
要
各类算法是数据结构课程中的一个重要组成部分，也是一个教学难点。本文结合作者几年来在本科教学过程中的经验和体会，浅谈一下针对不同特点的算法，如何综合使用各类教学方法获得较好的教学效果。关键词
数据结构
算法
教学方法
Exploration and Thinking of Algorithm Teaching in "Data Structure"Course //Ma Huanfei
Abstract Various algorithms constitute an important part in the teaching of data structure.It is a challenge to find efficient ways to carry out these algorithms.In this paper,we will introduce several teaching schemes designed for particular algorithms to reach better teaching effect.
Key words data structure;algorithm;teaching methods
1简介
数据结构与算法分析答案“数据结构”是计算机及相关理工科专业中的一门重要的专业基础课程，主要研究数据在计算机中的表示、组织和处理，以及相应结构上的算法设计和初步的性能分析技术。该课程的研究思想和研究方法在计算机科学及其他理工专业中许多有深度的研究领域得到广泛的应用，因此学好该课程为学生今后从事理论研究、应用开发提供了坚实的理论基础[1]。同时数据结构也是我国研究生入学考试计算机类全国统考科目之一，所以无论从课程的基础性质、后续发展还是教学要求来看，该课程都是本科教学的重中之重。
另一方面，该课程同时具有相当的抽象性和动态性，容易造成教学效率低下、学生理解困难以及理论和实际脱节等问题，所以如何让学生更好地掌握课程的精髓也就成为了教学过程中的一个难点和一个挑战。特别是，在数据结构教学中，算法和实际应用最相关，也最体现数据结构思想的一个部分。在整个教学过程中，会涉及大量算法的讲解，这些算法都需要结合程序语言的实现来让学生理解基本思想，掌握算法实现，特别地还要能够欣赏算法之美。这就提出了一系列的问题：如何在课堂有限的时间和有限的手段下，把算法的核心讲解清楚？如何让学生理解算法背后的思
想，并能运用到实际问题的解决中去？这些都是值得不断探索和思考的问题。
本文结合作者近几年来在本科教学过程中的经验和体会，浅谈一下针对不同的算法，如何综合使用各类教学手段，来获得较好的教学效果。
2各类算法教学方法
2.1逐步演示法
相对于一般的使用PPT 演示和讲授相结合的形式，逐步演示法是指通过专门编写的演示软件来演示算法的逐句执行过程。为了理解算法，需要理解算法的执行规则和各类变量的变化过程，这就需要动态的演示，而传统的PPT 电子教案则有其局限性：为了把相关概念的联系加以体现，往往需要按照视觉理论中
的靠近原则把相关概念放在相近的位置上，但PPT 演示文稿由于篇幅的限制，往往无法在一个页面内实现相关展示，而分页展示则需要在教学中反复切换，从而影响了知识的联结。有文献[2]表明，通过双盲分组测试，实验组（使用逐步演示法）相对于控制组（PPT 演示法）的学生对多个知识点的高级理解有显著差异。
下面以递归算法的栈空间使用演示为例，来说明逐步演示法的使用。递归算法本质上是一种堆栈算法，在每一次递归调用时，都需要为过程中使用的参数、局部变量和返回地址进行分配空间和暂时存储，这就形成了后进先出的栈组织结构。在算法教学过程中，可以结合最简单的递归结构来演示。以阶乘的递归定义为例，那么阶乘函数在求5的阶乘的时候，需要递归调用4的阶乘，活动记录框架中需要暂存参数、局部变量和返回地址，依次类推实现问题的分解，所有临时记录的活动记录框架实现一个工作栈的形式。当达到递归出口n=0时，再逐步取出临时记录进行问题求解，即前面记下的活动记录框架要逐步出栈，形成问题的求解过程。
这样的一个过程，需要动态演示之处很多，简单的PPT 课件未必能够很好地完成演示任务。而使用逐步演示方法，可以在同一个演示空间中，同时演示递归程序代码的每一步执行和调用，将工作栈的每一步变化与问题的从大到小
“数据结构”课程中算法教学的探索与思考
马欢飞
（苏州大学数学科学学院
江苏·苏州215006）
中图分类号：G642文献标识码：A
DOI ：10.16871/jki.kjwhb.2018.03.020
作者简介：马欢飞（1981—），副教授，研究方向为数据科学。
45
教改教法
的分解和从小到大的求解过程清晰地展示出来，帮助学生理解递归的内涵和程序的工作过程。
2.2案例法
案例教学法是利用案例作为教学媒介的一种方法[3]，一般认为案例教学法是指在教学过程中，教师围绕
一定的教学目的，把真实的场景加以典型化处理，形成供学生思考和解决的问题，从而提高学生的学习兴趣，增强学生分析问题解决问题的能力，最终实现学以致用的目的。下面结合若干算法的综合运用为例，来说明在数据结构教学过程中，案例法的使用和探索。
在数据结构的课程中，有大量表面上不同的算法，如穷举法，栈和队列的使用，递归算法，广度优先（BFS）算法和深度优先（DFS）算法，以及图论中的最短路径算法等。这些算法在本质上却有很多相通之处。为了说明这些算法的综合运用，可以通过一个实例来进行讲解。首先在实际问题的选择上，迷宫问题可以说是简单明了但又不失通用性的一个问题。其次在教学材料的准备上，可以通过FLASH或者支持图形界面的编程语言如Java等编写一个图形演示界面，一方面可以直观地展示迷宫的二维图形，另一方面可以给出用数组或邻接表存储的迷宫的表示方法和如何实现每一个格点上通路、障碍和围墙的不同表示方法。在讲解的过程中，可以结合各类算法，融入案例的演示中。对于穷举法，在不涉及栈的结构的时候，可以通过“回溯”的概念来演示路径的探索方法。有了穷举法的基础之后，使用栈和队列则可以更为清晰从更高的层次来演示“回溯”的概念。有了栈和队列的算法之后，可以结合具体案例来讨论两种算法各自到的路径的异同，从而引入如何寻迷宫的最短通路问题。如果进一步把迷宫抽象为一个图的话，那么很自然地就可以演示广度优先和深度优先遍历算法，并且自然而然就可以引入图的最短路径算法，如著名的Dijkstra算法。
以上案例教学方法中，同一个案例可以从浅至深，将整个数据结构从初步到高级的各类算法完全有机地
联系起来。
2.3计算机辅助教学法（CAI）
随着计算机技术的发展，计算机辅助教学（Computer Aided Instruction，简称CAI）得到了长足的发展[4]。CAI是在计算机辅助下进行的各种教学活动，与传统教育方法不同，CAI提供了互动的选项，可以以对话的方式与学生讨论教学内容并进行练习和训练，同时融入了多媒体和知识库等丰富的内容与材料。因此，与传统教学方法相比，CAI为学生提供了一个良好的个性化学习环境，克服了传统教学方式单一、片面的缺点。
在数据结构特别是树和图论中的各类算法中，很多情况不是那么的显然和直观，学生对于同一种算法的理解会有不同的侧重点，从而产生不同方面的疑问。解决这种困难的最好方法就是鼓励学生或者引导学生进行不断的尝试，因此在这种情况下，CAI的使用可以起到事半功倍的效果。下面以图论中求解最小生成树的Prim算法和求解最短路径的Dijkstra算法为例，探讨CAI在算法教学中的使用。
Prim算法求解的是从一个顶点出发，寻边的权重之和最小的连通集合，该算法将图的顶点分成两个集合，一个是已连通的集合，一个是尚未连通的集合，然后通过逐条边加入的过程来获得最终的边权重之和最小的连通集合。而Dijkstra算法求解的是从一个顶点出发，到达其他所有顶点的最短路径，其基本思想也是首先将顶点分为两个集合，然后通过逐步加入边的过程来获得最终的最短通路。这两个算法都需
要事先给定一个图的结构，然后指定一个顶点，逐步演化边的加入，最后实现问题的求解。
要让学生熟悉和掌握以上算法在各种情况下的工作步骤，可以通过各类程序编写图形界面的CAI软件，主要实现如下互动功能：1.个性化生成图形；2.自动化演示求解过程；
3.练习和考核过程。通过个性化图形结构的生成，可以指定顶点和边的信息产生各种特殊的图形，目的是把算法可能遇到的特殊情况都产生出来；通过自动化演示求解过程，可以逐步把两个顶点集通过不同的颜区分开来，把符合要求的边逐步加入图形，同时更新顶点集的信息，目的是把算法的步骤通过具体的图形显示逐步演示出来；通过练习和考核，可以由CAI的题库或者随机生成的图形供学生以互动的方式进行算法的逐步推进练习，在每一步中，CAI软件可以提示正确和错误，并给出候选帮助选项，目的是进一步巩固学生对算法细节的掌握和理解。通过以上CAI软件的辅助，教学信息从本来单向的教师讲解演示学生被动学习，变为双向的学生自我设计题目解决问题和人机交互逐步递进学习。
3总结
本文结合理工科专业本科层次数据结构课程的教学，就各类算法的教学方法提供了探索和思考，为进一步提高课堂效率和教学水平提供参考。囿于笔者的文献阅读量和教学实践还不够深入，本文难免有不足之处，期待读者和专家学者的指教。
参考文献
[1]李葆春.数据结构教程[M].北京：清华大学出版社,2017.
[2]哈斯.“数据结构”课程算法教学的实验研究[J].内蒙古师范大
学学报：教育科学版,2008,21(7):136-137.
[3]J.Shulman.Teacher-written cases with commentaries:A
teacher-researcher collaboration[J].Case methods in teacher education,1992:131-152.
[4]李艺.计算机辅助教学的概念、实践及其它[J].中国电化教育,
1999:5-8.
编辑张效瑞
46

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。