2012年第12期福建电脑
可移动交互式对象的设计
易著梁1，崔业勤2
（1、南宁职业技术学院广西南宁5300082、廊坊师范学院河北廊坊065000）
【摘要】：课堂教学中，经常需要用到可随意进行移动的交互式对象，藉此来辅助展示一些复杂的概念和理论，目前常用的课件制作软件PowerPoint虽然自带了一些动画实现的功能，但一般情况下只能按照用户事先设计好的路径和方式移动，很难满足随意拖动的需求。本文通过介绍KMP算法中，可移动交互式对象的实现方法，提供了解决此类问题的思路。
【关键词】：可移动交互式对象，KMP，AuthorWare
“数据结构”课程的教学过程中，有关KMP字
符串匹配算法的演示，是比较典型的可移动交互
式对象的应用。由于该算法较为复杂，在教学过程
中大部分教师往往通过多种教具和方法，学生才
得以理解和掌握。
过去，任课教师是通过自制的一个个的纸质字母卡片，排列在一起形成目标串和模式串，然后再由代表指向两个字符串的i和j指针卡片，通过手工移动模式串和指针卡片，来演示算法匹配的过程，非常形象，使观看者很容易就了解了原本复杂的算法，但手工制作，首先是比较麻烦，其次要想移动和调换内容的时候，那些排好队的小卡片就队形散乱，不便操作，最后是要想在课堂上授课，就必须借助于实物投影仪，才能让整个教室的学生都能看到。所有这些自然是受制于当时计算机软硬件发展的制约，随着计算机辅助教学软件的开发，此类算法演示可以在无编程的情况下轻松实现，本文就是以AuthorWare为制作工具，介绍了如何实现KMP算法的模拟演示。
KMP算法是目前性能较好的字符串匹配算法，匹配算法是日常生活中解决实际问题常用的算法，比如在Word中查一篇文章的某些字词，就是匹配算法的应用，按照传统的思维，要在一篇文章中寻某些关键字，尤其要借助于计算机来完成这项工作，就需要不断的按位比较，如图1所示，当前位置匹配时，向后移动指针，继续匹配其它字符，当出现如图2所示的字符不匹配的情况时，i和j指针都要回溯到如图3所示的位置，重新进行比较，因此，传统的匹配算法，效率很差，其时间复杂度简化后可表示为：目标串长度×模式串长度。
KMP算法将算法的复杂度降低为目标串长度，从而大大提高了算法的效率，那么其原理是什么呢？在KMP算法中，目标串的指针在出现不匹配的字符时，是不回溯的，而模式串的指针可能需要全部或者部分回溯。
如图4所示，是模式串指针全部回溯的情况，注意观察，此时，i指针回溯到开始位置。而图5中，目标串的j指针同样不回溯（这是KMP算法的关键），则是模式串指针i部分回溯，是否需要回溯，回溯多少，经过观察后可以推断，是由模式串的特性所决定的。如图4中，模式串的各子串均不相同，可以验证，在任何位置出现不匹配，i指针都要回溯到开始位置。
而图5中，模式串的构成则比较有趣，经过观察会发现，其中有重复的子串“ab”，既字符“c”
前
119
福建电脑2012年第12期
面，其前缀子串是“ab”，其后缀子串也是“ab”，因此，当字符“c”不匹配时，指向模式串的指针只需回溯到字符“a”的位置，直接省略了前面的子串“ab”的比较。正是有了D.E.Knuth、J.H.Morris和V. R.Pratt细致的观察和科学的推算，KMP算法中模式串的每个字符不匹配时指针回溯的位置，有了如下规则（字符的位置描述以本文中为准，下标从0开始）：其中，模式串的第一个位置的回溯标识-1，并不代表实际的位
置，而是当第一个字符就不匹配时，需要目标串指针向后移动一位，模式串指针位置不变，其余两种情况的值均代表模式串指针的实际回溯位置。
以图5中的模式串“ababc”为例，按照以上规则，可以推出该模式串每个字符位置上对应的回溯位置分别为-1，0，0，1，2，因此当字符“c”不匹配时，按照回溯位置，指针应回溯到2的位置，也就是第二个字符“a”所在的位置（注意：位置下标从0开始算起）。而图4中的模式串“abc”其回溯位置可以推得为-1，0，0，因此不管在哪个位置不匹配，指针都要回溯到0位置，也就是模式串的开始位置。
以上对于KMP算法的详细描述，是为了证实该算法的理解确实存在一定难度，在实际教学中，模式串的移动，指向目标串和模式串的i和j指针的移动，只有做成可以随意移动的对象的形式，算法的演示才能更加直接易懂。下面通过展示部分算法实现的流程，看如何通过AuthorWare实现这类可移动交互式对象的制作。
图7、图8是笔者为讲述字符串模式匹配算法所作的设计的一部分，实际运行效果中，指针i 和j还有模式串是可以沿水平直线在规定范围内移动的，这样可以避免由于鼠标操作不精确所带来的位置不易定位，除此之外，下方还设有4个可交互式按钮，分别用来完成初始化（i，j指针和模式串恢复原位），时间复杂度（转入另一段演示程序，论证传统模式匹配算法的时间复杂度的推算），KMP算法（转入KMP算法的演示），退出（退出整个演示窗口）。这样设计，使整个算法的演示不光易懂，还非常流畅。由于交
互性的设计是Authorware特有的优势，因此所有这些功能实现起来都比较容易。笔者通过课堂教学证实，通过该设计，一次讲述，理解率几乎达到100%，效果令人满意。
下面将设计中所涉及的可移动交互式对象实现的关键点介绍如下：
一、独立对象单独控制
首先确保，每一个要单独控制的对象分别在独立的显示图标中，如图7所示，可以看到两个指针和模式串，目标串分别在不同的显示图标中。
二、属性设置是关键
字符串长度17模式串长度对应显示图标的属性中，对象位置的设置，是程序运行后对象可做何种运动的关键，其中包含4种方式：
（一）不能改变
该种设置演示窗口中的对象将不能被用户拖动，在本例中，目标串即可设置成“不能改变”，防止被用户误拖动，需要注意的是，只有当程序打包后，不能移动的属性才能体现出来。
（二）在屏幕上
设置成在屏幕上这种方式，用户可拖动对象到屏幕上任意位置(不能超出屏幕)，这适用于可随意拖动的情况，例如笔者曾经用该属性完成了小学语文课件“走进田园”的一个环节——
—“布置自己的家园”，如图9所示，预先在不同的显示图标中绘制房屋，果树，家畜等元素，运行程序时，用户可随意拖动这些对象，在想象中布置自己的家园
。
图9
布置自己的家园120
2012年第12期福建电脑
（上接第36页）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
表1与“北京博看文思”联合培养实施方案
头人”的培养，采取有力措施，创造良好的环境，造就一批在本校、本地区、本省甚至全国有影响的科研团队，以此带动学科学术梯队的形成和教师整体师资水平的提高。此外，积极聘请来自行业、企业的兼职教师参与到教学过程中来优化教师队伍整体结构以促进教学发展。
五、结束语
改革的过程是一个艰难的过程，创新的过程也是一个艰难的过程。要完成整个软件工程专业的培养计划，
必须有企业和行业的参与，开展工学结合和校企合作。也是只有这样，才能将学与术、产与研、通与专有效结合，培养出兼具科学家头脑和工程师实践能力的卓越工程师。
参考文献：
[1]林建.工程师的分类与工程人才培养[J].清华大学教育研究,2010,31(1):51-60
[2]教育部高学校软件工程专业教学指导分委员会.高等学校软件工程专业规范[M].北京：高等教育出版社,2011.
[3]乔恩·R
·卡曾巴赫.团队的智慧———创建绩优组织[M].北京：经济科学出版社,1999:111-120
（三）在路径上
本文中，两个指针和模式串对象均被设置成该种方式，可以实现对象沿路径在指定范围内拖动的要求，设置成该属性后，需要在编辑窗口中拖动对象设定其运动路径，通过控制点可以调整路径的形状，双击控制点，还可以将直线路径改为曲线路径，如图10所示，从而对于模拟宇宙行星的运行轨迹类的曲线运动提供解决方案。
（四）在区域内
此种模式提供对象在一个限定的区域内移动，例如物理实验中物体在容器中的运动，可以通过该类属性实现。设置成该属性后，同样需要在编辑窗口拖动对象，完成限定区域范围的设置。
三、交互按钮功能实现（一）初始化按钮
初始化按钮的流程中通过附着在组图标上的计算功能，输入控制语句Restart()即可实现复位功能。
（二）时间复杂度和KMP 算法演示按钮
它们分别是两段演示程序的入口，通过进入组图标，进行相应流程设计即可。
（三）退出按钮
该按钮功能的实现同初始化按钮，只不过其中的控制语句变为了Quit （）命令。
四、打包程序
该实例中，由于所涉及的对象都是用户自绘
制的字符和图形，因此在打包成可直接执行的文件时，相对比较简单，选择文件菜单中中“发布”下的“发布设置”，将其中的“With Run time for Win -dow98,ME,NT,200,or XP ”前面的选项勾选上，然后单击Publish 按钮，进行发布打包，这样可以直接生成可执行文件，同时把必要的支持文件一起拷贝到可执行文件所在的位置，用户只需将所有文件一起拷贝，就可以在没有安装AuthorWare 软件的机器中正常运行，如果设计中包含了动画，声音，或者视频，则最好把相应的媒体文件一起拷贝到相应文件夹下。生成可执行文件的好处还可以在PowerPoint 等的媒体集成软件中将其嵌入运行，这样整个课堂授课就会很流畅，无割裂之感。
本文中有关流程实现的部分篇幅不多，这对于没有AuthorWare 基础的读者来讲，可能无法达到掌握的目的，但只要通过学习，首先掌握该软件的使用，相信以上算法实现起来是非常轻松的。
本文通过介绍字符串模式匹配算法，尤其是KMP 算法的原理，引出可移动交互式对象在课堂授课中的重要性，并提供了解决问题的一种方案，希望可以为电化教育中此类问题的解决提供思路。
参考文献：
[1]严蔚敏.数据结构.清华大学出版社，1997.
[2]胡伏湘，龚中良.多媒体技术教程：案例、训练与课程设计.清华大学出版社,2006.
121

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。