在数据结构与算法课程中应用中小型算法项目式教学设计研究——以迷宫程序在图论章节的讲解为例

孙晶 1， 2 郭成艳 1 赵向前 1 刁鹏程 1 郑东林 1

1 新疆大学信息科学与工程学院； 2 新疆多语种重点实验室

摘要：针对数据结构与算法课程当中的教学实例规模过小、理论与程序实现联系不足等缺点，本文提出了使用中型项目迷宫进行项目式教学，详细介绍了Prim算法在迷宫游戏中的应用并设计实现迷宫。实践证明使用了迷宫程序设计的项目教学法提高了学生的学习兴趣、自主学习能力、分析和解决中小型项目的模块分解能力及编程实践能力。

关键字：数据结构 算法 项目教学 Prim算法 迷宫

Abstract:In view of the disadvantages of small teaching examples in data structure and algorithm curriculum and insufficient connection between theory and program implementation,this paper proposes the use of medium-sized project maze,introduces the application of Prim algorithm in maze game and realizes the maze.Practice has proved that the project teaching method of maze programming is used to improve the students’ learning interest,independent learning ability,module decomposition ability and programming practice ability to analyze and solve small and medium-sized programs.

Keywords:data structure algorithm project teaching Prim algorithm maze

1 引言

数据结构与算法课程是计算机相关专业、信息管理专业等相关专业的一门重要的专业基础课程。通过该课程的学习，使学生学会正确分析数据的结构、合理地选择数据地存储方式，并设计科学操作算法，训练学生的发散型思维能力，提高学生的创新能力，增强学生的团队合作能力，为后续设计和实现编译程序、操作系统、数据系统及其它系统程序以及各种大型应用程序打下良好的基础。但由于该课程同时也是一门理论和实践性较强、内容丰富且较为抽象的课程，造成学生难以将理论应用于实践中，对算法设计难以理解和掌握。因而难以调动学生学习该课程的积极性和主动性。为了解决以上问题，我们在教学实践过程中采用了项目教学法。

项目式学习作为一种重要的教学策略，正在全世界获得越来越多的关注与学习。项目式学习为学生提供了一个行之有效的框架，来帮助学生更好地解决问题。在项目式学习过程中，学生会自主地提出问题、分析问题并解决问题，能够培养学生地自我管理能力和自主学习能力，也能使学生在收获深度知识地同时掌握21世纪的成功素养：批判性地思考、分析信息的可靠性、与不同的伙伴协作、创造性地解决问题。

2 项目教学法

2.1 基本含义

项目教学是按类别将某门专业课程分为若干技术与技能单元，每个技术或技能单元作为一个小的教学项目，实行理论实践一体化的单元式教学，每个单元教学都以应用该项技术或技能完成一项任务来结束，然后进行下一个项目的教学。简单的说，项目教学就是师生为有效完成某一具体的学习任务而开展的教学活动。项目教学是一种方法，更是一种方案。

项目教学法是以学生为中心，以项目为延伸，老师在整个过程中起引领和指导作用的教学模式。信息的收集、方案的实际、项目的实施及最终的成果展示，都有学生自行负责，最终的答辩是由老师与学生共同参与。

2.2 项目教学法的内涵

项目教学法是一种建立在建构主义学习理论基础上的教学法，它将以往以传授知识为主的传统教学理念转变为以解决问题、完成任务为主的多维互动式的教学理念，强调学习过程中学生的主动性、构建性，支持学生完成任务的自主权和中心地位^[1]。

在项目教学法中，通常老师把新知识隐含在具体的任务中，学生通过对提出的任务进行认知、理解和应用，完成具体的任务，达到教学目的。项目教学的核心就是让学生对知识感到渴求，自主地学习，将学到的知识理解、领悟并加以应用。项目教学法注重通过实际工作过程对学生实践技能、综合能力的培养。在整个教学过程中，通过对老师所提出项目的不断拓展和层层推进来带动课程的学习，学生根据项目的主题，查找资料、学习技能、动手实践、得出成果、成果答辩。对学生全面素质和综合能力方面的培养起着十分重要和有效的作用。

2.3 特点

(1)该项目具有清晰明确的学习任务说明

(2)它是教学内容的理论知识与实践技能的结合体；

(3)项目案例有实际的工程项目及作品；

(4)学生能够解决完成任务过程中所出现的问题

(5)学生能够得出成果并进行展示。

(6)成果展示后，老师和学生能对成果答辩做出合理的评价。

3 迷宫算法的教学设计

迷宫问题是图形学、图论和数据结构等领域中广为人知的一个经典问题，如何生成一个m×n的二维平面迷宫地图，实质上就是生成树的问题，可以应用深度优先搜索（DFS）、广度优先搜索（BFS）、Prim算法和Kruskal算法^[2]，本文介绍的随机迷宫生成算法参考了Prim算法。

3.1 最小生成树

在带权图G=（V，E）中（V为点集，E为边集且每条边带有权值），我们希望找到E的一个无环子集T,使得V中任意两点可到达。由于T无环且联通所有点，可知T必为一棵树，称为这种边子集T的生成树，称所有满足条件的T中权值和最小的为最小生成树。

