论文部分内容阅读
摘 要：“数据结构”是计算机类专业的核心课程，算法是“数据结构”课程中的重点和难点内容。由于“数据结构”课程一般在低年级开设，学生接触计算机相关的知识量还不够多，在教学过程中，普遍反映算法抽象，难以理解和应用。结合实际工作经验，开发和利用算法可视化工具，将排序、着色、最短路径等算法用可视化工具实时、动态展示出来，加深学生对算法的直观认识，可让学生更好地理解和使用算法，并提升了教学效果。
关键词：数据结构;算法可视化;教学方法
中图分类号：TP311.12-4 文献标识码：A 文章编号：2096-4706（2019）23-0095-03
Exploration and Thinking of Algorithm Visualization
Teaching in “Data Structure” Course
WANG Han
（School of Mathematics and Computer Science，Guangdong Ocean University，Zhanjiang 524088，China）
Abstract：“Data Structure” is the core course of computer major，and algorithm is the key and difficult content of “Data Structure” course. The course of “Data Structure” is generally offered in the junior grade，and the amount of knowledge related to computer is not enough. In the teaching process，it generally reflects the abstract algorithm，which is difficult to understand and apply. Combined with practical work experience，the algorithm visualization tools are developed and used to show the sorting，coloring，shortest path and other algorithms in real time and dynamically with the visualization tools，so as to improve students’intuitive understanding of the algorithm，make students better understand and use the algorithm，and improve the teaching effect.
Keywords：data structure;algorithm visualization;teaching methods
0 引 言
“数据结构”既是计算机类专业的专业基础课程，又是核心课程。这门课程在计算机的学科中起到了承上启下的作用，既会为后续学习操作系统、算法分析与设计和软件工程等课程打下良好的基础，同时也对培养学生抽象思维能力、创作力和解决实际问题的动手操作能力起到一定的指导作用。但是该课程概念繁多、信息量大、抽象性强，一般在低年级开设，学生刚开始接触计算机，相关的知识量还很小，所以在教学过程中，学生普遍反映算法抽象，很难理解。
由于算法过于抽象并且实践性较强，造成学生难以直观地学习和理解算法，以至于在对算法的学习和理解的过程中耗费时间和精力过多，造成教学效率低、学生难以理解，以及理论和实际联系不够紧密，出现脱节等问题。为了解决这一問题，本文提出如何将复杂的事物转化为直观的图像。利用可视化的方式，将算法所蕴含的精髓内容转化成易于观察的图像进行呈现，来帮助学生更好地理解和运用算法。
1 算法可视化教学方法
1.1 算法可视化的需求与设计
对算法进行可视化的原理是使用需要可视化的算法对输入的数据进行处理分析，然后根据需要选择性地将算法执行前、算法执行过程中和算法执行完毕后这三个阶段中数据的变化进行图形化显示，以供学生观察、分析和理解算法。
算法可视化的架构设计依托于其要实现的功能，因此，在了解了算法可视化的原理后，首先需要对算法可视化的需求进行分析，确定所需要实现的内容，随后再根据需求分析的结果，对算法可视化进行模块划分。
1.2 算法可视化的结构设计
根据算法可视化的流程，在对任何一个算法进行可视化时，都可以采用MVP模式的结构将其设计分为三层，分别是模型层（Model）、视图层（View）、和控制层（Controller）。如图1所示。
（1）模型层，也称作数据层，主要负责存储和处理用户输入的数据以及算法运行过程中产生的中间数据，并将处理后的数据发送给视图层。
（2）视图层，负责显示相关的运行逻辑，主要负责将数据进行处理转化为图像，并将图像输出到客户端。
（3）控制层，在这里需要同时控制数据层和视图层，起到传递消息和处理业务逻辑的作用。
1.3 算法可视化系统模块设计
根据算法可视化的类型，本文将可视化系统的模块分为2个，分别是过程可视化模块和概念可视化模块。模块之间相互独立，互不影响，每个模块都存在着其所属类别的算法可视化程序。对此，算法可视化系统的模块设计如图2所示。 1.4 算法演示界面的实现
系统界面是系统离用户最近的地方。在技术快速发展的当下，同一款产品，提供的功能差异不大时，哪一款产品界面设计得更友好，人们就会倾向于用哪一款。因此，界面设计得美观与否，直接决定产品是否能够得到用户的认可;除此之外，若界面设计得好，不用过多地引导用户操作，用户都会自己主动去探索使用方法。
尽管根据算法的特点，本系统的界面可能会有所不同，但其原型都是一样的。
1.5 过程可视化模块的实现
过程可视化模块主要实现对算法程序的执行流程，以及中间数据的变化用动态图像配合文字表现出来。过程可视化模块中实现了过程可视化的算法分别是：冒泡排序、归并排序、m着色问题、Kruskal算法求最小生成树和Dijkstra求最短路径算法。
1.5.1 冒泡排序法
冒泡排序算法是排序算法中最容易被理解的算法，其思路简单易懂，执行过程中没有太大的变化，因此可以直接采用动画的方式对冒泡排序的过程进行可视化。
图3为冒泡排序可视化过程中的一个关键帧，图中黑色柱子是已排序好的数字，两个框中的两个柱体是正在相互比较的两个数字，灰色则为未排序的数字。右侧是交互按钮和可视化程序执行过程中数据的变化细节。
1.5.2 归并排序法
归并排序使用了分而治之的设计理念，如图4所示是插入排序的过程可视化示例图，灰色柱状图是正在进行归并排序的动画，黑色柱状图则是由关键帧组成的静态图。框中的元素为正在排序的元素，其余为待排序的元素。
1.5.3 m着色问題
m着色问题算法的实现思路大致为：
（1）把一个图中的顶点按其角度大小依次减小的次序进行排列;
（2）然后用第一种颜色对第一个点进行上色，并且按照排列好的顺序，将与之前的着色点不相邻的每一点涂上同样的颜色;
（3）把第二种颜色对尚未着色的点重复步骤2，用第三种颜色继续，直到所有点全部上色为止。
m着色问题的可视化同样以动画的方式实现，不同的是，需要由用户绘制图的节点，然后连接成图，之后再由对应的程序对m着色的算法进行可视化。图5为m着色问题算法演示动画过程中的其中一帧。
1.5.4 最小生成树（Kruskal算法）
Kruskal生成最小生成树算法的可视化，以动画的方式实现。需要用户手动绘制一个图，之后再由系统程序使用Kruskal算法生成最小生成树。图6为Kruskal算法在演示动画过程中的其中一帧。
1.5.5 最短路径（Dijkstra算法）
最短路径Dijkstra算法的可视化，以动画的形式实现。需要用户手动绘制一个图，之后再由系统程序使用Dijkstra算法生成求出最短路径的演示动画。图7为Dijkstra算法在可视化过程中的其中一帧。
2 结 论
本文针对当前“数据结构”教学过程中存在的问题，结合多年的理论教学经验，进行教学改革与探索，开发和利用算法可视化工具，针对不同算法将其实时、动态地展示出来，以加深学生对算法的直观认识，让学生能够更好地理解和运用算法，为教师进一步提高课堂教学效率和教学水平提供了参考。
参考文献：
[1] 郭伊.《数据结构》课程教学动态演示系统的设计与实现 [D].杨凌：西北农林科技大学，2015.
[2] 刘丛.针对数据结构的命令式算法可视化系统设计与开发 [D].长沙：湖南大学，2015.
[3] 熊慧.jQuery技术在网页美工中的应用 [J].中国新通信，2018，20（6）：100.
[4] MCCORMICK H B. Visualization in scientific computing [J].ACM SIGBIO Newsletter，1988，10（1）：15-21.
作者简介：王晗（1976.04-），女，汉族，陕西西安人，中级职称，本科，研究方向：计算机及其应用。
关键词：数据结构;算法可视化;教学方法
中图分类号：TP311.12-4 文献标识码：A 文章编号：2096-4706（2019）23-0095-03
Exploration and Thinking of Algorithm Visualization
Teaching in “Data Structure” Course
WANG Han
（School of Mathematics and Computer Science，Guangdong Ocean University，Zhanjiang 524088，China）
Abstract：“Data Structure” is the core course of computer major，and algorithm is the key and difficult content of “Data Structure” course. The course of “Data Structure” is generally offered in the junior grade，and the amount of knowledge related to computer is not enough. In the teaching process，it generally reflects the abstract algorithm，which is difficult to understand and apply. Combined with practical work experience，the algorithm visualization tools are developed and used to show the sorting，coloring，shortest path and other algorithms in real time and dynamically with the visualization tools，so as to improve students’intuitive understanding of the algorithm，make students better understand and use the algorithm，and improve the teaching effect.
Keywords：data structure;algorithm visualization;teaching methods
0 引 言
“数据结构”既是计算机类专业的专业基础课程，又是核心课程。这门课程在计算机的学科中起到了承上启下的作用，既会为后续学习操作系统、算法分析与设计和软件工程等课程打下良好的基础，同时也对培养学生抽象思维能力、创作力和解决实际问题的动手操作能力起到一定的指导作用。但是该课程概念繁多、信息量大、抽象性强，一般在低年级开设，学生刚开始接触计算机，相关的知识量还很小，所以在教学过程中，学生普遍反映算法抽象，很难理解。
由于算法过于抽象并且实践性较强，造成学生难以直观地学习和理解算法，以至于在对算法的学习和理解的过程中耗费时间和精力过多，造成教学效率低、学生难以理解，以及理论和实际联系不够紧密，出现脱节等问题。为了解决这一問题，本文提出如何将复杂的事物转化为直观的图像。利用可视化的方式，将算法所蕴含的精髓内容转化成易于观察的图像进行呈现，来帮助学生更好地理解和运用算法。
1 算法可视化教学方法
1.1 算法可视化的需求与设计
对算法进行可视化的原理是使用需要可视化的算法对输入的数据进行处理分析，然后根据需要选择性地将算法执行前、算法执行过程中和算法执行完毕后这三个阶段中数据的变化进行图形化显示，以供学生观察、分析和理解算法。
算法可视化的架构设计依托于其要实现的功能，因此，在了解了算法可视化的原理后，首先需要对算法可视化的需求进行分析，确定所需要实现的内容，随后再根据需求分析的结果，对算法可视化进行模块划分。
1.2 算法可视化的结构设计
根据算法可视化的流程，在对任何一个算法进行可视化时，都可以采用MVP模式的结构将其设计分为三层，分别是模型层（Model）、视图层（View）、和控制层（Controller）。如图1所示。
（1）模型层，也称作数据层，主要负责存储和处理用户输入的数据以及算法运行过程中产生的中间数据，并将处理后的数据发送给视图层。
（2）视图层，负责显示相关的运行逻辑，主要负责将数据进行处理转化为图像，并将图像输出到客户端。
（3）控制层，在这里需要同时控制数据层和视图层，起到传递消息和处理业务逻辑的作用。
1.3 算法可视化系统模块设计
根据算法可视化的类型，本文将可视化系统的模块分为2个，分别是过程可视化模块和概念可视化模块。模块之间相互独立，互不影响，每个模块都存在着其所属类别的算法可视化程序。对此，算法可视化系统的模块设计如图2所示。 1.4 算法演示界面的实现
系统界面是系统离用户最近的地方。在技术快速发展的当下，同一款产品，提供的功能差异不大时，哪一款产品界面设计得更友好，人们就会倾向于用哪一款。因此，界面设计得美观与否，直接决定产品是否能够得到用户的认可;除此之外，若界面设计得好，不用过多地引导用户操作，用户都会自己主动去探索使用方法。
尽管根据算法的特点，本系统的界面可能会有所不同，但其原型都是一样的。
1.5 过程可视化模块的实现
过程可视化模块主要实现对算法程序的执行流程，以及中间数据的变化用动态图像配合文字表现出来。过程可视化模块中实现了过程可视化的算法分别是：冒泡排序、归并排序、m着色问题、Kruskal算法求最小生成树和Dijkstra求最短路径算法。
1.5.1 冒泡排序法
冒泡排序算法是排序算法中最容易被理解的算法，其思路简单易懂，执行过程中没有太大的变化，因此可以直接采用动画的方式对冒泡排序的过程进行可视化。
图3为冒泡排序可视化过程中的一个关键帧，图中黑色柱子是已排序好的数字，两个框中的两个柱体是正在相互比较的两个数字，灰色则为未排序的数字。右侧是交互按钮和可视化程序执行过程中数据的变化细节。
1.5.2 归并排序法
归并排序使用了分而治之的设计理念，如图4所示是插入排序的过程可视化示例图，灰色柱状图是正在进行归并排序的动画，黑色柱状图则是由关键帧组成的静态图。框中的元素为正在排序的元素，其余为待排序的元素。
1.5.3 m着色问題
m着色问题算法的实现思路大致为：
（1）把一个图中的顶点按其角度大小依次减小的次序进行排列;
（2）然后用第一种颜色对第一个点进行上色，并且按照排列好的顺序，将与之前的着色点不相邻的每一点涂上同样的颜色;
（3）把第二种颜色对尚未着色的点重复步骤2，用第三种颜色继续，直到所有点全部上色为止。
m着色问题的可视化同样以动画的方式实现，不同的是，需要由用户绘制图的节点，然后连接成图，之后再由对应的程序对m着色的算法进行可视化。图5为m着色问题算法演示动画过程中的其中一帧。
1.5.4 最小生成树（Kruskal算法）
Kruskal生成最小生成树算法的可视化，以动画的方式实现。需要用户手动绘制一个图，之后再由系统程序使用Kruskal算法生成最小生成树。图6为Kruskal算法在演示动画过程中的其中一帧。
1.5.5 最短路径（Dijkstra算法）
最短路径Dijkstra算法的可视化，以动画的形式实现。需要用户手动绘制一个图，之后再由系统程序使用Dijkstra算法生成求出最短路径的演示动画。图7为Dijkstra算法在可视化过程中的其中一帧。
2 结 论
本文针对当前“数据结构”教学过程中存在的问题，结合多年的理论教学经验，进行教学改革与探索，开发和利用算法可视化工具，针对不同算法将其实时、动态地展示出来，以加深学生对算法的直观认识，让学生能够更好地理解和运用算法，为教师进一步提高课堂教学效率和教学水平提供了参考。
参考文献：
[1] 郭伊.《数据结构》课程教学动态演示系统的设计与实现 [D].杨凌：西北农林科技大学，2015.
[2] 刘丛.针对数据结构的命令式算法可视化系统设计与开发 [D].长沙：湖南大学，2015.
[3] 熊慧.jQuery技术在网页美工中的应用 [J].中国新通信，2018，20（6）：100.
[4] MCCORMICK H B. Visualization in scientific computing [J].ACM SIGBIO Newsletter，1988，10（1）：15-21.
作者简介：王晗（1976.04-），女，汉族，陕西西安人，中级职称，本科，研究方向：计算机及其应用。