【正文】 器。調(diào)用每一個組件的setLocation()方法決定組件位置。調(diào)用每一個組件的setSize()。布局管理器種類FlowLayout: 在一行上水平排列組件，直到該行沒有足夠的空間為止，然后另起一行繼續(xù)排列當(dāng)用戶縮放容器時，布局管理器將自動進(jìn)行控制，重新排列。BorderLayout（邊界布局管理器）的布局分為東、南、西、北、中五個位置。可以把組件放在這五個位置的任意一個，假如沒有指定位置，就把中作為默認(rèn)的位置。GridLayout（網(wǎng)格布局管理器）在你創(chuàng)建用戶界面時，經(jīng)常像將對象按網(wǎng)格一樣均勻排列，例如一行或者一列單選按鈕，它所確保的所有構(gòu)件占用的空間完全相同，創(chuàng)網(wǎng)格由應(yīng)占的行數(shù)和列數(shù)決定。網(wǎng)格布局管理器具有更復(fù)雜、功能更強(qiáng)的網(wǎng)格布局。網(wǎng)格布局的每一個組件作為一個卡片，該容器只顯示多個卡片中的某一個。setLayout(new GridLayout(行數(shù), 列數(shù)))。setLayout(new GridLayout(行數(shù), 列數(shù),行間隔,列間隔))。調(diào)用容器的方法add()將組件加入容器，組件填入容器的順序?qū)凑盏谝恍械谝粋€、第一行第二個、……每個網(wǎng)格中都必須填入組件，假如希望是空白的網(wǎng)格，可以給它添加一個空的標(biāo)簽： add (new Label())。三、事件處理在一個GUI程序中，為了與用戶進(jìn)行交互，需要接受鍵盤和鼠標(biāo)的操作。當(dāng)用戶執(zhí)行一個用戶界面級的操作時，會引發(fā)一個事件，通常一個鍵盤和鼠標(biāo)操作將引發(fā)一個系統(tǒng)事先定義好的事件，用戶程序只需要編寫代碼定義每個事件發(fā)生時程序應(yīng)做何種響應(yīng)即可[8]。事件 ：說明“發(fā)生了什么事情”的對象。 系統(tǒng)根據(jù)用戶的操作構(gòu)造出相應(yīng)事件類的對象。事件可以分為焦點(diǎn)事件、鍵盤事件、鼠標(biāo)事件。事件源：有自己的方法，通過它像其注冊事件監(jiān)聽器，事件監(jiān)聽器是一個實例。事件處理程序：是一個方法，它接收一個事件對象然后分析這個對象最后完成對該事件的處理。每個事件有一個相應(yīng)的監(jiān)聽者接口，它規(guī)定了能夠接收（并處理）該類事件的方法的規(guī)范。 界面構(gòu)成第三節(jié) 相關(guān)算法的介紹一、冒泡排序什么是交換所謂交換，就是根據(jù)序列中兩個元素關(guān)鍵字的比較結(jié)果對換這兩個記錄在序列中的位置，基于交換排序的算法有很多，本次設(shè)計以冒泡排序來為例子，更容易讓人們理解交換的概念。冒泡排序的概念冒泡排序算法的基本思想是：假設(shè)待排序長為n，從后向前或者從前向后兩兩比較相鄰元素的值。這里我假如是從從小到大排序，若為逆序（即A[i1]A[i]）,則交換他們直到序列比較完，我們稱他們?yōu)橐惶嗣芭?，結(jié)果將最小的元素交換到待排元素的序列的第一個位置，下一趟冒泡時，前一趟確定的最小元素不再參與比較，待排序列減少一個元素，每趟冒泡的結(jié)果把序列中的最小元素放到了序列的最終位置，......，這樣最多做n1趟冒泡排序就把所有元素排好序[9]。冒泡排序的性能分析冒泡排序的性能分析如下：空間效率：僅使用了常數(shù)個輔助單元，因而空間復(fù)雜度為0(1)。時間效率：當(dāng)初始序列有序時，比較次數(shù)為n1次，移動次數(shù)為0，從而最好情況下的時間復(fù)雜度為O(n)；當(dāng)初始序列為逆序時，需要進(jìn)行n1趟排序，第i趟需要進(jìn)行ni次關(guān)鍵字的比較，而且每次比較都需要移動三次來交換元素位置。這種情況下:元素的比較次數(shù)==n(n1)/2元素的移動次數(shù)：==3n(n1)/2從而最壞情況下時間復(fù)雜度為O(n*n)。穩(wěn)定性：由于當(dāng)ij且A[i].key=A[j].key時不會交換兩個元素，從而冒泡排序算法是一個穩(wěn)定的排序算法。由此可以總結(jié)出冒泡排序的優(yōu)點(diǎn)是具有穩(wěn)定性，缺點(diǎn)是慢，每次只能移動相鄰的兩個數(shù)據(jù)。冒泡排序雖然可能不是最好的做法排序[10]，但確是經(jīng)常用的一種排序算法。二、插入排序什么是插入排序它的基本思想就是每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好的子序列中，直到完成了全部記錄插入。由插入排序可以引申出三種重要的排序算法：直接插入排序、折半插入排序、希爾排序。在這里主要介紹直接插入排序。直接插入插入排序的概念直接插入排序是一種簡單的排序方法，它的基本操作是將一個記錄插入到已經(jīng)排好的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。例如，已知待排序的一組記錄的初始序列如下所示：有序序列L[1…i1]L(i)無序序列L[i+1…n]為了實現(xiàn)將元素L(i)插入到已有序的子序列L[1.......i1]中我們需要執(zhí)行以下操作（為避免混淆，下面用”L[]”表示一個表，而L（）表示一個元素排序L(i)在L[1.......i1中的出入位置k。將L[k.......i1]中所有元素后移一個位置。將L(i)復(fù)制到L(k)。為了實現(xiàn)對L[1...n]的排序，可以將L(2)到L(n)依前面次插入到前面已經(jīng)排好的子序列當(dāng)中，初始假設(shè)L[1]是一個已經(jīng)排好的子序列，上述操作執(zhí)行n1次，就能得到一個有序的表插入排序在實現(xiàn)上通常采用的就是就地排序（空間復(fù)雜度為O(1)）,因而在從后向前的比較過程中，需要反復(fù)把已經(jīng)排好的元素逐步向后移位，為新元素提供插入空間。直接插入排序的性能分析直接插入排序的性能分析如下：空間效率：僅使用了常數(shù)個輔助單元，因而空間復(fù)雜度為0(1)。時間效率：在排序過程中，向有序字表中逐個的插入元素的操作進(jìn)行了n1趟，每趟操作都分為比較關(guān)鍵字和移動元素，而比較次數(shù)和移動次數(shù)是取決于排序表初始狀態(tài)的。在最好的情況下，表中元素已經(jīng)有序，此時每插入一個元素，都只需比較移動一次而不用移動元素，因而時間復(fù)雜度為O（n)。在最壞的情況下：表中序列剛好與排序結(jié)果中元素順序相反（逆序）的的移動次數(shù)為0，總的比較次數(shù)達(dá)到最大，為，總的移動次數(shù)也達(dá)到最大，為。平均情況下，考慮待排序元素是隨機(jī)的，此時可以取上述最好與最壞情況的平均值作為平均情況下的時間復(fù)雜度，總的比較次數(shù)與總的移動次數(shù)約為n*n/4。由此直接插入排序算法的時間復(fù)雜度為O(n*n),插入排序往往能表現(xiàn)出很好的性能。穩(wěn)定性：由于每次插入元素時總是從后向前先比較再移動的，所以不會出現(xiàn)相同元素的相對位置發(fā)生變化，即直接插入排序算法是一個穩(wěn)定的排序算法。適用性：直接插入排序適用順序儲存和鏈?zhǔn)絻Υ娴木€性表。當(dāng)為鏈?zhǔn)絻Υ鏁r可以從前往后排序指定元素的位置，通常的排序算法中，大部分都僅適用于順序的線性表。三、選擇排序什么是選擇排序選擇排序的的基本思想是：每一趟（例如第i趟）在后面ni+1(i=1,2,...,n1)個待排序元素中選擇關(guān)鍵字最小的元素，作為有序元素序列的第i個元素，直到第n1趟做完，待排序元素只剩下一個，就不用選了。簡單選擇排序的概念假設(shè)排序表為L[1...n],第i趟排序即從L[i...n]中選擇關(guān)鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置，這樣經(jīng)過n1趟排序就可以使得整個排序表有序。簡單選擇排序的性能分析簡單選擇排序的性能分析如下：空間效率：僅使用了常數(shù)個輔助單元，因而空間復(fù)雜度為0(1)。時間效率：元素的移動操作很少不會超過3（n1）次，最好情況下移動次數(shù)為0，此時對應(yīng)的表已經(jīng)有序；但元素間比較的次數(shù)與元素的初始序列無關(guān)，始終是n(n1)/2；所以時間復(fù)雜度始終是O(n*n)。穩(wěn)定性。在第i趟找到最小元素后，和第i個元素交換，可能會導(dǎo)致第i個元素與其含有相同關(guān)鍵字元素的相對位置發(fā)生改變，因此，簡單選擇排序是一個不穩(wěn)定的排序算法。四、 二叉查找樹二叉查找樹的定義二叉查找樹（簡稱BST）也稱二叉排序樹。二叉查找樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： （1）若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)關(guān)鍵字的值； （2）若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的關(guān)鍵值值； （3）左、右子樹也分別為二叉查找樹；由此定義可以知，二叉查找樹是一個遞歸的數(shù)據(jù)結(jié)構(gòu)，可以很方便地使用遞歸算法對二叉查找樹進(jìn)行各種運(yùn)算，根據(jù)二叉查找樹的定義，左子樹=根節(jié)點(diǎn)值=右子樹節(jié)點(diǎn)值，所以，對二叉查找樹進(jìn)行中序遍歷，可以得到一個非遞減的有序序列。例如，下圖的二叉樹查找的中序遍歷的順序為234579，： 一棵二叉樹二叉查找樹的建立建立一顆二叉查找樹，就是要依順序輸入數(shù)據(jù)元素，然后將他們插入到二叉查找樹合適的位置的一個過程，其具體的過程，就是在每次輸入一個元素的時候，就要建立一個新的結(jié)點(diǎn)，如果二叉查找樹不是空的，就將新結(jié)點(diǎn)的值與根結(jié)點(diǎn)， 如果小于根結(jié)點(diǎn)的值，就要其插入到左子樹種，如果比根結(jié)點(diǎn)大，就需要將其插入到右子樹中。如果二叉樹為空，就將新結(jié)點(diǎn)作為根結(jié)點(diǎn)。二叉查找樹的插入二叉樹是一種動態(tài)的集合，它的特點(diǎn)是樹的結(jié)點(diǎn)往往不是僅以此就能生成的，而是在通過排序的過程中，當(dāng)且僅當(dāng)該關(guān)鍵值不等于樹中的時候才插入。因為二叉查找樹是的定義是遞歸的，那么插入結(jié)點(diǎn)的過程是，如果原來的二叉樹是空的，就可以把結(jié)點(diǎn)直接插入進(jìn)去，如果不是空的，若關(guān)鍵字的值比根結(jié)點(diǎn)小，就將其出入到左子樹中，如果比根結(jié)點(diǎn)的值大，就要將其插入到右子樹中。二叉查找樹的刪除當(dāng)刪除一個二叉查找樹的結(jié)點(diǎn)時，不可以把以該結(jié)點(diǎn)的作為根的子樹上的結(jié)點(diǎn)都刪除了，而是必須先把要刪除的結(jié)點(diǎn)從存儲的二叉樹的鏈表上摘下，把因為刪除結(jié)點(diǎn)而斷開的二叉鏈表，重新連接起來，而且要確保二叉查找樹的性質(zhì)不會改變[13]。刪除操作的過程一般按三種情況來處理的：假如刪除的結(jié)點(diǎn)是A是葉結(jié)點(diǎn)，就可以直接刪了，而不會改變該二叉樹的性質(zhì)。如果結(jié)點(diǎn)A或者是一顆左子樹，或者是右子樹，就讓A的子樹成為a父節(jié)點(diǎn)的子樹，代替A 的位置。如果結(jié)點(diǎn)A既有左子樹，又有右子樹，就令A(yù)的直接后繼（或者是直接前驅(qū)）代替A，然后從二叉排序中刪去這個直接后繼（或者直接前驅(qū)），這樣就可以換成前面兩種情況了。二叉查找樹的性能分析二叉查找樹的高度為H，它的插入和刪除操作的運(yùn)行時間都是O(H),但是在最壞的情況下，即構(gòu)造二叉查找樹的輸入序列是有序的，就會形成一個傾斜的單支樹，此時二叉查找樹的性能就會明顯的變壞，樹的高度也增加元素N。在等概率的條件下，ASL=(1+2*2+3*4+4*3)/10=3ASL=(1+2+3+4+5+6+7+8+9+10)/10=由此可知，二叉查找樹排序算法的平均排序長度，主要取決于樹的高度，即與二叉樹的形態(tài)無關(guān)。從排序過程看，二叉查找樹也二分排序相識，就平均時間而言，二叉查找樹的排序和二分排序差不多，但二分排序的判定樹唯一，而二叉查找樹不唯一，相同的關(guān)鍵字，其插入順序不同可能生成不同的二叉查找樹。就維護(hù)表而言，二叉查找樹無須移動結(jié)點(diǎn)，只需修改指針即可，插入和刪除操作，其平均執(zhí)行時間為0(log2n)。二分排序的對象是有序順序表，若有插入和刪除結(jié)點(diǎn)的操作，則維護(hù)表的有序性所花的代價是O(n)。當(dāng)有序表是靜態(tài)排序表時，易用順序表作為存儲結(jié)構(gòu)，而采用二分排序?qū)崿F(xiàn)其排序操作。若有序表是動態(tài)排序表，則應(yīng)選擇二叉查找樹作為存儲結(jié)構(gòu)。第四節(jié) 本章小結(jié)在本章中比較詳細(xì)的介紹了Java的相關(guān)知識及其發(fā)展史，了解到了Java的主要特性。在后面章節(jié)中，我們會一實際的算法可視化的例子來說明是如何實現(xiàn)相關(guān)功能的。還介紹了關(guān)于圖形界面知識的概念，通過此本章的學(xué)習(xí)，能讓大家怎樣完成圖形界面實現(xiàn)，設(shè)計出更美觀的界面，對以后進(jìn)一步學(xué)習(xí)這部分的知識很有幫助。最后還介紹了四種排序算法的概念，操作的實現(xiàn)以及算法的性能分析，通過此本章的學(xué)習(xí)，能讓大家清楚排序算法的基本原理和具體實現(xiàn)過程，能在不同的情況下選擇適合的排序算法，能讓大家更好的掌握知識并運(yùn)用所學(xué)的知識解決問題。第三章 需求分析需求分析是軟件定義時期的最后一個階段，它的工作是軟件工程生命周期中的第一步，也是起決定性的一步，在需求分析階段我們需要全面了解整個系統(tǒng)的功能和性能方面的要求，為軟件設(shè)計打下堅實的基礎(chǔ)[14]。它的基本任務(wù)是確定系統(tǒng)必須完成哪些工作，也就是對目標(biāo)系統(tǒng)提出完整、準(zhǔn)確、清晰、具體的要求。第一節(jié) 系統(tǒng)功能需求一、系統(tǒng)設(shè)計目標(biāo)開發(fā)軟件首先做的是開發(fā)過程中最主要的就是系統(tǒng)的需求分析[15]，了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備獨(dú)立分析和能力；提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；設(shè)計并實現(xiàn)直觀、容易被理解的排序算法和二叉查找樹的動態(tài)演示系統(tǒng)，是系統(tǒng)設(shè)計的目標(biāo)。二、系統(tǒng)功能需求算法可視化的演示有很多種，而此次設(shè)計要想實現(xiàn)的就是借助以前學(xué)過的數(shù)據(jù)結(jié)構(gòu)所學(xué)的知識，實現(xiàn)對排序算法的演示。排序算法所實現(xiàn)的功能① 輸入少于20個小于650的整數(shù)，并對其排序演示。② 實現(xiàn)對冒泡排序進(jìn)行演示，并顯示排序前后的數(shù)組，排序所交換的次數(shù)、比較的次數(shù)、探測的次數(shù)及其所用的總的時間。③ 實現(xiàn)對插入排序進(jìn)行演示，并顯示排序前后的數(shù)組，排序所交換的次數(shù)、比較的次數(shù)、探測的次數(shù)及其所用的總的時間。④ 實現(xiàn)對選擇排序排序進(jìn)行演示，并顯示排序前后的數(shù)組，排序所交換的次數(shù)、比較的次數(shù)、探測的次數(shù)及其所用的總的時間。⑤ 可以生成隨機(jī)數(shù)，然后進(jìn)行插入、選擇、冒泡三種排序演示。⑥ 對一個已有的文本文件進(jìn)行排序演示。二叉查找樹實現(xiàn)的功能① 二叉查找樹的插入演示。 ②二叉查找樹的刪除演示。③二叉查找樹的查找路徑演示。第二節(jié) 系統(tǒng)運(yùn)行環(huán)境本系統(tǒng)對運(yùn)行環(huán)境的要求如下：硬件環(huán)境：①PC兼容機(jī)；②2G 內(nèi)存。軟件環(huán)境：① 操作系統(tǒng)：Windows XP、Windows Windows 8；② 相關(guān)應(yīng)用軟件：JDK、Eclipse。第三節(jié) 本章小結(jié)本章主要是對算發(fā)可視化演示系統(tǒng)的設(shè)計目標(biāo)和系統(tǒng)所所要實現(xiàn)的功能以及運(yùn)行環(huán)境進(jìn)行了分析。需求分析在軟件的開發(fā)中是很關(guān)鍵的一步，一個軟件開發(fā)成功與否需求分析起著十分重要的作用，所以我們在開發(fā)一個軟件前，一定要做好需求分析。第四章 系統(tǒng)設(shè)計第一節(jié) 系統(tǒng)總體