最小生成树的构造有多种算法，在数据结构与算法课本中主要介绍了Prim算法和Kruskal算法两种经典算法。这两种算法均有各自的优点。Prim算法的时间复杂度与边数无关，比较适合求边稠密网络的最小生成树，而Kruskal算法的时间复杂度与顶点数无关，适合求边稀疏网络的最小生成树。下文主要讲述的是Prim算法在迷宫游戏中的应用。

3.2 Prim 算法

设图G=(V,E)是连通网，其生成树的顶点集合为U，从指定顶点V0开始将它加入集合U中，然后将集合U中的顶点与集合V-U中的顶点构成的所有边中选取权值最小的一条边作为生成树的边，并将V-U中的那个顶点加入到U中，表示该顶点已连通。再用U中的顶点与V-U中的顶点构成的边中找最小的边，并将相应的顶点加入U中，如此下去直到全部顶点都加入到U中，得到最小生成树。即：

①把V0放入U。

②在所有u∈U,v∈V-U的边(u，v)∈E中找到一条最小权值的边，加入生成树。

③把②找到的边的顶点v加入U集合。如果U=V，则结束，否则继续执行②。

3.3 Prim 算法和迷宫生成

3.3.1 迷宫生成和最小生成树的联系

假设迷宫初始化时所有的墙壁都是封死的，路径格处于独立状态，如果把迷宫看作带权图G,则点集V为路径格，边集E则是任意相邻两路径格间连线的集合，可看作所有路径权值都相等。设迷宫入口为左上角的路径格，出口为右下角的路径格（如图1)，则生成一个迷宫的实质就是找G的一个最小生成树T，T包含所有路径格，不成环，且其中任意两个路径格连通。将入口处的路径格定义为起点，把起点加入到生成树的顶点集合U中，然后将集合U中的顶点与集合V-U中的顶点构成的边中选取一条边作为生成树的边，并将该顶点加入到U中，表示该顶点已连通。然后再重复上面步骤，直至全部顶点都加入到U中，得到一颗最小生成树。

3.3.2 Prim 迷宫生成算法

①初始化生成一个网状的结构用于生成迷宫。首先将地图全部赋为墙壁，接着将奇行奇列变为空格如图2所示（将地图中的每个空格设置为一个顶点，顶点之间的墙设置为一条边）。

②选取迷宫入口的空格为起点，将该空格加入到已访问的空格集合U中，并把其上下左右的墙加入到被访问的墙集合E中，将起点周围随机可走的墙变为通路。

③当集合E里还有墙时

a.从集合E里随机选一个墙，如果这面墙分隔的两个空格有一个空格还没有被加入集合U中，那么把这面墙打通，让未访问的空格成为迷宫的通路，再把这个空格加入到集合U中，并将其上下左右的墙加入到集合E中。

b.如果墙两面的空格都已经被访问过，那就从集合E里移除这面墙。

④集合E里已经没有墙了，结束。

图1 迷宫界面显示图 图2 迷宫游戏的初始化地图 图3 Prim算法生成地图详细过程图

通过设计和实现迷宫，我们首先学习并掌握了游戏实现过程中所需要用到的知识点，Prim算法、最小生成树以及Prim算法在迷宫中是如何让应用的，接下来我们将详细介绍迷宫游戏的各个模块是如何实现的。

4 迷宫的设计与实现

迷宫的设计是按照自上而下的模块分解的结构化程序设计方法划分游戏的功能，此种划分是一个总体比较抽象的划分，通过主函数对各模块函数的调用，从而最终能够实现游戏的所有功能。迷宫游戏实现的主要功能模块图如图4所示。

图4 迷宫游戏功能模块图

4.1游戏的界面设计

游戏以蓝色方块和黑色背景为主要的界面元素，界面入口的小球为移动的元素，出口的五角星为游戏终点的标志，系统主界面图如图1所示。

4.2　迷宫游戏的控制方式

游戏是通过设置键盘上的快捷键设置实现小球的移动，在菜单里，不同的键选择游戏操作的不同等级。

5总结

经过本次实践后，对近150名学生在图论内容的知识进行了考核，得出了学生在最小生成树部分的得分占比图如图4所示。

图4 最小生成树测试题得分占比图

根据上图得分比，发现大多数学生对最小生成树的两种构造方法的掌握程度比较好，得低分的学生主要是学习态度不太好，学习习惯较为懒散，得分在4~5分的同学主要是对两种构造方法没有透彻的掌握。

在数据结构与算法的图论章节当中采用中小型程序的项目教学法，教学效果会有明显的提升，学生普遍认为自己的动手能力得到了提高，并且在面对实际的问题时，分析问题和解决问题的能力也有了提高。项目教学法改变了传统的教学模式，不再是把老师传授知识作为主要的目标，而是在老师的指导下，学生自主去实践，探寻结果，可以说这是对传统教学法的创新。

参考文献

1. 游琪. 项目驱动在数据结构实践教学中的应用研究[J]. 软件导刊, 2010, 09(001):187-188.

2. 袁开友, 杨勇. 平面迷宫地图随机生成树算法设计与实现[J]. 科学咨询, 2013, 000(001):138-138,139.