XML驱动的算法可视化系统JH AVE ′-II

理论计算机科学电子笔记178（2007）129-135www.elsevier.com/locate/entcs实现XML驱动的算法可视化托马斯午睡1威斯康星大学计算机科学系：美国威斯康星州奥什科什迈尔斯·麦克纳利2阿尔玛学院关闭MI，USA斯科特·格里森3美国密歇根州阿伦代尔大峡谷州立大学计算机科学系摘要本文介绍了新一代基于客户服务器的算法可视化系统JH AVE ′-II 的开发过程 。 我们相信这是第一个完全由XML驱动的算法可视化系统。我们描述了XML脚本语言可视化作者可以使用JH AVE′-II来定义图形快照序列、集成的弹出问题、同步的伪代码和构成特定算法可视化的文档信息。然后，JH AVE′-II使用这些脚本来呈现可视化效果，并支持学生探索算法。保留字：算法，可视化，xml1引言让学生参与算法可视化（AV）的标准已在[2]中预先详细说明。这些标准被组织到一个项目分类中1电子邮件：naps@uwosh.edu2电子邮件：mcnally@alma.edu3电子邮件：grissom@gvsu.edu1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.01.042130T. Naps等人/理论计算机科学电子笔记178（2007）129这包括响应（关于可视化的问题）、改变（通过向被可视化的算法提供新数据来可视化）、构造（负责由可视化完成的图形呈现的外观）和呈现（使用可视化作为书面，口头，或算法的超文本解释）。一个有效的教学算法可视化必须远远超过一系列漂亮的图片。使用AV的完整教学包必须允许可视化设计师向学习者提问，以便策略性地允许学习者提供输入， 该算法，并补充适当的文本，如同步的伪代码和算法的其他描述的可视化有大量的数据是有效AV的基础-程序状态数据、数据集输入生成、伪代码、超文本解释以及关于学习者正在查看的算法的非平凡问题的生成。去年的ITiCSE工作组“开发基于XML的工具以支持用户与算法可视化的交互”认识到了这一事实。其报告[4]建立了一个框架，为未来的研究和开发确定了方向，并提出了可视化系统设计中的一些有趣问题。在本文中，我们描述了解决这些问题的重要的第一步，通过描述我们认为是第一个完全基于底层数据的XML描述的指令性AV系统的正在进行的工作。 虽然第一步，这个系统不仅仅是一个原型。 环境内我们已经开发了大量的教学可视化，包括适合于典型数据算法和数据结构课程的排序、搜索树和图形算法的完整集合。通过使用XML作为这些可视化操作的数据的底层表示，我们大大减少了生成可视化所需的开发人员时间。此外，我们亦已作好更充分的准备，以应付日后不可避免要扩展的系统。2JHAVE′-IIArchitectureJHAVE′-II结构是对文献[3]中提出的JHAVE′AVe n-V i ro n ment e n的扩展。与最初的JHAVE'一样，JHAVE'-II仍然是一个基于互联网的系统，它通过在服务器上执行算法来生成可视化，生成可视化脚本，并将该脚本交付给JHAVE'客户端以供学习者使用。 然而，与JH A V E ′的起源不同，JHAVE′-II将依赖XML作为定义这些脚本的语言。在这种架构中，服务器应用程序管理可用的算法，并生成客户端显示的可视化脚本。 在标准会话中，学习者首先启动客户端应用程序的实例，该实例显示可用算法的列表。当用户从该列表中选择算法时，客户端向服务器发送请求。 服务器知道学习器必须为此算法提供什么样的输入数据，并向客户端发送适当的输入生成器对象的描述。客户端使用此函数生成T. Naps等人/理论计算机科学电子笔记178（2007）129131图1.一、JHAVE′-II截图为学习者提供适当输入区域的框架。一旦学习者填满了这些区域，客户端将输入作为数据集返回给服务器，以便在运行算法时使用。然后服务器运行一个程序，该程序为该算法生成脚本，并向客户端发送一个URL，脚本可以从该URL中读取。JHAVE′-II客户端安装了适当的可视化器插件，用于解析、呈现和向学习者呈现脚本-并配有标准的VCR式查看控件、停下来思考问题和信息/伪代码窗口。图1展示了Quicksort算法的可视化，并附带了伪代码窗口和一个停下来思考的问题。在JHAVE′-II可视化会话期间的数据流如图所示二、其中，Vis Script脚本流目前是用XML实现的。这是最复杂的一个流程，将在下一节中进行部分描述。其余的工作流（Choice、Input Generator、Input）仍在进行中，此处不作报告。原始的JHAVE'client和插件在解析从服务器接收的Vis脚本时非常困难。 这是因为，不管使用什么插件，数据都是以一种相对神秘的格式到达客户端的，这种格式只有熟悉JHAVE和插件内部复杂性的人才有意义。 在JHAVE′-II中，客户端接收的XML数据是有意义的标记，可以清楚地标识脚本的各个组件。此外，由于XML解析工具的范围很广，所以客户机对数据的解析不是问题。JHAVE′-IIclient简单地使用JDOM132T. Naps等人/理论计算机科学电子笔记178（2007）129图二、JHAVE'-IIDataFlows解析器类（可在http://www.jdom.org）来验证它正在接收语法上有效的脚本，然后构建脚本的内部树表示。然后递归地遍历该内部树以呈现并向学习者呈现可视化。 在JHAVE′（Animal[6]、GAIGS[5]和Samba[7]）可用的各种可视化工具插件中，目前只有GAIGS支持与XML Vis ™一起使用。动物支持正在开发中。3可视化的XML脚本在本节中，我们将简要介绍JHAVE′-II的XML Vis Script语言的部分内容。它本质上是一种脚本语言，可以在算法执行期间的有趣事件中捕获数据结构的表示。这些数据结构的快照然后可以通过JHAVE′-IIe nummentt的各种支持工具来增强。 能够用XML描述的数据结构- 我们还开发了一个类，它实现了数据结构以及toXML方法，可视化设计人员可以使用该方法在感兴趣的事件中注释算法，从而生成可视化脚本所需的XML。 编写可视化脚本生成程序的过程 首先实现你希望可视化的算法，然后注释该程序以类似于插入跟踪器输出以调试程序时所做的方式查看其感兴趣的事件。每种数据结构都有toXML方法，这使得生成普通的可视化非常容易，可以向其中添加停下来思考的问题、同步的伪代码和文档。尽管生产这样高质量的可视化当然需要更多的编程，但我们认为XML标记的描述性本质我们使用的脚本语言仍然使它成为一个相对无痛的过程。T. Naps等人/理论计算机科学电子笔记178（2007）129133<！ELEMENT show（snap+，questions？）>><！ELEMENT捕捉（标题，doc url？伪代码url？，（树|阵列|图|堆叠|队列|问题参考？ ）>的LinkedList|条形图|节点）*，<！元件层积体<！元素界<！ATTLIST边界FONTSIZE<！ELEMENT列表项<！ATTLIST列表项<！元素标签（姓名？，界限？列表项目 *）>（空）>x1 CDATA #REQUIREDy1 CDATA #REQUIREDx2 CDATA #REQUIREDy2 CDATA #REQUIREDCDATA（标签）>color CDATA（#PCDATA）>3.1整体脚本组织JHAVE′-I的当前插件使用XML DTD（数据类型定义）为其脚本指定XML。对于那些不熟悉DTD的人 简言之，这样的DTD类似于语言的扩展巴科斯-诺尔范式（EBNF）描述。在图3中定义的DTDforJHAVE′-II指定可视化由称为show的标记实体定义。每个这样的节目都由一个或多个快照（即快照）组成，后面是零个或多个问题。快照包含标题、可选文档和伪代码URL、零个或多个数据结构（堆栈、队列、数组、链表、树或图形）以及快照的可选问题参考图三. 高级脚本DTD3.2数据结构每一个可以由当前JHAVE′-II插件呈现的六个数据结构都有自己的DTD定义。例如，考虑图4中的堆栈定义。堆栈中的数据由零个或多个列表项的序列组成。可选的bounds标签可以用来指定插件呈现的堆栈图片的位置和大小。列表项的color属性用于指定堆栈中每个数据项的颜色见图4。 堆栈数据结构当然，非线性数据结构（如树和图）具有更复杂的DTD定义。尽管如此，bounds标签和color属性在所有数据结构定义中以一致的方式134T. Naps等人/理论计算机科学电子笔记178（2007）129><！ELEMENT变量<！ELEMENT变量<！元素替换<！ATTLIST替换（变量 *）>（#PCDATA，replace）>（空）>var NMTOKEN #REQUIRED>3.3文档、伪代码和交互式问题JHAVE′-II为它的插件提供的支持包括s-o-cumetatio和d-pseu-docode窗口。文档窗口内容的DTD仅仅是对指定HTML文档的URL的伪代码窗口更加复杂，因为它们必须与学习者正在查看例如，图1显示了快速排序算法可视化的伪代码窗口除了程序清单之外，请注意调用堆栈和各个变量的当前值。这样一个伪代码窗口的DTD如图5所示。<！元件文档URL（#PCDATA）><！元件伪代码（调用堆栈？，节目单？变量？ ）>的<！元件调用堆栈（#PCDATA）><！元件节目列表（签名？，在线 *）><！元件签名（#PCDATA）><！元件<！ATTLIST线线（（#PCDATA|替换）+）>行号CDATA #IMPLIED图五. 伪码DTD交互式停下来思考问题的DTD也被定义。目前支持四种类型的问题-4结论在本文中，我们描述了下一代JHAVE′-II正在进行的工作的客户端服务器基于JHAVE′AVenvironme nt。 虽然这一新版本将由于进行了大量的增强，因此将所有JHAVE′数据流转换为XML格式。这种转换的积极成果将包括增强的可扩展性和可视化开发的易用性。5确认这项工作得到了美国国家科学基金会CSLI赠款DUE-0126494的支持。引用[1] Harold，E.和S. XML in a Nutshell，O'Reilly，2004年。[2] 纳普斯，S. 别这样，B。科尔德霍夫角 Les ka，G. R？oßling，W. Dann，A. 科尔霍宁湖Malmi，M. 麦克纳尔，J. Rantakokko和R.罗斯，评估可视化的教育影响，ACM SIGCSE公告35（2003），pp. 124-136T. Naps等人/理论计算机科学电子笔记178（2007）129135[3] 纳普斯， J. Eagan和L. 诺顿，Jha v'e-一个环境，以积极参与学生在网络- b as e d算法可视化，ACMSIGCSE公告32（2000年），页。109比113[4] 纳普斯，G. Robling，P.Brusilovsky，J.英语，D.Jarc，V.卡拉维尔塔角Leska，M.McNally，A.莫雷诺，R. Ross和J. Urquiza-Fuentes，开发基于XML的工具以支持用户与算法可视化的，ACM SIGCSE Bulletin37（2005），pp.123-138[5] 纳普斯，T。和B.Swander，一种面向对象的算法可视化方法-简单，可扩展和动态，ACM SIGCSEBulletin26（1994），pp.46比50[6] R？oßling，G. 和B. Freisle ben，Animalscript：An extensiblescriptinglanguageforaltainanimation，ACM SIGCSE Bulletin 33（2001），pp. 70比74[7] Stasko，J.，使用学生构建的算法动画作为学习辅助工具，ACM SIGCSE Bulletin29（1997），pp.25比29