算法可视化演示软件开发.docx
《算法可视化演示软件开发.docx》由会员分享，可在线阅读，更多相关《算法可视化演示软件开发.docx（55页珍藏版）》请在冰点文库上搜索。
算法可视化演示软件开发
编号：
审定成绩：
重庆邮电大学
毕业设计（论文）
设计（论文）题目：
算法可视化演示软件开发
学院名称：
计算机科学与技术
学生姓名：
专业：
班级：
学号：
指导教师：
答辩组负责人：
填表时间：
2012年6月
重庆邮电大学教务处制
摘要
算法可视化是研究程序性能行为的有力工具，也是近几十年新兴起的一个算法研究方向。
运行一个可视化的算法程序时，程序中不易被人理解的数据结构。
算法特征和程序功能可以以图形方式动态地显示在计算机屏幕上，用户可按屏幕上的的视图来分析算法和数据结构的细节，用各种视图展示程序运行的各个侧面。
伴随着可视化技术的大力发展，可视化技术在各个领域都得到了广泛应用。
目前,许多研究者已经肯定了算法可视化在数据结构教学方面的作用和地位,并且开始了在算法可视化教学方面的研究。
数据结构和算法是计算机课程教学的核心，教学难点在于它们的抽象性和动态性。
应用可视化教学，能使抽象的知识变得具体，执行过程更直观,理解起来也更容易。
本次此毕业设计的内容是设计并实现一个小型的可视化演示系统。
本系统主要是使用javax.swing图形界面，结合Java编程语言实现算法和所学的数据结构的算法思想来实现可视化的演示系统。
演示的算法包括插入排序、冒泡排序、选择排序三种排序算法的排序过程和二叉查找树的插入、删除、以及查找的过程，通过多个数列测试证明：
该可视化系统可以正确、精确的反映各算法的执行过程。
【关键词】算法可视化排序算法二叉查找树
ABSTRACT
Researchonalgorithmvisualizationisnotonlyapowerfultoolforprogramperformancebehavior,butalsoanewalgorithmfordirectioninrecentdecades.Runingavisualizationalgorithmprogramisnoteasytounderstooddatastructures,algorithms,features.programfunctionscanbedynamicallydisplayedgraphicallyonthecomputerscreen,theusercantanalyzealgorithmsanddatastructuresdetailviewingonthescreen,usingavarietyofviewsshowallrunningside.Withthevigorousdevelopmentofvisualizationtechnology,visualizationtechnologyinvariousfieldshasbeenwidelyused.Currently,manyresearchershaveconfirmedthealgorithmvisualizationinthedatastructure'sroleandstatusofteaching,andbeganteachinginthealgorithmvisualizationresearch.Datastructuresandalgorithmsarethecoreofteachingcomputercourses,teachingdifficultyliesintheirabstractanddynamic.ApplicationVisualizationTeaching,abstractknowledgecanbecomeconcrete,theimplementationprocessismoreintuitiveandeasiertobeunderstood.
Thecontentofthisgraduationprojectistodesignandimplementasmallvisualpresentationsystem.Thesystemismainlyusedjavax.swinggraphicalinterface,combinedwiththeJavaprogramminglanguagealgorithmsanddatastructureslearnedalgorithmideastovisualizethedemonstrationsystem.Demoalgorithmsincludinginsertionsort,bubblesort,selectionsortthreesortingalgorithmssortingprocessandabinarysearchtreeinsertion,deletion,andfindtheprocessbymultipleseriestested:
Thevisualizationsystemcancorrect,precisereflectthealgorithmimplementationprocess.
【Keywords】algorithmvisualizationSortingAlgorithmBinarysearchtree
前言
可视化（Visualizations）计算机图形学和图像处理技术，将数据转换成图形或图像在屏幕上显示出来，并进行交互处理的理论、方法和技术。
此次设计算法可视化（AlgorithmVisualizations）就是利用可视化技术将算法可视化[1]。
排序是计算机程序设计中的一种重要操作，其功能是一个数据元素（或者记录）的任意序列，从新排列成一个按关键字有序的序列。
在我们所学的数据结构中了解到了排序算法的原理，以及实现过程，但是不清楚它的具体过程是怎么样的。
算法的概念极为抽象，算法有时也枯燥难懂，所以很多时候就提不起学生的兴趣，此次的毕业设计所研究的就是在算法基础上结合图形界面动态的演示排序算法的具体实现过程，从一定程度上也可以提起学生的兴趣，让读者不仅从理论上理解它，更是从实践过程去接受知识，给学生更深的印象。
所要达到的目的是以生动、活泼、全新的教学系统，提供全新的环境提高学生的听课兴趣，增加学生的记忆。
并且本次毕业设计也选择了不同的排序算法，这样在演示的过程中，我们可以根据实现的复杂程度和执行速度等方面为该系统选择合适的排序算法，使之高效率运行，进而提高对排序算法的掌握程度[2]。
二叉树的算法、结构化查询语言等的研究对数据查询有着很重要的实际意义。
用二叉查找树的关系表的方法，可提高商品信息的查询效率。
此次毕业设计还选择了二叉树算法的动态演示，对研究二叉查找树是很有帮助，让大家更了解二叉查找树的实际意义，对研究更复杂的数据库关系打下了基础。
第一章绪论
第一节课题背景
随着社会和计算机技术的发展，如今，在可视化技术这个大家庭中不仅仅只有科学计算机可视化，它还包括了信息可视化、数据可视化、知识可视化等一系列的分支。
数据可视化有可能帮助人类在大量数据的分析和理解，并检测模式[3]。
近年来，各种可视化技术已经扩展到军事、医学、医学研究、经济、解释工程等各个领域。
其中有很多问题需要在以后的研究中加以解，从整体上来说，我国的可视化技术与世界先进水平还有很大的差距。
而算法可视化是研究其它更深层次领域的基础，因此在研究其它领域的可视化前，我们必须先搞清楚算法可视化这个概念。
由于数据结构中算法是算法可视化中最容易让读者理解和明白的算法，因此，此次设计主要以排序算法和二叉查找树的相关操作来研究。
排序在计算机辅助设计、计算机图形学、机器人、模式识别、基因排序学工程以及统计学等领域都具有广泛的应用，因此在排序的研究不仅有理论上的重要意义，而且有更大的实际应用价值。
又加上如今信息产业在快速的发展信息的流通量越来越大，这些信息数据不仅庞大而且杂乱无章，很难管理和查询，所以更加需要一种非常快捷而且有效的编排手段来整理这些数据信息，提高我们的工作效率。
第二节课题的目的与意义
设计并实现直观、容易被理解的算法的动态演示系统，是课题研究的目的。
随着计算机技术的不断发展，人们提出了各种算法，算法可视化在计算机领域里有十分重要的意义，并且应用广泛。
在当今信息发达的时代，面对着海量的无序数据信息，如果没有一个规则来编排和查询，就会给我们的工作和信息带来很大的不方便，所以利用计算机的高速运行和计算能力，编写出一种合适的排序软件，是十分必要的。
并且在设计的过程中也能让学生更加的了解排序算法和实现过程，使他们在以后的学习和工作中能找到更加高效的排序系统，提高学习效果和工作效率。
第三节论文结构
本次的论文共有六个章节，详细的阐述了算法可视化的具体实现：
第一章，主要介绍了研究的背景、内容、目的和意义。
第二章，简述相关的Java知识，进一步了解Java的发展史、特性，还介绍Java图形界面的相关知识和相关算的一些知识。
第三章，通过仔细研究，进行系统地需求分析。
第四章，明确项目模块，进行系统概要设计。
第五章，可视化算法的具体实现、及其功能。
第六章，系统测试，以及在做毕设的过程中遇到的问题，最后对本次毕设进行总结。
第二章相关知识概述
第一节Java知识相关概述
一、Java的发展史
Java是由Sun公司1995年5月开发的新一代面向对象编程语言（简称Java语言）和Java平台的总称。
Java的正式推出是1995年，它是JamesGosling和同事们一起研发的，HotJava浏览器是用Java实现的，它（支持Javaapplet）显示了Java的魅力：
动态的Web、跨平台、Internet计算。
它可以应用在各种不同的平台上，正逐步成为internet应用的主要开发语言。
此后，Java不仅被广泛接受还推动了Web的快速发展，我们所用的一般的浏览器均支持Javaapplet。
另一方面，Java技术也一直在更新。
Java是由四个方面组成的：
Java编程语言、Java类文件格式、Java虚拟机和Java应用程序接口（JavaAPI）。
Java技术具有突出的的平台移植性、高效性、通用性和安全性，它应广泛的用于数据中心、个人PC、移动电话、游戏控制台、互联网以及科学超级计算机，并且在全球拥有的开发者专业社群是最大的。
在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔的前景[4]。
二、Java的主要特性
Java的主要特性有平台无关性、安全性、面向对象特性、简单性、动态特性、多线程性、健壮性等特性[5]。
Java语言是体系结构中立的，是可移植的。
是解释型的，而且是高性能的，是动态的[6]。
Java语言的设计的其中一个目标就是要适应环境的动态变化。
能够把程序需要的类动态的载入到运行环境，同时所需要的类也可以通过网络载入。
这样对软件的升级很有用。
Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。
Java语言的优良特性使得Java应用有很高的的可靠性和健壮性，同时应用系统维护的费用也相对减少了。
Java对对象技术的全面支持和Java平台内嵌的API能减少应用系统的开发所需要的时间还能有效降低成本。
Java的编译一次，其随处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。
尤其是Java企业应用编程接口（JavaEnterpriseAPIs）为企业计算及电子商务应用系统提供了丰富的类库很相关技术。
Java语言是面向对象的，面向对象技术的基本特征主要有抽象性、封装性、继承性和多态性。
而在本次设计中主要涉及到的是JavaSwing包。
三、JDK平台相关信息
本系统利用JavaJDK作为开发平台，利用它的可视化界面和图形用户界面在硬件环境：
PC兼容机，1G内存以及软件环境MicrosoftWindows7操作系统（可以移植到大部分机器上）下一个演示不同的算法，利用Java编写的图形界面演示的动态交换过程。
JDK是Java开发工具包（Javadevelopmentkit））的缩写，是整个Java的核心，是一种用于构建在Java平台上发布的应用程序包括了Java运行环境（JavaRuntimeEnvirement），一堆Java工具和Java基础的类库（rt.jar）。
不论什么Java应用服务器实质都是内置了某个版本的JDK。
因此掌握JDK是学好Java的第一步。
最主流的JDK是Sun公司发布的JDK，除了Sun之外，还有很多公司和组织都开发了自己的JDK，例如IBM公司开发的JDK，BEA公司的Jrocket，还有GNU组织开发的JDK等等。
其中IBM的JDK包含的JVM（JavaVirtualMachine）运行效率要比SunJDK包含的JVM高出许多。
而专门运行在x86平台的Jrocket在服务端运行效率也要比SunJDK好很多。
但无论怎么说，我们都要需要先把SunJDK掌握好。
JDK1.1及其以后的版本都支持委托模型。
在委托事件处理模型中，用户操作引发的事件对象仍然传递给相应的组件，但是为了接受事件并进行事件处理，组件必须注册一个事件处理程序，这种事件处理程序称为事件的监听程序（Listener）。
事件的监听程序可以定义在组件所在的类，也可以定义在其他的类里，而对事件的处理，则由组件委托给事件监听所在的类来完成。
第二节Java图形界面技术概述
一、JavaSwing相关概述
在Java中设计图形界面程序时，通常选用AWT组件和Swing组件。
Java的出现带来了抽象窗口工具（AWT），其设计目标是希望构建一个通用的GUI（图形用户界面）使得利用它编程的程序能够运行在所有平台上，以实现SUN你公司的口号“一次编写，随处运行”。
SUN公司推出了新的用户界面库：
Swing，相对AWT来说，Swing功能更强大、使用更方便，它的出现是使得Java的图形用户上了一个台阶[7]。
Swing的关键在于一旦有了顶级容器，则其中所有构件都可以用Java编写，例如，将按钮（JButton）放入框架（JFrame）中时，本机操作系统不需要了解该按钮的任何信息，该按钮完全用Java编写且无同级组件，因而组件称为“轻”组件。
Swing具有以下几点优势：
①丰富的组件类型:
Swing提供了非常广泛的标准组件。
这些组件和SWT一样丰富。
基于它良好的可扩展性，除了标准组件，Swing还提供了大量的第三方组件。
许多商业或开源的Swing组件库在开发多年后都已经可以方便地获取了。
②丰富的组件特性:
Swing不仅包含了所有平台上的特性，它还支持根据程序所运行的平台来添加额外特性。
Swing组件特性遵循特定原则，易于扩展，因此能够提供较SWT和AWT更多的功能。
③好的组件API模型支持:
Swing遵循MVC模式，这是一种非常成功的设计模式。
它的API成熟并设计良好。
经过多年的演化，Swing组件APIs变得越来越强大，灵活和可扩展。
它的API设计被认为是最成功的GUIAPI之一。
较之SWT和AWT更面向对象，也更灵活而可扩展。
④标准的GUI库：
Swing和AWT一样是JRE中的标准库。
因此，你不用单独地将它们随你的应用程序一起分发。
它们是平台无关的，不用担心平台兼容性。
⑤成熟稳定：
由于它是纯Java实现的，不会有SWT的兼容性问题。
Swing在每个平台上都有相同的性能，不会有明显的性能差异。
⑥可扩展和灵活性。
Swing完全由Java代码实现。
Swing基于MVC的结构使得它可以发挥Java作为一门面向对象语言的优势。
它提供了许总体上良好的性能。
Swing也有着许多不足之处：
比如Swing比AWT和SWT更多的内存消耗。
Swing自己实现了所有组件。
因此，它在运行时装载了大量的类。
而在运行时Java在堆上创建小的对象导致了额外的堆空间消耗。
而许多小的对象难以有效地被垃圾回收机制回收。
因此，Swing应用程序通常会因无法及时回收冗余的对象而导致性能下降。
二、容器和布局
我们都知道，Java的GUI界面定义是由AWT类包和Swing类包来完成的[8]。
它在布局管理上采用了容器和布局管理分离的方案。
也就是说，容器只管将其他组件放入其中，而不管这些组件是如何放置的。
对于布局的管理交给专门的布局管理器类（LayoutManager）来完成。
Java中的容器是用来放置其它组件的一种特殊部件（如标签、按钮、文本框等），用Containers来描述容器，容器组件Window不需要其他组件支撑，独立显示。
容器主要有面板和框架两类，在AWT中，Frame是对应于框架的类，大部分AWT组件在Swing中都有等价的组件，他们在形式上相差一个“J”。
Dialog表示没有菜单条，但是不能改它的变大小。
Pane一定要放在Web浏览器窗口（或者Window组件）中才可以显示。
它是一矩形域，在里面可以摆放其它的组件，也可以有自己的布局管理器。
基本方法是remove（Component comp）删除指定组件、add（Componentcomp）将指定组件放到容器中、add（Componentcomp，intindex）,setLayout（LayoutManager mgr）设置容器布局。
在Java中还提供了支持用户界面元素自动定位的布局工具。
容器的组件布局,负责确定组件在容器中的位置和大小。
布局管理有流布局管理、边界布局管理和网格布局三种布局管理器。
调用容器的setLayout（布局管理器对象）方法，为容器指定某种布局管理器的一个对象。
当容器需要确定组件大小和定位组件的时候，就会发消息给布局管理器对象，让它完成该项工作。
直接管理组件调用容器setLayout（null）方法，关闭布局管理器。
调用每一个组件的setLocation（）方法决定组件位置。
调用每一个组件的setSize（）方法决定其大小.直接管理组件将失去平台无关性。
布局管理器种类FlowLayout:
在一行上水平排列组件，直到该行没有足够的空间为止，然后另起一行继续排列当用户缩放容器时，布局管理器将自动进行控制，重新排列。
BorderLayout（边界布局管理器）的布局分为东、南、西、北、中五个位置。
可以把组件放在这五个位置的任意一个，假如没有指定位置，就把中作为默认的位置。
GridLayout（网格布局管理器）在你创建用户界面时，经常像将对象按网格一样均匀排列，例如一行或者一列单选按钮，它所确保的所有构件占用的空间完全相同，创网格由应占的行数和列数决定。
网格布局管理器具有更复杂、功能更强的网格布局。
网格布局的每一个组件作为一个卡片，该容器只显示多个卡片中的某一个。
setLayout（newGridLayout（行数,列数））;setLayout（newGridLayout（行数,列数,行间隔,列间隔））;调用容器的方法add（）将组件加入容器，组件填入容器的顺序将按照第一行第一个、第一行第二个、……每个网格中都必须填入组件，假如希望是空白的网格，可以给它添加一个空的标签：
add（newLabel（））。
三、事件处理
在一个GUI程序中，为了与用户进行交互，需要接受键盘和鼠标的操作。
当用户执行一个用户界面级的操作时，会引发一个事件，通常一个键盘和鼠标操作将引发一个系统事先定义好的事件，用户程序只需要编写代码定义每个事件发生时程序应做何种响应即可[8]。
事件：
说明“发生了什么事情”的对象。
系统根据用户的操作构造出相应事件类的对象。
事件可以分为焦点事件、键盘事件、鼠标事件。
事件源：
有自己的方法，通过它像其注册事件监听器，事件监听器是一个实例。
事件处理程序：
是一个方法，它接收一个事件对象然后分析这个对象最后完成对该事件的处理。
每个事件有一个相应的监听者接口，它规定了能够接收（并处理）该类事件的方法的规范。
图2.1界面构成
第三节相关算法的介绍
一、冒泡排序
1、什么是交换
所谓交换，就是根据序列中两个元素关键字的比较结果对换这两个记录在序列中的位置，基于交换排序的算法有很多，本次设计以冒泡排序来为例子，更容易让人们理解交换的概念。
2、冒泡排序的概念
冒泡排序算法的基本思想是：
假设待排序长为n，从后向前或者从前向后两两比较相邻元素的值。
这里我假如是从从小到大排序，若为逆序（即A[i-1]>A[i]）,则交换他们直到序列比较完，我们称他们为一趟冒泡，结果将最小的元素交换到待排元素的序列的第一个位置，下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，......，这样最多做n-1趟冒泡排序就把所有元素排好序[9]。
3、冒泡排序的性能分析
冒泡排序的性能分析如下：
空间效率：
仅使用了常数个辅助单元，因而空间复杂度为0
（1）。
时间效率：
当初始序列有序时，比较次数为n-1次，移动次数为0，从而最好情况下的时间复杂度为O（n）；当初始序列为逆序时，需要进行n-1趟排序，第i趟需要进行n-i次关键字的比较，而且每次比较都需要移动三次来交换元素位置。
这种情况下:
元素的比较次数=
=n（n-1）/2
元素的移动次数：
=
=3n（n-1）/2
从而最坏情况下时间复杂度为O（n*n）。
稳定性：
由于当i>j且A[i].key=A[j].key时不会交换两个元素，从而冒泡排序算法是一个稳定的排序算法。
由此可以总结出冒泡排序的优点是具有稳定性，缺点是慢，每次只能移动相邻的两个数据。
冒泡排序虽然可能不是最好的做法排序[10]，但确是经常用的一种排序算法。
二、插入排序
1、什么是插入排序
它的基本思想就是每次将一个待排序的记录，按其关键字大小插入到前面已经排好的子序列中，直到完成了全部记录插入。
由插入排序可以引申出三种重要的排序算法：
直接插入排序、折半插入排序、希尔排序。
在这里主要介绍直接插入排序。
2、直接插入插入排序的概念
直接插入排序是一种简单的排序方法，它的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。
例如，已知待排序的一组记录的初始序列如下所示：
表2.1排序初始序列
有序序列L[1…i-1]
L（i）
无序序列L[i+1…n]
为了实现将元素L（i）插入到已有序的子序列L[1.......i-1]中我们需要执行以下操作（为避免混淆，下面用”L[]”表示一个表，而L（）表示一个元素
排序L（i）在L[1.......i-1中的出入位置k。
将L[k.......i-1]中所有元素后移一个位置。
将L（i）复制到L（k）。
为了实现对L[1...n]的排序，可以将L
（2）到L（n）依前面次插入到前面已经排好的子序列当中，初始假设L[1]是一个已经排好的子序列，上述操作执行n-1次，就能得到一个有序的表插入排序在实现上通常采用的就是就地排序（空间复杂度为O
（1））,因而在从后向前的比较过程中，需要反复把已经排好的元素逐步向后移位，为新元素提供插入空间。
3、直接插入排序的性能分析
直接插入排序的性能分析如下：
空间效率：
仅使用了常数个辅助单元，因而空间复杂度为0（1
升级会员 