“数据结构”课程中算法可视化教学的探索与思考

来源 :现代信息科技 | 被引量 : 0次 | 上传用户:drygps
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘  要:“数据结构”是计算机类专业的核心课程,算法是“数据结构”课程中的重点和难点内容。由于“数据结构”课程一般在低年级开设,学生接触计算机相关的知识量还不够多,在教学过程中,普遍反映算法抽象,难以理解和应用。结合实际工作经验,开发和利用算法可视化工具,将排序、着色、最短路径等算法用可视化工具实时、动态展示出来,加深学生对算法的直观认识,可让学生更好地理解和使用算法,并提升了教学效果。
  关键词:数据结构;算法可视化;教学方法
  中图分类号: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-),女,汉族,陕西西安人,中级职称,本科,研究方向:计算机及其应用。
其他文献
分析丁一种基于共享密钥的EAP认证和密钥建立协议——EAP—SAKE。首先,介绍了该协议的报文交换流程,并详细分析了其中每一种报文的结构。接下来分析了该协议中的不同密钥之间的
加曼特金矿位于西天山北段的近东西向晚古生代吐拉苏-也列莫顿成矿带,本文着重对该矿成矿条件与斑岩型金矿进行了对比研究,初步认为:加曼特金矿可能属中低温热液过渡型金矿,并
对碲铜复杂原料中碲贵金属采用了加压浸出工艺处理,研究了游离NaOH浓度、固液比、浸出时间、浸出压力、浸出温度对浸出效果的影响。研究结果表明,游离NaOH浓度为40g.L^-1、固
文章研究了外平面图的匹配控制数.当直径为2和3时,匹配控制数皆为2或4;当直径大于3时,笔者举例说明匹配控制数可以任意大.同时,笔者也刻画了所有直径为2的外平面图.
针对三维OTSU算法计算量较大、运算时间较长的问题,提出了基于布谷鸟搜索优化的三维OTSU图像分割算法.该算法采用布谷鸟搜索算法对三维OTSU进行优化.其中,以像素灰度值-领域均值-领域中值的三维类间方差作为布谷鸟搜索算法的适应度函数,通过评价Lévy飞行路径上像素的适应度,获得最佳分割阈值.实验结果表明:与灰度值领域均值梯度的三维OTSU算法相比,该算法对低信噪比的图像分割稳定性和可靠性较佳;同
文章针对新疆喀什地区盐渍土进行了介电常数室内实验,从分析盐渍土介电特性的主要影响因素入手,分别从理论和实验两方面对盐渍土的介电特性进行分析;通过含水含盐量正交测试,
针对"两客一危"相关的行业管理端、企业管理端信息管理系统数据标准不统一、业务间信息不共享、整合困难大等问题,提出一种基于安全闭环的"两客一危"动态监管平台,该平台能够
本文介绍一种PC中断机制在信号测量领域的非常规使用方法,其特点是直接将被测量的信号作为中断请求,通过软件记录每次中断的时刻从推知被测量信号的波形、周期、频率或进行更高层次的编码识别等等。
本文以C++为基础,详细论述了面向对象的程序设计技巧,提出了自顶向下设计,自底向上编码的设计方法,阐明了包容类的设计过程,给出了用C++语言编写的关键程序及应用实例。
当——当——当,远处的钟声响起,新学期终于来了。习惯了假期的懒散悠闲,该调适心情,迎接新的挑战啦!