算法可视化演示软件开发

重庆邮电大学本科毕业设计(论文) 编 号： 审定成绩： 重庆邮电大学毕业设计（论文）设计（论文）题目：算法可视化演示软件开发学 院 名 称 ：计算机科学与技术学 生 姓 名 ：专 业 ：班 级 ：学 号 ：指 导 教 师 ：答辩组 负责人 ：填表时间：2012年 6 月重庆邮电大学教务处制 - IV -摘 要算法可视化是研究程序性能行为的有力工具，也是近几十年新兴起的一个算法研究方向。运行一个可视化的算法程序时，程序中不易被人理解的数据结构。算法特征和程序功能可以以图形方式动态地显示在计算机屏幕上，用户可按屏幕上的的视图来分析算法和数据结构的细节，用各种视图展示程序运行的各个侧面。伴随着可视化技术的大力发展，可视化技术在各个领域都得到了广泛应用。目前,许多研究者已经肯定了算法可视化在数据结构教学方面的作用和地位,并且开始了在算法可视化教学方面的研究。数据结构和算法是计算机课程教学的核心，教学难点在于它们的抽象性和动态性。应用可视化教学，能使抽象的知识变得具体，执行过程更直观,理解起来也更容易。本次此毕业设计的内容是设计并实现一个小型的可视化演示系统。本系统主要是使用javax.swing图形界面，结合Java编程语言实现算法和所学的数据结构的算法思想来实现可视化的演示系统。演示的算法包括插入排序、冒泡排序、选择排序三种排序算法的排序过程和二叉查找树的插入、删除、以及查找的过程，通过多个数列测试证明：该可视化系统可以正确、精确的反映各算法的执行过程。【关键词】 算法可视化 排序算法 二叉查找树ABSTRACTResearch on algorithm visualization is not only a powerful tool for program performance behavior, but also a new algorithm for direction in recent decades. Runing a visualization algorithm program is not easy to understood data structures, algorithms, features. program functions can be dynamically displayed graphically on the computer screen, the user can tanalyze algorithms and data structures detail viewing on the screen, using a variety of views show all running side. With the vigorous development of visualization technology, visualization technology in various fields has been widely used. Currently, many researchers have confirmed the algorithm visualization in the data structures role and status of teaching, and began teaching in the algorithm visualization research. Data structures and algorithms are the core of teaching computer courses, teaching difficulty lies in their abstract and dynamic. Application Visualization Teaching, abstract knowledge can become concrete, the implementation process is more intuitive and easier to be understood.The content of this graduation project is to design and implement a small visual presentation system.The system is mainly used javax.swing graphical interface, combined with the Java programming language algorithms and data structures learned algorithm ideas to visualize the demonstration system . Demo algorithms including insertion sort, bubble sort, selection sort three sorting algorithms sorting process and a binary search tree insertion, deletion, and find the process by multiple series tested: The visualization system can correct, precise reflect the algorithm implementation process.【Key words】 algorithm visualization Sorting Algorithm Binary search tree目 录前 言1第一章 绪论2第一节 课题背景2第二节 课题的目的与意义2第三节 论文结构3第二章 相关知识概述4第一节 Java知识相关概述4一、Java的发展史4二、Java的主要特性4三、JDK 平台相关信息5第二节 Java图形界面技术概述5一、 Java Swing相关概述5二、容器和布局7三、事件处理8第三节 相关算法的介绍9一、冒泡排序9二、插入排序10三、选择排序12四、 二叉查找树12第四节 本章小结15第三章 需求分析17第一节 系统功能需求17一、系统设计目标17二、系统功能需求17第二节 系统运行环境18第三节 本章小结18第四章 系统设计19第一节 系统总体描述19第二节 模块设计20一、算法模块设计20二、界面模块设计22第三节 系统流程图25第四节 本章小结26第五章 系统实现27第一节 可视化主界面的实现27第二节 排序算法界面所实现的功能28第三节 二叉查找树可视化功能的实现31第四节 本章小结33第六章 系统测试34第一节 问题解决及测试结果34一、 遇到的问题34二、解决的方法34三、测试结果34第二节 本章小结41结 论42致 谢43参考文献44附 录45一、英文原文45二、英文翻译52重庆邮电大学本科毕业设计(论文)前 言可视化（ Visualizations）计算机图形学和图像处理技术，将数据转换成图形或图像在屏幕上显示出来，并进行交互处理的理论、方法和技术。此次设计算法可视化（ Algorithm Visualizations）就是利用可视化技术将算法可视化1。排序是计算机程序设计中的一种重要操作，其功能是一个数据元素（或者记录）的任意序列，从新排列成一个按关键字有序的序列。在我们所学的数据结构中了解到了排序算法的原理，以及实现过程，但是不清楚它的具体过程是怎么样的。算法的概念极为抽象，算法有时也枯燥难懂，所以很多时候就提不起学生的兴趣，此次的毕业设计所研究的就是在算法基础上结合图形界面动态的演示排序算法的具体实现过程，从一定程度上也可以提起学生的兴趣，让读者不仅从理论上理解它，更是从实践过程去接受知识，给学生更深的印象。所要达到的目的是以生动、活泼、全新的教学系统，提供全新的环境提高学生的听课兴趣，增加学生的记忆。并且本次毕业设计也选择了不同的排序算法，这样在演示的过程中，我们可以根据实现的复杂程度和执行速度等方面为该系统选择合适的排序算法，使之高效率运行，进而提高对排序算法的掌握程度2。二叉树的算法、结构化查询语言等的研究对数据查询有着很重要的实际意义。用二叉查找树的关系表的方法，可提高商品信息的查询效率。此次毕业设计还选择了二叉树算法的动态演示，对研究二叉查找树是很有帮助，让大家更了解二叉查找树的实际意义，对研究更复杂的数据库关系打下了基础。第一章 绪论第一节 课题背景随着社会和计算机技术的发展，如今，在可视化技术这个大家庭中不仅仅只有科学计算机可视化，它还包括了信息可视化、数据可视化、知识可视化等一系列的分支。数据可视化有可能帮助人类在大量数据的分析和理解，并检测模式3。近年来，各种可视化技术已经扩展到军事、医学、医学研究、经济、解释工程等各个领域。其中有很多问题需要在以后的研究中加以解，从整体上来说，我国的可视化技术与世界先进水平还有很大的差距。而算法可视化是研究其它更深层次领域的基础，因此在研究其它领域的可视化前，我们必须先搞清楚算法可视化这个概念。由于数据结构中算法是算法可视化中最容易让读者理解和明白的算法，因此，此次设计主要以排序算法和二叉查找树的相关操作来研究。排序在计算机辅助设计、计算机图形学、机器人、模式识别、基因排序学工程以及统计学等领域都具有广泛的应用，因此在排序的研究不仅有理论上的重要意义，而且有更大的实际应用价值。又加上如今信息产业在快速的发展信息的流通量越来越大，这些信息数据不仅庞大而且杂乱无章，很难管理和查询，所以更加需要一种非常快捷而且有效的编排手段来整理这些数据信息，提高我们的工作效率。第二节 课题的目的与意义设计并实现直观、容易被理解的算法的动态演示系统，是课题研究的目的。随着计算机技术的不断发展，人们提出了各种算法，算法可视化在计算机领域里有十分重要的意义，并且应用广泛。在当今信息发达的时代，面对着海量的无序数据信息，如果没有一个规则来编排和查询，就会给我们的工作和信息带来很大的不方便，所以利用计算机的高速运行和计算能力，编写出一种合适的排序软件，是十分必要的。并且在设计的过程中也能让学生更加的了解排序算法和实现过程，使他们在以后的学习和工作中能找到更加高效的排序系统，提高学习效果和工作效率。第三节 论文结构本次的论文共有六个章节，详细的阐述了算法可视化的具体实现：第一章，主要介绍了研究的背景、内容、目的和意义。第二章，简述相关的Java知识，进一步了解Java的发展史、特性，还介绍Java图形界面的相关知识和相关算的一些知识。第三章，通过仔细研究，进行系统地需求分析。第四章，明确项目模块，进行系统概要设计。第五章，可视化算法的具体实现、及其功能。第六章，系统测试，以及在做毕设的过程中遇到的问题，最后对本次毕设进行总结。第二章 相关知识概述第一节 Java知识相关概述一、Java的发展史Java是由Sun公司1995年5月开发的新一代面向对象编程语言（简称Java语言）和Java平台的总称。Java的正式推出是1995年，它是James Gosling和同事们一起研发的，HotJava浏览器是用Java实现的，它（支持Java applet）显示了Java的魅力：动态的Web、跨平台、Internet计算。它可以应用在各种不同的平台上，正逐步成为internet应用的主要开发语言。此后，Java不仅被广泛接受还推动了Web的快速发展，我们所用的一般的浏览器均支持Java applet。另一方面，Java技术也一直在更新。Java是由四个方面组成的：Java编程语言、Java类文件格式、Java虚拟机和Java应用程序接口(Java API)。Java 技术具有突出的的平台移植性、高效性、通用性和安全性，它应广泛的用于数据中心、个人PC、移动电话、游戏控制台、互联网以及科学超级计算机，并且在全球拥有的开发者专业社群是最大的。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔的前景4。二、Java的主要特性Java的主要特性有平台无关性、安全性、面向对象特性、简单性、动态特性、多线程性、健壮性等特性5。Java语言是体系结构中立的，是可移植的。是解释型的，而且是高性能的，是动态的6。Java语言的设计的其中一个目标就是要适应环境的动态变化。能够把程序需要的类动态的载入到运行环境，同时所需要的类也可以通过网络载入。这样对软件的升级很有用。Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java语言的优良特性使得Java应用有很高的的可靠性和健壮性，同时应用系统维护的费用也相对减少了。Java对对象技术的全面支持和Java平台内嵌的API能减少应用系统的开发所需要的时间还能有效降低成本。Java的编译一次，其随处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。尤其是Java企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了丰富的类库很相关技术。Java语言是面向对象的，面向对象技术的基本特征主要有抽象性、封装性、继承性和多态性。而在本次设计中主要涉及到的是Java Swing包。三、JDK 平台相关信息本系统利用Java JDK作为开发平台，利用它的可视化界面和图形用户界面在硬件环境：PC兼容机，1G 内存以及软件环境Microsoft Windows7操作系统（可以移植到大部分机器上）下一个演示不同的算法，利用Java编写的图形界面演示的动态交换过程。JDK是Java开发工具包（Java development kit)）的缩写，是整个Java的核心，是一种用于构建在Java平台上发布的应用程序包括了Java运行环境（Java Runtime Envirement），一堆Java工具和Java基础的类库(rt.jar)。不论什么Java应用服务器实质都是内置了某个版本的JDK。因此掌握JDK是学好Java的第一步。最主流的JDK是Sun公司发布的JDK，除了Sun之外，还有很多公司和组织都开发了自己的JDK，例如IBM公司开发的JDK，BEA公司的Jrocket，还有GNU组织开发的JDK等等。其中IBM的JDK包含的JVM（Java Virtual Machine）运行效率要比Sun JDK包含的JVM高出许多。而专门运行在x86平台的Jrocket在服务端运行效率也要比Sun JDK好很多。但无论怎么说，我们都要需要先把Sun JDK掌握好。JDK1.1及其以后的版本都支持委托模型。在委托事件处理模型中，用户操作引发的事件对象仍然传递给相应的组件，但是为了接受事件并进行事件处理，组件必须注册一个事件处理程序，这种事件处理程序称为事件的监听程序（Listener）。事件的监听程序可以定义在组件所在的类，也可以定义在其他的类里，而对事件的处理，则由组件委托给事件监听所在的类来完成。第二节 Java图形界面技术概述一、 Java Swing相关概述在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设计被认为是最成功的GUI API之一。较之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(Componentcomp) 删除指定组件、add(Component comp) 将指定组件放到容器中、add(Component comp，int index), setLayout(LayoutManagermgr)设置容器布局。在Java中还提供了支持用户界面元素自动定位的布局工具。容器的组件布局 ,负责确定组件在容器中的位置和大小。布局管理有流布局管理、边界布局管理和网格布局三种布局管理器。调用容器的setLayout(布局管理器对象) 方法，为容器指定某种布局管理器的一个对象。当容器需要确定组件大小和定位组件的时候，就会发消息给布局管理器对象，让它完成该项工作。直接管理组件调用容器setLayout(null) 方法，关闭布局管理器。调用每一个组件的setLocation()方法决定组件位置。调用每一个组件的setSize()方法决定其大小.直接管理组件将失去平台无关性。布局管理器种类FlowLayout: 在一行上水平排列组件，直到该行没有足够的空间为止，然后另起一行继续排列当用户缩放容器时，布局管理器将自动进行控制，重新排列。BorderLayout（边界布局管理器）的布局分为东、南、西、北、中五个位置。可以把组件放在这五个位置的任意一个，假如没有指定位置，就把中作为默认的位置。GridLayout（网格布局管理器）在你创建用户界面时，经常像将对象按网格一样均匀排列，例如一行或者一列单选按钮，它所确保的所有构件占用的空间完全相同，创网格由应占的行数和列数决定。网格布局管理器具有更复杂、功能更强的网格布局。网格布局的每一个组件作为一个卡片，该容器只显示多个卡片中的某一个。setLayout(new GridLayout(行数, 列数);setLayout(new GridLayout(行数, 列数,行间隔,列间隔);调用容器的方法add()将组件加入容器，组件填入容器的顺序将按照第一行第一个、第一行第二个、每个网格中都必须填入组件，假如希望是空白的网格，可以给它添加一个空的标签： add (new Label()。三、事件处理在一个GUI程序中，为了与用户进行交互，需要接受键盘和鼠标的操作。当用户执行一个用户界面级的操作时，会引发一个事件，通常一个键盘和鼠标操作将引发一个系统事先定义好的事件，用户程序只需要编写代码定义每个事件发生时程序应做何种响应即可8。事件 ：说明“发生了什么事情”的对象。 系统根据用户的操作构造出相应事件类的对象。事件可以分为焦点事件、键盘事件、鼠标事件。事件源：有自己的方法，通过它像其注册事件监听器，事件监听器是一个实例。事件处理程序：是一个方法，它接收一个事件对象然后分析这个对象最后完成对该事件的处理。每个事件有一个相应的监听者接口，它规定了能够接收（并处理）该类事件的方法的规范。图2.1 界面构成第三节 相关算法的介绍一、冒泡排序1、什么是交换所谓交换，就是根据序列中两个元素关键字的比较结果对换这两个记录在序列中的位置，基于交换排序的算法有很多，本次设计以冒泡排序来为例子，更容易让人们理解交换的概念。2、冒泡排序的概念冒泡排序算法的基本思想是：假设待排序长为n，从后向前或者从前向后两两比较相邻元素的值。这里我假如是从从小到大排序，若为逆序（即Ai-1Ai）,则交换他们直到序列比较完，我们称他们为一趟冒泡，结果将最小的元素交换到待排元素的序列的第一个位置，下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，.，这样最多做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)。稳定性：由于当ij且Ai.key=Aj.key时不会交换两个元素，从而冒泡排序算法是一个稳定的排序算法。由此可以总结出冒泡排序的优点是具有稳定性，缺点是慢，每次只能移动相邻的两个数据。冒泡排序虽然可能不是最好的做法排序10，但确是经常用的一种排序算法。二、插入排序1、什么是插入排序它的基本思想就是每次将一个待排序的记录，按其关键字大小插入到前面已经排好的子序列中，直到完成了全部记录插入。由插入排序可以引申出三种重要的排序算法：直接插入排序、折半插入排序、希尔排序。在这里主要介绍直接插入排序。2、直接插入插入排序的概念直接插入排序是一种简单的排序方法，它的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。例如，已知待排序的一组记录的初始序列如下所示：表2.1排序初始序列有序序列L1i-1L(i)无序序列Li+1n为了实现将元素L(i)插入到已有序的子序列L1.i-1中我们需要执行以下操作（为避免混淆，下面用”L”表示一个表，而L（）表示一个元素排序L(i)在L1.i-1中的出入位置k。将Lk.i-1中所有元素后移一个位置。将L(i)复制到L(k)。为了实现对L1.n的排序，可以将L(2)到L(n)依前面次插入到前面已经排好的子序列当中，初始假设L1是一个已经排好的子序列，上述操作执行n-1次，就能得到一个有序的表插入排序在实现上通常采用的就是就地排序（空间复杂度为O(1)）,因而在从后向前的比较过程中，需要反复把已经排好的元素逐步向后移位，为新元素提供插入空间。3、直接插入排序的性能分析直接插入排序的性能分析如下：空间效率：仅使用了常数个辅助单元，因而空间复杂度为0(1)。时间效率：在排序过程中，向有序字表中逐个的插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数是取决于排序表初始状态的。在最好的情况下，表中元素已经有序，此时每插入一个元素，都只需比较移动一次而不用移动元素，因而时间复杂度为O（n)。在最坏的情况下：表中序列刚好与排序结果中元素顺序相反（逆序）的的移动次数为0，总的比较次数达到最大，为，总的移动次数也达到最大，为。平均情况下，考虑待排序元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数约为n*n/4。由此直接插入排序算法的时间复杂度为O(n*n),插入排序往往能表现出很好的性能。稳定性：由于每次插入元素时总是从后向前先比较再移动的，所以不会出现相同元素的相对位置发生变化，即直接插入排序算法是一个稳定的排序算法。适用性：直接插入排序适用顺序储存和链式储存的线性表。当为链式储存时可以从前往后排序指定元素的位置，通常的排序算法中，大部分都仅适用于顺序的线性表。三、选择排序1、什么是选择排序选择排序的的基本思想是：每一趟（例如第i趟）在后面n-i+1(i=1,2,.,n-1)个待排序元素中选择关键字最小的元素，作为有序元素序列的第i个元素，直到第n-1趟做完，待排序元素只剩下一个，就不用选了。2、简单选择排序的概念假设排序表为L1.n,第i趟排序即从Li.n中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。3、简单选择排序的性能分析简单选择排序的性能分析如下：空间效率：仅使用了常数个辅助单元，因而空间复杂度为0(1)。时间效率：元素的移动操作很少不会超过3（n-1）次，最好情况下移动次数为0，此时对应的表已经有序；但元素间比较的次数与元素的初始序列无关，始终是n(n-1)/2；所以时间复杂度始终是O(n*n)。稳定性;在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变，因此，简单选择排序是一个不稳定的排序算法。四、 二叉查找树1、二叉查找树的定义二叉查找树（简称BST）也称二叉排序树。二叉查找树或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树非空，则左子树上所有结点的值均小于它的根结点关键字的值； （2）若右子树非空，则右子树上所有结点的值均大于它的根结点的关键值值； （3）左、右子树也分别为二叉查找树；由此定义可以知，二叉查找树是一个递归的数据结构，可以很方便地使用递归算法对二叉查找树进行各种运算，根据二叉查找树的定义，左子树=根节点值=右子树节点值，所以，对二叉查找树进行中序遍历，可以得到一个非递减的有序序列。例如，下图的二叉树查找的中序遍历的顺序为234579，如图2.2所示：图2.2 一棵二叉树2、二叉查找树的建立建立一颗二叉查找树，就是要依顺序输入数据元素，然后将他们插入到二叉查找树合适的位置的一个过程，其具体的过程，就是在每次输入一个元素的时候，就要建立一个新的结点，如果二叉查找树不是空的，就将新结点的值与根结点， 如果小于根结点的值，就要其插入到左子树种，如果比根结点大，就需要将其插入到右子树中。如果二叉树为空，就将新结点作为根结点。3、二叉查找树的插入二叉树是一种动态的集合，它的特点是树的结点往往不是仅以此就能生成的，而是在通过排序的过程中，当且仅当该关键值不等于树中的时候才插入。因为二叉查找树是的定义是递归的，那么插入结点的过程是，如果原来的二叉树是空的，就可以把结点直接插入进去，如果不是空的，若关键字的值比根结点小，就将其出入到左子树中，如果比根结点的值大，就要将其插入到右子树中。4、二叉查找树的删除当删除一个二叉查找树的结点时，不可以把以该结点的作为根的子树上的结点都删除了，而是必须先把要删除的结点从存储的二叉树的链表上摘下，把因为删除结点而断开的二叉链表，重新连接起来，而且要确保二叉查找树的性质不会改变13。删除操作的过程一般按三种情况来处理的：假如删除的结点是A是叶结点，就可以直接删了，而不会改变该二叉树的性质。如果结点A或者是一颗左子树，或者是右子树，就让A的子树成为a父节点的子树，代替A 的位置。如果结点A既有左子树，又有右子树，就令A的直接后继（或者是直接前驱）代替A，然后从二叉排序中删去这个直接后继（或者直接前驱），这样就可以换成前面两种情况了。5、二叉查找树的性能分析二叉查找树的高度为H，它的插入和删除操作的运行时间都是O(H),但是在最坏的情况下，即构造二叉查找树的输入序列是有序的，就会形成一个倾斜的图2.3一般情况的二叉树图2.4最坏情况下的二叉树单支树，此时二叉查找树的性能就会明显的变坏，树的高度也增加元素N。在等概率的条件下，图2.3排序成功的平均排序长度为ASL=(1+2*2+3*4+4*3)/10=3而图2.4排序成功的平均排序长度为ASL=(1+2+3+4+5+6+7+8+9+10)/10=5.5由此可知，二叉查找树排序算法的平均排序长度，主要取决于树的高度，即与二叉树的形态无关。从排序过程看，二叉查找树也二分排序相识，就平均时间而言，二叉查找树的排序和二分排序差不多，但二分排序的判定树唯一，而二叉查找树不唯一，相同的关键字，其插入顺序不同可能生成不同的二叉查找树。就维护表而言，二叉查找树无须移动结点，只需修改指针即可，插入和删除操作，其平均执行时间为0(log2n)。二分排序的对象是有序顺序表，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态排序表时，易用顺序表作为存储结构，而采用二分排序实现其排序操作;若有序表是动态排序表，则应选择二叉查找树作为存储结构。第四节 本章小结在本章中比较详细的介绍了Java的相关知识及其发展史，了解到了Java的主要特性。在后面章节中，我们会一实际的算法可视化的例子来说明是如何实现相关功能的。还介绍了关于图形界面知识的概念，通过此本章的学习，能让大家怎样完成图形界面实现，设计出更美观的界面，对以后进一步学习这部分的知识很有帮助。最后还介绍了四种排序算法的概念，操作的实现以及算法的性能分析，通过此本章的学习，能让大家清楚排序算法的基本原理和具体实现过程，能在不同的情况下选择适合的排序算法，能让大家更好的掌握知识并运用所学的知识解决问题。第三章 需求分析需求分析是软件定义时期的最后一个阶段，它的工作是软件工程生命周期中的第一步，也是起决定性的一步，在需求分析阶段我们需要全面了解整个系统的功能和性能方面的要求，为软件设计打下坚实的基础14。它的基本任务是确定系统必须完成哪些工作，也就是对目标系统提出完整、准确、清晰、具体的要求。第一节 系统功能需求一、系统设计目标开发软件首先做的是开发过程中最主要的就是系统的需求分析15，了解并掌握数据结构与算法的设计方法，具备独立分析和能力；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；设计并实现直观、容易被理解的排序算法和二叉查找树的动态演示系统，是系统设计的目标。二、系统功能需求算法可视化的演示有很多种，而此次设计要想实现的就是借助以前学过的数据结构所学的知识，实现对排序算法的演示。1、排序算法所实现的功能 输入少于20个小于650的整数，并对其排序演示。 实现对冒泡排序进行演示，并显示排序前后的数组，排序所交换的次数、比较的次数、探测的次数及其所用的总的时间。 实现对插入排序进行演示，并显示排序前后的数组，排序所交换的次数、比较的次数、探测的次数及其所用的总的时间。 实现对选择排序排序进行演示，并显示排序前后的数组，排序所交换的次数、比较的次数、探测的次数及其所用的总的时间。 可以生成随机数，然后进行插入、选择、冒泡三种排序演示。 对一个已有的文本文件进行排序演示。2、二叉查找树实现的功能 二叉查找树的插入演示。 二叉查找树的删除演示。二叉查找树的查找路径演示。第二节 系统运行环境本系统对运行环境的要求如下：硬件环境：PC兼容机；2G 内存。软件环境： 操作系统：Windows XP、Windows 7、Windows 8； 相关应用软件：JDK、Eclipse。第三节 本章小结本章主要是对算发可视化演示系统的设计目标和系统所所要实现的功能以及运行环境进行了分析。需求分析在软件的开发中是很关键的一步，一个软件开发成功与否需求分析起着十分重要的作用，所以我们在开发一个软件前，一定要做好需求分析。第四章 系统设计第一节 系统总体描述本系统的主要是由四个算法来实现的，由此我们得到系统的结构图如图4.1所示：图4.1 系统结构图系统总的来说包括两个部分：一个是基于排序算法的演示系统，一个是基于二叉查找树的排序系统。在排序算法的系统中主要是冒泡排序模块、插入排序模块、选择排序模块，实现排序算法的演示，而二叉查找树模块主要是实现二叉查找树的插入、删除、排序功能。在开启算法可视化演示系统之后，用户可以选择排序系统或者二叉查找树系统进行演示，如果选择的是排序系统，就会出现三个子系统，然后可以对三个系统进行演示。如果选择的是二叉查找树系统就可以对该系统进行插入、删除、排序操作。第二节 模块设计一、算法模块设计1、排序算法模块设计Sort类定义了排序算法的参数，数组的长度，排序前的数组，以及排序后的数组，获取排序参数，打印排序前后的数组等一系列操作，是冒泡、选择、插入的父类，如图4.2所示：图4.2 排序类2、冒泡排序模块设计BubbleSort类是从排序类继承而来的，完成对冒泡排序的排序、获取排序的名字具体操作如图4.3所示：图4.3. 冒泡排序类3、选择排序模块设计SelectSort类是从排序类继承而来的，完成对选择排序的排序、获取排序的名字具体操作如图4.4所示：图4.4. 选择排序类3、插入排序模块设计InsertSort类是从排序类继承而来的，完成对选插入序的排序、获取排序的名字具体操作如图4.5所示：图4.5插入排序类二、界面模块设计1、界面所含的主要继承的类此次设计我们使用面向对象的设计模式，算的实现和可视化的部分写在各自的类里面，可视化是采用图形界面写的。虽然算法不同，但它们之间还是有很多的共同之处。比如：在排序的时候需要的排序对象的数组是整形的，它们必须给外界提供一个公共的排序方法接口；和它们在排序过程中所需要的适配器来进控制，如图4.6所示：图4.6 界面类的继承关系从上图我们可以清楚的看到类TreeControl和类TreeView都继承了类JPanel，类而类JPanel又继承了JComponent。他们既有共性又有特性，如果只考虑他们的共性，而不考虑他们的特性，就不能反映出他们之间的层次关系，不能完整、正确地对客观世界，进行抽象的描述，类TreeControl和类TreeView都有类JPanel的所有的特征，即有他们的共性。同时这三个类都有JComponent的性质，而反过来则不一定成立。本次设计我们所用的算法最多的就是排序算法，类SelectSort 和 BubbleSort 以及类InsertSort都继承了Sort。它们都有公共的算法，有交换，和开始时间，结束时间，都需要一个数组来存放这些值，Sort就含有它们的公共属性，而选择排序，插入排序金额冒泡排序都各自有自己的实现方法，如图4.7所示：图4.7排序算法类的继承关系2、主界面模块的设计VisualFrame类是该系统的主界面，该类主要定义了界面的按钮，以及生成界面的方法和响应方法，具体的类图如图4.8所示：图4.8 VisualFrame类的类图3、排序界面模块的设计MainSortApp类是实现排序算法的界面，在此界面上可以选择三种排序中的一种进行排序，如图4.9所示：图4.9排序演示界面的类图4、排序时弹出界面模块的设计OutPutFrame类是实现具体排序算法的界面，当选择三种排序的一种算法时就会出现弹出的界面，具体的结构如图4.10所示：图4.10弹出的排序演示界面的类图5、二叉查找树界面模块的设计TreeControl的类是实现二叉查找树的界面，在此类中定义了插入、删除、查找等按钮，将这些按钮都加入监听，类图的结构如4.11所示：图4.11二叉查找树演示界面的类图第三节 系统流程图当打开演示系统后，显示的界面上有两个按钮，选择演示类型，如果是选择排序，就可以输入数据，选择排序插入排序，或者冒泡排序，或者选择排序，之后就展示演示过程，演过示完后可以选择继续排序，也可以退出循环，结束此过程。如果在第一个分支时不是选择的是排序演示，则输入节点值，选择插入、删除、排序三种方式中的一种，然后展示相应的效果，完了之后我们也可以继续此操作，也可以结束此操作。在对系统进行了需求分析和概要设计之后的，对系统进行了详细的设计，分析了各个模块的流程和步骤，并进行了流程的系统分析，绘出的本系统总体工作流程图，如图4.12所示。图4.12 算法可视化演示软件开发总体流程图第四节 本章小结本章主要是对算发可视化演示系统进行总体设计，设计了程序对应的模块，并画了相应的流程图，为接下来的系统实现打下了坚实的基础。第五章 系统实现第一节 可视化主界面的实现本段代码实现的算法可视化的主界面，当开始运行时，系统就会判断选择的哪个按钮，然后做相应的响应，如果是选择的排序按钮，就会把排序按钮设置为不可见的，如果是选择的二叉查找树的按钮那么，这个按钮也会被设置为不可见的按钮，也就是界面会显示“排序可视化”和“二叉查找树”两个互斥按钮。首先定义排序可视化和二叉查找树演示两个按钮：public class VisualFrame extends JFrame private JButton sort=new JButton(排序可视化);private JButton tree=new JButton(二叉查找树演示);private ActionListener arg0=new ActionListener() public void actionPerformed(ActionEvent arg0) /实现按钮操作的响应方法/ TODO Auto-generated method stubif(arg0.getSource()=sort)/用来判断发起事件的控件是不是sortEventQueue.invokeLater(new Runnable() / 导致 runnable 的 run 方法在 EventQueue 的指派线程上被调用public void run() try MainSortApp window = new MainSortApp();window.frame.setVisible(true); catch (Exception e) e.printStackTrace(););sort.setEnabled(false);/按钮不可用 tree.setEnabled(true);/按钮可用 if(arg0.getSource()=tree)/用来判断发起事件的控件是不是tree DisplayBinar