【正文】 算法可視化演示軟件開(kāi)發(fā)畢業(yè)設(shè)計(jì)目 錄前 言 1第一章 緒論 2第一節(jié) 課題背景 2第二節(jié) 課題的目的與意義 2第三節(jié) 論文結(jié)構(gòu) 3第二章 相關(guān)知識(shí)概述 4第一節(jié) Java知識(shí)相關(guān)概述 4一、Java的發(fā)展史 4二、Java的主要特性 4三、JDK 平臺(tái)相關(guān)信息 5第二節(jié) Java圖形界面技術(shù)概述 5一、 Java Swing相關(guān)概述 5二、容器和布局 7三、事件處理 8第三節(jié) 相關(guān)算法的介紹 9一、冒泡排序 9二、插入排序 10三、選擇排序 12四、 二叉查找樹(shù) 12第四節(jié) 本章小結(jié) 15第三章 需求分析 17第一節(jié) 系統(tǒng)功能需求 17一、系統(tǒng)設(shè)計(jì)目標(biāo) 17二、系統(tǒng)功能需求 17第二節(jié) 系統(tǒng)運(yùn)行環(huán)境 18第三節(jié) 本章小結(jié) 18第四章 系統(tǒng)設(shè)計(jì) 19第一節(jié) 系統(tǒng)總體描述 19第二節(jié) 模塊設(shè)計(jì) 20一、算法模塊設(shè)計(jì) 20二、界面模塊設(shè)計(jì) 22第三節(jié) 系統(tǒng)流程圖 25第四節(jié) 本章小結(jié) 26第五章 系統(tǒng)實(shí)現(xiàn) 27第一節(jié) 可視化主界面的實(shí)現(xiàn) 27第二節(jié) 排序算法界面所實(shí)現(xiàn)的功能 28第三節(jié) 二叉查找樹(shù)可視化功能的實(shí)現(xiàn) 31第四節(jié) 本章小結(jié) 33第六章 系統(tǒng)測(cè)試 34第一節(jié) 問(wèn)題解決及測(cè)試結(jié)果 34一、 遇到的問(wèn)題 34二、解決的方法 34三、測(cè)試結(jié)果 34第二節(jié) 本章小結(jié) 41結(jié) 論 42致 謝 43參考文獻(xiàn) 44附 錄 45一、英文原文 45二、英文翻譯 52重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)(論文)前 言可視化（ Visualizations）計(jì)算機(jī)圖形學(xué)和圖像處理技術(shù)，將數(shù)據(jù)轉(zhuǎn)換成圖形或圖像在屏幕上顯示出來(lái)，并進(jìn)行交互處理的理論、方法和技術(shù)。此次設(shè)計(jì)算法可視化（ Algorithm Visualizations）就是利用可視化技術(shù)將算法可視化[1]。排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，其功能是一個(gè)數(shù)據(jù)元素（或者記錄）的任意序列，從新排列成一個(gè)按關(guān)鍵字有序的序列。在我們所學(xué)的數(shù)據(jù)結(jié)構(gòu)中了解到了排序算法的原理，以及實(shí)現(xiàn)過(guò)程，但是不清楚它的具體過(guò)程是怎么樣的。算法的概念極為抽象，算法有時(shí)也枯燥難懂，所以很多時(shí)候就提不起學(xué)生的興趣，此次的畢業(yè)設(shè)計(jì)所研究的就是在算法基礎(chǔ)上結(jié)合圖形界面動(dòng)態(tài)的演示排序算法的具體實(shí)現(xiàn)過(guò)程，從一定程度上也可以提起學(xué)生的興趣，讓讀者不僅從理論上理解它，更是從實(shí)踐過(guò)程去接受知識(shí)，給學(xué)生更深的印象。所要達(dá)到的目的是以生動(dòng)、活潑、全新的教學(xué)系統(tǒng)，提供全新的環(huán)境提高學(xué)生的聽(tīng)課興趣，增加學(xué)生的記憶。并且本次畢業(yè)設(shè)計(jì)也選擇了不同的排序算法，這樣在演示的過(guò)程中，我們可以根據(jù)實(shí)現(xiàn)的復(fù)雜程度和執(zhí)行速度等方面為該系統(tǒng)選擇合適的排序算法，使之高效率運(yùn)行，進(jìn)而提高對(duì)排序算法的掌握程度[2]。二叉樹(shù)的算法、結(jié)構(gòu)化查詢語(yǔ)言等的研究對(duì)數(shù)據(jù)查詢有著很重要的實(shí)際意義。用二叉查找樹(shù)的關(guān)系表的方法，可提高商品信息的查詢效率。此次畢業(yè)設(shè)計(jì)還選擇了二叉樹(shù)算法的動(dòng)態(tài)演示，對(duì)研究二叉查找樹(shù)是很有幫助，讓大家更了解二叉查找樹(shù)的實(shí)際意義，對(duì)研究更復(fù)雜的數(shù)據(jù)庫(kù)關(guān)系打下了基礎(chǔ)。第一章 緒論第一節(jié) 課題背景隨著社會(huì)和計(jì)算機(jī)技術(shù)的發(fā)展，如今，在可視化技術(shù)這個(gè)大家庭中不僅僅只有科學(xué)計(jì)算機(jī)可視化，它還包括了信息可視化、數(shù)據(jù)可視化、知識(shí)可視化等一系列的分支。數(shù)據(jù)可視化有可能幫助人類在大量數(shù)據(jù)的分析和理解，并檢測(cè)模式[3]。近年來(lái)，各種可視化技術(shù)已經(jīng)擴(kuò)展到軍事、醫(yī)學(xué)、醫(yī)學(xué)研究、經(jīng)濟(jì)、解釋工程等各個(gè)領(lǐng)域。其中有很多問(wèn)題需要在以后的研究中加以解，從整體上來(lái)說(shuō)，我國(guó)的可視化技術(shù)與世界先進(jìn)水平還有很大的差距。而算法可視化是研究其它更深層次領(lǐng)域的基礎(chǔ)，因此在研究其它領(lǐng)域的可視化前，我們必須先搞清楚算法可視化這個(gè)概念。由于數(shù)據(jù)結(jié)構(gòu)中算法是算法可視化中最容易讓讀者理解和明白的算法，因此，此次設(shè)計(jì)主要以排序算法和二叉查找樹(shù)的相關(guān)操作來(lái)研究。排序在計(jì)算機(jī)輔助設(shè)計(jì)、計(jì)算機(jī)圖形學(xué)、機(jī)器人、模式識(shí)別、基因排序?qū)W工程以及統(tǒng)計(jì)學(xué)等領(lǐng)域都具有廣泛的應(yīng)用，因此在排序的研究不僅有理論上的重要意義，而且有更大的實(shí)際應(yīng)用價(jià)值。又加上如今信息產(chǎn)業(yè)在快速的發(fā)展信息的流通量越來(lái)越大，這些信息數(shù)據(jù)不僅龐大而且雜亂無(wú)章，很難管理和查詢，所以更加需要一種非?？旖荻矣行У木幣攀侄蝸?lái)整理這些數(shù)據(jù)信息，提高我們的工作效率。第二節(jié) 課題的目的與意義設(shè)計(jì)并實(shí)現(xiàn)直觀、容易被理解的算法的動(dòng)態(tài)演示系統(tǒng)，是課題研究的目的。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，人們提出了各種算法，算法可視化在計(jì)算機(jī)領(lǐng)域里有十分重要的意義，并且應(yīng)用廣泛。在當(dāng)今信息發(fā)達(dá)的時(shí)代，面對(duì)著海量的無(wú)序數(shù)據(jù)信息，如果沒(méi)有一個(gè)規(guī)則來(lái)編排和查詢，就會(huì)給我們的工作和信息帶來(lái)很大的不方便，所以利用計(jì)算機(jī)的高速運(yùn)行和計(jì)算能力，編寫(xiě)出一種合適的排序軟件，是十分必要的。并且在設(shè)計(jì)的過(guò)程中也能讓學(xué)生更加的了解排序算法和實(shí)現(xiàn)過(guò)程，使他們?cè)谝院蟮膶W(xué)習(xí)和工作中能找到更加高效的排序系統(tǒng)，提高學(xué)習(xí)效果和工作效率。第三節(jié) 論文結(jié)構(gòu)本次的論文共有六個(gè)章節(jié)，詳細(xì)的闡述了算法可視化的具體實(shí)現(xiàn)：第一章，主要介紹了研究的背景、內(nèi)容、目的和意義。第二章，簡(jiǎn)述相關(guān)的Java知識(shí)，進(jìn)一步了解Java的發(fā)展史、特性，還介紹Java圖形界面的相關(guān)知識(shí)和相關(guān)算的一些知識(shí)。第三章，通過(guò)仔細(xì)研究，進(jìn)行系統(tǒng)地需求分析。第四章，明確項(xiàng)目模塊，進(jìn)行系統(tǒng)概要設(shè)計(jì)。第五章，可視化算法的具體實(shí)現(xiàn)、及其功能。第六章，系統(tǒng)測(cè)試，以及在做畢設(shè)的過(guò)程中遇到的問(wèn)題，最后對(duì)本次畢設(shè)進(jìn)行總結(jié)。第二章 相關(guān)知識(shí)概述第一節(jié) Java知識(shí)相關(guān)概述一、Java的發(fā)展史Java是由Sun公司1995年5月開(kāi)發(fā)的新一代面向?qū)ο缶幊陶Z(yǔ)言（簡(jiǎn)稱Java語(yǔ)言）和Java平臺(tái)的總稱。Java的正式推出是1995年，它是James Gosling和同事們一起研發(fā)的，HotJava瀏覽器是用Java實(shí)現(xiàn)的，它（支持Java applet）顯示了Java的魅力：動(dòng)態(tài)的Web、跨平臺(tái)、Internet計(jì)算。它可以應(yīng)用在各種不同的平臺(tái)上，正逐步成為internet應(yīng)用的主要開(kāi)發(fā)語(yǔ)言。此后，Java不僅被廣泛接受還推動(dòng)了Web的快速發(fā)展，我們所用的一般的瀏覽器均支持Java applet。另一方面，Java技術(shù)也一直在更新。Java是由四個(gè)方面組成的：Java編程語(yǔ)言、Java類文件格式、Java虛擬機(jī)和Java應(yīng)用程序接口(Java API)。Java 技術(shù)具有突出的的平臺(tái)移植性、高效性、通用性和安全性，它應(yīng)廣泛的用于數(shù)據(jù)中心、個(gè)人PC、移動(dòng)電話、游戲控制臺(tái)、互聯(lián)網(wǎng)以及科學(xué)超級(jí)計(jì)算機(jī)，并且在全球擁有的開(kāi)發(fā)者專業(yè)社群是最大的。在全球云計(jì)算和移動(dòng)互聯(lián)網(wǎng)的產(chǎn)業(yè)環(huán)境下，Java更具備了顯著優(yōu)勢(shì)和廣闊的前景[4]。二、Java的主要特性Java的主要特性有平臺(tái)無(wú)關(guān)性、安全性、面向?qū)ο筇匦浴⒑?jiǎn)單性、動(dòng)態(tài)特性、多線程性、健壯性等特性[5]。Java語(yǔ)言是體系結(jié)構(gòu)中立的，是可移植的。是解釋型的，而且是高性能的，是動(dòng)態(tài)的[6]。Java語(yǔ)言的設(shè)計(jì)的其中一個(gè)目標(biāo)就是要適應(yīng)環(huán)境的動(dòng)態(tài)變化。能夠把程序需要的類動(dòng)態(tài)的載入到運(yùn)行環(huán)境，同時(shí)所需要的類也可以通過(guò)網(wǎng)絡(luò)載入。這樣對(duì)軟件的升級(jí)很有用。Java中的類有一個(gè)運(yùn)行時(shí)刻的表示，能進(jìn)行運(yùn)行時(shí)刻的類型檢查。Java語(yǔ)言的優(yōu)良特性使得Java應(yīng)用有很高的的可靠性和健壯性，同時(shí)應(yīng)用系統(tǒng)維護(hù)的費(fèi)用也相對(duì)減少了。Java對(duì)對(duì)象技術(shù)的全面支持和Java平臺(tái)內(nèi)嵌的API能減少應(yīng)用系統(tǒng)的開(kāi)發(fā)所需要的時(shí)間還能有效降低成本。Java的編譯一次，其隨處可運(yùn)行的特性使得它能夠提供一個(gè)隨處可用的開(kāi)放結(jié)構(gòu)和在多平臺(tái)之間傳遞信息的低成本方式。尤其是Java企業(yè)應(yīng)用編程接口（Java Enterprise APIs）為企業(yè)計(jì)算及電子商務(wù)應(yīng)用系統(tǒng)提供了豐富的類庫(kù)很相關(guān)技術(shù)。Java語(yǔ)言是面向?qū)ο蟮?，面向?qū)ο蠹夹g(shù)的基本特征主要有抽象性、封裝性、繼承性和多態(tài)性。而在本次設(shè)計(jì)中主要涉及到的是Java Swing包。三、JDK 平臺(tái)相關(guān)信息本系統(tǒng)利用Java JDK作為開(kāi)發(fā)平臺(tái)，利用它的可視化界面和圖形用戶界面在硬件環(huán)境：PC兼容機(jī)，1G 內(nèi)存以及軟件環(huán)境Microsoft Windows7操作系統(tǒng)（可以移植到大部分機(jī)器上）下一個(gè)演示不同的算法，利用Java編寫(xiě)的圖形界面演示的動(dòng)態(tài)交換過(guò)程。JDK是Java開(kāi)發(fā)工具包（Java development kit)）的縮寫(xiě)，是整個(gè)Java的核心，是一種用于構(gòu)建在Java平臺(tái)上發(fā)布的應(yīng)用程序包括了Java運(yùn)行環(huán)境（Java Runtime Envirement），一堆Java工具和Java基礎(chǔ)的類庫(kù)()。不論什么Java應(yīng)用服務(wù)器實(shí)質(zhì)都是內(nèi)置了某個(gè)版本的JDK。因此掌握J(rèn)DK是學(xué)好Java的第一步。最主流的JDK是Sun公司發(fā)布的JDK，除了Sun之外，還有很多公司和組織都開(kāi)發(fā)了自己的JDK，例如IBM公司開(kāi)發(fā)的JDK，BEA公司的Jrocket，還有GNU組織開(kāi)發(fā)的JDK等等。其中IBM的JDK包含的JVM（Java Virtual Machine）運(yùn)行效率要比Sun JDK包含的JVM高出許多。而專門(mén)運(yùn)行在x86平臺(tái)的Jrocket在服務(wù)端運(yùn)行效率也要比Sun JDK好很多。但無(wú)論怎么說(shuō)，我們都要需要先把Sun JDK掌握好。在委托事件處理模型中，用戶操作引發(fā)的事件對(duì)象仍然傳遞給相應(yīng)的組件，但是為了接受事件并進(jìn)行事件處理，組件必須注冊(cè)一個(gè)事件處理程序，這種事件處理程序稱為事件的監(jiān)聽(tīng)程序（Listener）。事件的監(jiān)聽(tīng)程序可以定義在組件所在的類，也可以定義在其他的類里，而對(duì)事件的處理，則由組件委托給事件監(jiān)聽(tīng)所在的類來(lái)完成。第二節(jié) Java圖形界面技術(shù)概述一、 Java Swing相關(guān)概述在Java中設(shè)計(jì)圖形界面程序時(shí)，通常選用AWT組件和Swing組件。Java的出現(xiàn)帶來(lái)了抽象窗口工具（AWT），其設(shè)計(jì)目標(biāo)是希望構(gòu)建一個(gè)通用的GUI(圖形用戶界面)使得利用它編程的程序能夠運(yùn)行在所有平臺(tái)上，以實(shí)現(xiàn)SUN你公司的口號(hào)“一次編寫(xiě)，隨處運(yùn)行”。SUN公司推出了新的用戶界面庫(kù)：Swing，相對(duì)AWT來(lái)說(shuō)，Swing功能更強(qiáng)大、使用更方便，它的出現(xiàn)是使得Java的圖形用戶上了一個(gè)臺(tái)階[7]。Swing的關(guān)鍵在于一旦有了頂級(jí)容器，則其中所有構(gòu)件都可以用Java編寫(xiě)，例如，將按鈕（JButton)放入框架（JFrame）中時(shí)，本機(jī)操作系統(tǒng)不需要了解該按鈕的任何信息，該按鈕完全用Java編寫(xiě)且無(wú)同級(jí)組件，因而組件稱為“輕”組件。Swing具有以下幾點(diǎn)優(yōu)勢(shì)：①豐富的組件類型:Swing提供了非常廣泛的標(biāo)準(zhǔn)組件。這些組件和SWT一樣豐富?；谒己玫目蓴U(kuò)展性，除了標(biāo)準(zhǔn)組件，Swing還提供了大量的第三方組件。許多商業(yè)或開(kāi)源的Swing組件庫(kù)在開(kāi)發(fā)多年后都已經(jīng)可以方便地獲取了。②豐富的組件特性:Swing不僅包含了所有平臺(tái)上的特性，它還支持根據(jù)程序所運(yùn)行的平臺(tái)來(lái)添加額外特性。Swing組件特性遵循特定原則，易于擴(kuò)展，因此能夠提供較SWT和AWT更多的功能。③好的組件API模型支持:Swing遵循MVC模式，這是一種非常成功的設(shè)計(jì)模式。它的API成熟并設(shè)計(jì)良好。經(jīng)過(guò)多年的演化，Swing組件APIs變得越來(lái)越強(qiáng)大，靈活和可擴(kuò)展。它的API設(shè)計(jì)被認(rèn)為是最成功的GUI API之一。較之SWT和AWT更面向?qū)ο?，也更靈活而可擴(kuò)展。④標(biāo)準(zhǔn)的GUI庫(kù)：Swing和AWT一樣是JRE中的標(biāo)準(zhǔn)庫(kù)。因此，你不用單獨(dú)地將它們隨你的應(yīng)用程序一起分發(fā)。它們是平臺(tái)無(wú)關(guān)的，不用擔(dān)心平臺(tái)兼容性。⑤成熟穩(wěn)定：由于它是純Java實(shí)現(xiàn)的，不會(huì)有SWT的兼容性問(wèn)題。Swing在每個(gè)平臺(tái)上都有相同的性能，不會(huì)有明顯的性能差異。⑥可擴(kuò)展和靈活性。Swing完全由Java代碼實(shí)現(xiàn)。Swing基于MVC的結(jié)構(gòu)使得它可以發(fā)揮Java作為一門(mén)面向?qū)ο笳Z(yǔ)言的優(yōu)勢(shì)。它提供了許總體上良好的性能。Swing也有著許多不足之處：比如Swing比AWT和SWT更多的內(nèi)存消耗。Swing自己實(shí)現(xiàn)了所有組件。因此，它在運(yùn)行時(shí)裝載了大量的類。而在運(yùn)行時(shí)Java在堆上創(chuàng)建小的對(duì)象導(dǎo)致了額外的堆空間消耗。而許多小的對(duì)象難以有效地被垃圾回收機(jī)制回收。因此，Swing應(yīng)用程序通常會(huì)因無(wú)法及時(shí)回收冗余的對(duì)象而導(dǎo)致性能下降。二、容器和布局我們都知道，Java的GUI界面定義是由AWT類包和Swing類包來(lái)完成的[8]。它在布局管理上采用了容器和布局管理分離的方案。也就是說(shuō)，容器只管將其他組件放入其中，而不管這些組件是如何放置的。對(duì)于布局的管理交給專門(mén)的布局管理器類(LayoutManager)來(lái)完成。Java中的容器是用來(lái)放置其它組件的一種特殊部件（如標(biāo)簽、按鈕、文本框等），用Containers 來(lái)描述容器，容器組件Window 不需要其他組件支撐，獨(dú)立顯示。容器主要有面板和框架兩類，在AWT中，F(xiàn)rame是對(duì)應(yīng)于框架的類， 大部分AWT組件在Swing中都有等價(jià)的組件，他們?cè)谛问缴舷嗖钜粋€(gè)“J”。Dialog 表示沒(méi)有菜單條，但是不能改它的變大小。Pane一定要放在Web瀏覽器窗口（或者Window組件）中才可以顯示。它是一矩形域，在里面可以擺放其它的組件，也可以有自己的布局管理器。基本方法是remove(Componentp) 刪除指定組件、add(Component p) 將指定組件放到容器中、add(Component p，int index), setLayout(LayoutManagermgr)設(shè)置容器布局。在Java中還提供了支持用戶界面元素自動(dòng)定位的布局工具。容器的組件布局 ,負(fù)責(zé)確定組件在容器中的位置和大小。布局管理有流布局管理、邊界布局管理和網(wǎng)格布局三種布局管理器。調(diào)用容器的setLayout(布局管理器對(duì)象) 方法，為容器指定某種布局管理器的一個(gè)對(duì)象。當(dāng)容器需要確定組件大小和定位組件的時(shí)候，就會(huì)發(fā)消息給布局管理器對(duì)象，讓它完成該項(xiàng)工作。直接管理組件調(diào)用容器setLayout(null) 方法，關(guān)閉布局管理