翻转课堂在数据结构课程中的应用

摘要：分析现行教学模式下数据结构课程的教学现状，探讨翻转课堂在数据结构课程中的应用，以数据结构课程的教学内容“最小生成树”为例，提出翻转课堂教学实例。

关键词：翻转课堂；数据结构；教学实例；自主学习

1 数据结构课程的教学现状

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的课程，在计算机科学中是一门综合性的专业基础类主干课程。该课程的教学要求是：学会分析研究计算机加工的数据结构特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术。

数据结构课程的现行教学模式以教师讲授为主，即在课堂内通过教师讲课进行知识的传授，在课堂外则通过学生完成作业进行知识的内化。这种教学模式在实施过程中存在以下3个方面的不足：漠视学生的差异化需求，影响学生的学习兴趣和积极性；学生是知识的被动接受者，抑制学生独立思考和探索创新能力的发展；讲授时间偏长，易造成学生注意力分散，影响学习效果。

探索新的教学模式，提高数据结构课程的教

2 翻转课堂概述

翻转课堂是在信息化环境中，教师提供以教学视频为主要形式的学习资源，学生在上课前完成对教学视频等学习资源的观看和学习，师生在课堂上一起完成作业答疑、协作探究和互动交流等活动的一种新型教学模式，简而言之即“课前传授+课上内化”。

翻转课堂弥补了现行教学模式的不足：①满足学生的差异化需求，激发学生的学习兴趣和积极性。②促进学生自主学习、探索创新和协作沟通能力的发展，学生不再是知识的被动接受者，而是知识的主动学习者；教师不再是知识的传授者，而是学生自主学习的“引路人”和“指导者”。③能使学生自主掌握学习节奏，有利于教学效果的提高。

随着互联网的发展和普及，翻转课堂已经逐渐成为教育教学改革的一波新浪潮。加拿大的《环球邮报》将翻转课堂评为2011年影响课堂教学的重大技术变革。

3 翻转课堂在数据结构课程中的应用

数据结构课程具有知识点繁多、知识抽象性高、对学生的编程实践能力要求高的特点。将翻转课堂应用于数据结构课程，教学视频覆盖知识点面，但在知识深度和编程实践两个方面，还需要课堂教学和上机实验的配合。

3.1 课前活动安排

从教师的角度出发，在课前，教师对教学内容进行梳理，划分出若干相对独立的小知识点，针对每一个小知识点录制10分钟的教学视频。除此以外，教师整理出每一个小知识点的在线测试题目；在学生观看教学视频时，参与在线讨论，了解学生的差异化需求。

从学生的角度出发，在课前，学生观看教学视频，完成在线测试。进度快、基础好的学生可以直接进行在线测试，然后带着问题有针对性地学习；进度慢、基础薄弱的学生可以重复观看教学视频，也可以与同学、老师进行在线讨论等。

3.2 课中活动安排

从教师的角度出发，在课中，教师首先根据学生课前在线讨论和在线测试的情况，进行有针对性的讲解；然后组织学生完成作业或进行小组讨论。对于简单的、概念性的知识点，教师直接组织学生完成作业，对学习有困难的学生进行一对一辅导。对于复杂的、设计实现性的知识点，教师归纳总结出几个关键性问题，组织学生小组讨论，教师旁听学生的讨论情况，适当进行引导和建议。小组讨论结束后，教师听取代表学生的发言，对小组讨论过程中出现的问题进行讲解。

从学生的角度出发，在课中，学生完成作业或进行小组讨论。数据结构一般为小班教学，学生人数不超过20人，学生由3-5人组成一个讨论小组，每个小组选出一名小组长。小组长负责组织协调小组成员的讨论和发言，并在小组讨论结束后进行代表发言。小组成员应积极交流对问题的认识和想法，达成组内共识。

4 翻转课堂应用于数据结构课程的教学实例

以数据结构第7章“图”中的教学内容“图的最小生成树”为例，介绍翻转课堂应用于数据结构课程的实施过程。这一教学内容的教学要求如下：

①了解图的最小生成树的概念；②理解构造图的最小生成树的两种算法：普里姆（Prim）算法和克鲁斯卡尔（Kruscal）算法的算法思想；③掌握普里姆算法和克鲁斯卡尔算法的编程实现。

其中，教学重点是理解普里姆算法和克鲁斯卡尔算法的算法思想，教学难点是掌握普里姆算法和克鲁斯卡尔算法的编程实现。

根据教学要求，这一教学内容可以划分成3个相对独立的小知识点：图的最小生成树的概念；普里姆算法；克鲁斯卡尔算法；其中，普里姆算法和克鲁斯卡尔算法的教学安排类似，在接下来的讨论中均以普里姆算法为例。

4.1 课前活动设计

根据对教学内容的划分，教师在课前可以录制3个教学视频，分别介绍图的最小生成树的概念、普里姆算法和克鲁斯卡尔算法。然而，要在短短10分钟的教学视频中完整介绍普里姆算法或克鲁斯卡尔算法的算法思想和编程实现是不可能的，因此，在学习普里姆算法和克鲁斯卡尔算法时，需要教学视频、课堂讨论、上机实验的相互配合。

4.1.1 图的最小生成树的概念

（1）教学视频设计。图的最小生成树指的是带权无向连通图中各边权值之和最小的生成树，常常应用于构造具有最小代价的通信线路等实际问题中。教学视频如果只是理论性地介绍什么是图的最小生成树的概念，学生难以将这一概念与实际应用联系起来，因此，教师由一个实际问题出发，通过分析，引出图的最小生成树的概念，使得学生在学习这一概念的同时，能了解它的实际应用。

问题设计：

已知6座城市：合肥（H）、芜湖（W）、六安（L）、亳州（B）、滁州（C）、马鞍山（M）。要在这6座城市之间建设通讯网络，要求所有城市能相互通讯，且总的建设成本最小。

问题分析：

这个实际问题可以抽象成一个无向完全网G。网G包含6个顶点，15条边。其中顶点表示城市，边表示两城市之间的通讯线路，边的权值表示相应的建设成本。

这个实际问题转换成：构造网G的各边权值之和最小的生成树（最小生成树）。

（2）在线测试设计。什么是图的最小生成树？图的最小生成树一般应用于哪些实际问题中？

4.1.2 普里姆算法

（1）教学视频设计。对普里姆算法的学习包括理解算法思想，掌握编程实现。教学视频只介绍普里姆算法的算法思想。

普里姆算法是一种构造图的最小生成树的算法，算法思想如下：

假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={uo}（uo∈V），TE={）开始，重复执行下述操作：在所有u∈U.v∈V-U的边（u，v）∈E（待选边）中找一条权值最小的边（uo，vo）并人集合TE，同时v。并入u，直至U=V为止。此时TE中必有n-l条边，则T=（V，{TE}）为N的最小生成树。

教学视频如果只是理论性地介绍普里姆算法的算法思想，不仅枯燥无味，而且难以表达清楚，因此，教师配合动画演示，讲解利用普里姆算法构造图的最小生成树的具体过程。在讲解过程中，需要注意以下两点：①集合V中的每一个顶点都可以作为初始的u。点；②当待选边集合中出现多条权值相等且最小的边时，任意选择其中一条即可。

（2）在线测试设计。给出具有典型特征的图，要求学生利用普里姆算法构造其最小生成树，画出构造过程。

4.2 课中活动设计

在课中，教师首先根据学生课前在线讨论和在线测试的情况，进行有针对性的讲解，然后组织学生完成作业或进行小组讨论。

1）图的最小生成树的概念。

图的最小生成树是一个简单的概念性的知识点，教师直接组织学生完成作业。在学生完成作业的过程中，教师对学习有困难的学生进行一对一辅导。

2）普里姆算法。

普里姆算法是一个复杂的设计性的知识点，在教学视频中只介绍了普里姆算法的算法思想。在课中，教师归纳总结出普里姆算法在编程实现时需要解决的几个关键性问题，依次组织学生进行小组讨论。归纳总结出的问题如下：

（1）无向连通网如何存储？在普里姆算法中，可以采用邻接矩阵或邻接表存储无向连通网。

（2）待选边集合如何表示？待选边集合已经存储在邻接矩阵或邻接表中，但由于邻接矩阵或邻接表中存储了网中所有的边，要在待选边集合中选择权值最小的边，需要遍历整个邻接矩阵或邻接表，每次遍历的时间复杂度为O（n2）。为了降低时间复杂度，附设一个辅助数组，用于存储待选边集合。

（3）权值最小的边如何选择？在辅助数组中选择权值最小的边，可以采用朴素的最小值求解算法，时间复杂度降低为O（n）。

（4）-个顶点并入集合U如何表示？当挑选出权值最小的边后，需要将该边依附的属于集合V-U的顶点并入集合U，此时，将辅助数组中该顶点对应分量的权值域置为0。

针对这4个问题，教师在每次提问后，给学生10分钟左右的时间进行小组讨论，由小组长负责协调小组成员的讨论和发言，达成组内共识。在学生进行小组讨论的过程中，教师旁听学生的讨论情况，适当进行引导和建议。小组讨论结束后，教师听取小组长的汇报，对小组讨论过程中出现的典型问题进行讲解。

经过小组讨论后，学生对普里姆算法在编程实现过程中需要解决的4个关键性问题已经有了自己的认识和想法，接下来组织学生上机实验，利用C语言编程实现普里姆算法。在上机实验过程中，教师对编程有困难的学生进行一对一辅导。

5 结语

数据结构课程具有知识点繁多，知识抽象性高，对学生的编程实践能力要求高的特点。在现行教学模式下，学生习惯于被动地接受知识，而不是主动地思考和探究，以至于最后对知识的理解比较肤浅，编程实践能力也比较薄弱。将翻转课堂应用于数据结构课程的教学中，学生成为知识的主动学习者，培养了学生独立思考和探索创新的能力；学生在小组讨论的过程中，锻炼了组织协调和团队合作能力；教师能够关注学生的个体化差异，满足学生的差异化需求，有利于教学效果的提高。