畢業(yè)論文---數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)</p><p>　　Data Structure Demonstration System</p><p><b>　　目錄</b></p><p><b>　　目錄I</b></p><p><b>　　摘要IV</b><

2、/p><p>　　ABSTRACTV</p><p><b>　　前言1</b></p><p><b>　　第1章 緒論2</b></p><p>　　1.1課題研究背景2</p><p>　　1.2國(guó)內(nèi)計(jì)算機(jī)輔助教學(xué)的現(xiàn)狀2</p><p>

3、　　1.3計(jì)算機(jī)輔助教學(xué)的發(fā)展趨勢(shì)4</p><p>　　1.4系統(tǒng)建設(shè)的目的4</p><p><b>　　本章小結(jié)5</b></p><p>　　第2章 需求分析6</p><p>　　2.1功能性需求分析6</p><p>　　2.1.1系統(tǒng)需求6</p><

4、p>　　2.1.2識(shí)別參與者和用例7</p><p>　　2.1.3用例的事件流描述9</p><p>　　2.2非功能性需求分析18</p><p>　　2.2.1設(shè)計(jì)思想18</p><p>　　2.2.2可行性分析19</p><p><b>　　本章小結(jié)20</b><

5、;/p><p>　　第3章 系統(tǒng)詳細(xì)設(shè)計(jì)21</p><p>　　3.1系統(tǒng)總體結(jié)構(gòu)圖21</p><p>　　3.2靜態(tài)結(jié)構(gòu)模型21</p><p>　　3.2.1定義系統(tǒng)對(duì)象類(lèi)21</p><p>　　3.2.2定義用戶界面類(lèi)25</p><p>　　3.2.3建立類(lèi)圖31</

6、p><p>　　3.3動(dòng)態(tài)行為模型31</p><p><b>　　本章小結(jié)39</b></p><p>　　第4章 系統(tǒng)實(shí)現(xiàn)40</p><p>　　4.1多線程簡(jiǎn)介40</p><p>　　4.1.1線程、多線程概念40</p><p>　　4.1.2實(shí)現(xiàn)多線程的

7、方法40</p><p>　　4.2動(dòng)態(tài)算法演示模板42</p><p>　　4.3算法演示的多線程設(shè)計(jì)43</p><p>　　4.3.1源代碼同步演示的實(shí)現(xiàn)44</p><p>　　4.3.2動(dòng)畫(huà)的同步實(shí)現(xiàn)45</p><p>　　4.3.3算法中變量值的同步實(shí)現(xiàn)45</p><p&

8、gt;<b>　　本章小結(jié)45</b></p><p><b>　　結(jié)論46</b></p><p><b>　　總結(jié)與體會(huì)47</b></p><p><b>　　謝辭48</b></p><p><b>　　參考文獻(xiàn)49</b

9、></p><p><b>　　附錄一50</b></p><p><b>　　附錄二55</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)</p><p><b>　　摘要</b></p><p>　　本系統(tǒng)以清華大學(xué)出版社出版的C語(yǔ)言版《數(shù)

10、據(jù)結(jié)構(gòu)》為藍(lán)本，合理地選擇數(shù)據(jù)結(jié)構(gòu)中部分算法并在系統(tǒng)中進(jìn)行有機(jī)地組合,形成優(yōu)化的動(dòng)態(tài)演示系統(tǒng)。 它可適應(yīng)讀者對(duì)算法的演示數(shù)據(jù)和過(guò)程執(zhí)行的控制方式的不同需求, 在計(jì)算機(jī)的屏幕上顯示算法執(zhí)行過(guò)程中數(shù)據(jù)的邏輯結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)的變化狀況或遞歸算法執(zhí)行過(guò)程中棧的變化狀況。本系統(tǒng)采用C#多線程技術(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)算法的算法動(dòng)態(tài)演示設(shè)計(jì)，提供及源代碼跟蹤、變量跟蹤、模擬動(dòng)態(tài)效果“三合一“的算法演示同步平臺(tái)。</p><p>　　關(guān)

11、鍵詞：算法,動(dòng)態(tài)演示,C#,多線程,同步</p><p>　　Data Structure Demonstration System</p><p><b>　　ABSTRACT</b></p><p>　　This system takes Qinghua University publishing house publication C l

12、anguage version “Data Structure“ as a main source, reasonably chooses part of algorithms in the Data Structure and carries on in the system organically combinations, forms the optimized dynamic demonstration system. It m

13、ay adapt the readers’ different demands to the algorithm data-in and control modes the process execution, and demonstrates in the algorithm implementation on the computer screen the data logical organization eit</p>

14、;<p>　　Keywords: Data structures, Dynamic demonstration, C#, Multhread, Synchronous</p><p><b>　　前言</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)的核心課程，對(duì)各類(lèi)算法的理解則是課程教學(xué)的重點(diǎn)和難點(diǎn)，算法動(dòng)態(tài)演示作為輔助教學(xué)過(guò)程的手段則可以有效

15、幫助學(xué)生更快的理解、掌握算法。數(shù)據(jù)結(jié)構(gòu)對(duì)后續(xù)課程的學(xué)習(xí)極其重要。但該課程涉及大量的概念、定義、模型和算法，顯得很抽象和深?yuàn)W。在教學(xué)過(guò)程中，如果能加以計(jì)算機(jī)輔助教學(xué)，可以提高教學(xué)效果，所以編寫(xiě)這樣的程序不僅有助于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，同時(shí)也大大增強(qiáng)了學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的編程能力。這是因?yàn)?，一方面利用算法演示系統(tǒng)的生動(dòng)性和直觀性，使教學(xué)內(nèi)容條理化和形象化，降低了對(duì)知識(shí)理解的難度；另一方面，由于演示系統(tǒng)的趣味性和交互性，有利于激發(fā)學(xué)生濃厚的學(xué)習(xí)

16、興趣，使其愿學(xué)、樂(lè)學(xué)。</p><p>　　可視化是演示系統(tǒng)應(yīng)該具備的要求。本系統(tǒng)采用C#多線程技術(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)算法的算法動(dòng)態(tài)演示設(shè)計(jì)，提供及源代碼跟蹤、變量跟蹤、模擬動(dòng)態(tài)效果“三合一“的算法演示同步平臺(tái)。</p><p><b>　　緒論</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專(zhuān)業(yè)的核心課程，重點(diǎn)培養(yǎng)學(xué)生在對(duì)數(shù)據(jù)分析組織與程序設(shè)計(jì)

17、算法思想上的綜合能力。算法是數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，也是數(shù)據(jù)結(jié)構(gòu)教學(xué)的重點(diǎn)和難點(diǎn)。但在數(shù)據(jù)結(jié)構(gòu)的教學(xué)過(guò)程中，使用傳統(tǒng)的靜態(tài)課件或“粉筆 + 黑板”教學(xué)形式很難將算法的執(zhí)行過(guò)程動(dòng)態(tài)地演示出來(lái)，影響了教學(xué)效果?！稊?shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示設(shè)計(jì)》是使用專(zhuān)業(yè)編程技術(shù)實(shí)現(xiàn)算法的動(dòng)態(tài)展示，使學(xué)生更直觀的從算法的設(shè)計(jì)思想、程序運(yùn)行描述、程序運(yùn)行結(jié)果同步跟蹤展示等全方位的了解算法，使學(xué)生能主動(dòng)積極地學(xué)習(xí)和掌握應(yīng)用這些算法。 </p><p&g

18、t;<b>　　1.1課題研究背景</b></p><p>　　隨著現(xiàn)代科學(xué)技術(shù)的迅猛發(fā)展，計(jì)算機(jī)技術(shù)已滲透到各個(gè)領(lǐng)域，成為各行業(yè)必不可少的工具，特別是Internet技術(shù)的推廣和信息高速公路的建立，使IT產(chǎn)業(yè)在市場(chǎng)競(jìng)爭(zhēng)中越發(fā)顯示出其獨(dú)特的優(yōu)勢(shì)，步入數(shù)字化時(shí)代，有巨大的數(shù)據(jù)信息等待著加工處理和傳輸，這將現(xiàn)實(shí)的許多東西都進(jìn)入虛擬的世界當(dāng)中，這都需要計(jì)算機(jī)技術(shù)的支持。同樣的，學(xué)院的教學(xué)手段也在逐

19、步信息化，這使得計(jì)算機(jī)輔助教學(xué)CAI的出現(xiàn)成為一種必然的趨勢(shì)。</p><p>　　90 年代以來(lái), 隨著多媒體和Internet 網(wǎng)絡(luò)的出現(xiàn)，計(jì)算機(jī)教育已步入一個(gè)全新的階段，計(jì)算機(jī)輔助教學(xué)CAI作為一種先進(jìn)的教學(xué)手段正逐步滲透于各類(lèi)院校的各個(gè)學(xué)科?！稊?shù)據(jù)結(jié)構(gòu)》不僅是大學(xué)計(jì)算機(jī)專(zhuān)業(yè)的核心課程之一，也是非計(jì)算機(jī)專(zhuān)業(yè)的主要選修課程之一。該課程涉及大量的概念、數(shù)據(jù)結(jié)構(gòu)和算法，理論性強(qiáng)又較為抽象，尤其是對(duì)算法描述的執(zhí)行過(guò)

20、程的理解是難點(diǎn)和重點(diǎn)。在課堂教學(xué)上，大量的算法不可能也無(wú)法一一詳述。運(yùn)用計(jì)算機(jī)輔助教學(xué)系統(tǒng)——《數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)》可以使教學(xué)內(nèi)容化靜為動(dòng)，調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣；變難為易，提高學(xué)生學(xué)習(xí)興趣；使學(xué)生寓學(xué)于樂(lè)，培養(yǎng)學(xué)生的學(xué)習(xí)興趣，與此同時(shí)，利用計(jì)算機(jī)輔助教學(xué)還可以滿足學(xué)生的學(xué)習(xí)興趣。它已成為激發(fā)學(xué)生興趣的新方法、新手段。</p><p>　　1.2國(guó)內(nèi)計(jì)算機(jī)輔助教學(xué)的現(xiàn)狀</p><p>

21、　　隨著時(shí)代的進(jìn)步，電子技術(shù)的飛速發(fā)展，全球網(wǎng)絡(luò)化進(jìn)程的加快，社會(huì)各行各業(yè)中都應(yīng)用到了計(jì)算機(jī)這種現(xiàn)代技術(shù)工具，目前我國(guó)的教育領(lǐng)域也已經(jīng)開(kāi)始運(yùn)用計(jì)算機(jī)輔助教學(xué)（Computer-Assisted Instruction,以下簡(jiǎn)稱CAI）這一現(xiàn)代化教學(xué)手段進(jìn)行教育教學(xué)。</p><p>　　作為一種媒體，計(jì)算機(jī)與其他教學(xué)媒體（如黑板、教科書(shū)、投影儀、電視機(jī)、錄像機(jī)等）沒(méi)有什么不同，能夠幫助教師提高教學(xué)效果、擴(kuò)大教學(xué)范

22、圍、延伸教師的教育功能。 課堂教學(xué)，在今天和今后相當(dāng)長(zhǎng)的歷史時(shí)期中，仍然是學(xué)校教學(xué)活動(dòng)的主要場(chǎng)所，因此計(jì)算機(jī)輔助教學(xué)（CAI）作為一種現(xiàn)代化的教學(xué)技術(shù)，將集中體現(xiàn)在課堂教學(xué)中。計(jì)算機(jī)輔助教學(xué)是利用計(jì)算機(jī)作為主要的教學(xué)媒體來(lái)進(jìn)行教學(xué)活動(dòng)，即利用計(jì)算機(jī)來(lái)輔助教師執(zhí)行教學(xué)。計(jì)算機(jī)不僅能呈現(xiàn)單純的文字、數(shù)字等字符教學(xué)信息，而且還能。輸出動(dòng)畫(huà)、視頻、圖像和聲音，能非常容易做到教學(xué)信息的圖、文、聲并茂，這種多維立體的教育信息傳播，增強(qiáng)了信

23、息的真實(shí)感和表現(xiàn)力。另外，計(jì)算機(jī)作為教學(xué)媒體，學(xué)生可利用一定的輸入、輸出設(shè)備，通過(guò)人機(jī)“對(duì)話”的方式進(jìn)行學(xué)習(xí)，這種人機(jī)交互作用是計(jì)算機(jī)媒體所特有的。</p><p>　　計(jì)算機(jī)輔助教學(xué)的作用。多年以來(lái)，我們的教學(xué)工作一般都是教師用黑板板書(shū)，用口頭說(shuō)教；學(xué)生用筆記錄，用耳朵聽(tīng)講，所以，教師和學(xué)生都形成了一定的思維定勢(shì)。隨著時(shí)代的發(fā)展和科學(xué)技術(shù)的進(jìn)步，人類(lèi)的教育水平及教育手段也在不斷的提高。電化教育已滲透到各個(gè)學(xué)科當(dāng)

24、中，近30年來(lái)，計(jì)算機(jī)輔助教學(xué)（CAI）興起，利用計(jì)算機(jī)來(lái)幫助教師執(zhí)行教學(xué)功能，老師運(yùn)用計(jì)算機(jī)輔助教學(xué)的手段，采用計(jì)算機(jī)多媒體教學(xué)方法，成為激發(fā)學(xué)生興趣的新方法。如教師在教學(xué)中，可以運(yùn)用計(jì)算機(jī)來(lái)呈現(xiàn)教學(xué)計(jì)劃、教學(xué)內(nèi)容、記錄學(xué)生的學(xué)習(xí)情況和控制學(xué)習(xí)進(jìn)程等；教師可以在教學(xué)中根據(jù)本學(xué)科的特點(diǎn)，制作各種課件、軟件，使整個(gè)課堂從原來(lái)抽象、死板的氛圍轉(zhuǎn)到生動(dòng)、活躍起來(lái)，把教師的主導(dǎo)性和學(xué)生的主體性充分發(fā)揮出來(lái)[16]。</p><

25、;p>　　傳統(tǒng)的教學(xué)方法正在逐步向現(xiàn)代化計(jì)算機(jī)輔助教學(xué)方向發(fā)展。但目前，計(jì)算機(jī)輔助教學(xué)還屬于起步階段，很多工作還需要進(jìn)一步開(kāi)展。目前我國(guó)經(jīng)濟(jì)欠發(fā)達(dá)地區(qū)還沒(méi)有開(kāi)展計(jì)算機(jī)輔助教學(xué)，還有一些教育工作者對(duì)計(jì)算機(jī)普及教育以及運(yùn)用計(jì)算機(jī)改革傳統(tǒng)教學(xué)的興趣不濃，積極性不高，為此，應(yīng)從提高認(rèn)識(shí)入手，著力從教育系統(tǒng)內(nèi)部的觀念更新向全社會(huì)教育觀念更新推進(jìn)。</p><p>　　1.3計(jì)算機(jī)輔助教學(xué)的發(fā)展趨勢(shì)</p>

26、<p>　　目前我國(guó)已認(rèn)識(shí)到計(jì)算機(jī)輔助教學(xué)在教育教學(xué)中的重要作用，無(wú)論是從經(jīng)濟(jì)上還是在教師培訓(xùn)上都在采用積極的態(tài)度：對(duì)CAI軟件的開(kāi)發(fā)作理論上、技術(shù)上和應(yīng)用方面的深入研究，是促進(jìn)CAI不斷發(fā)展的基礎(chǔ)工作，此方面已給予充分重視。同時(shí)也正在不斷地解決CAI軟件使用中的問(wèn)題，其中教師的培訓(xùn)是一個(gè)關(guān)鍵。不僅要使教師掌握CAI軟件的具體的使用方法，更重要的是觀念的轉(zhuǎn)變，以教學(xué)改革促進(jìn)CAI的應(yīng)用，反之又通過(guò)CAI的應(yīng)用促進(jìn)教學(xué)改革。

27、CAI是在教育教學(xué)改革中產(chǎn)生和發(fā)展起來(lái)的，它本身帶有鮮明的革新品格。用傳統(tǒng)的方法、其它的媒體，甚至人類(lèi)教師本身無(wú)法或難以實(shí)現(xiàn)的目標(biāo)，通過(guò)計(jì)算機(jī)資源的合理應(yīng)用，將使問(wèn)題得到圓滿地解決。因此，明確CAI軟件的研究和應(yīng)用的根本目的在于改革教學(xué)、提高學(xué)生的培養(yǎng)質(zhì)量，而不在于為了形式上的使用，把研究、應(yīng)用和教師培訓(xùn)有機(jī)地結(jié)合起來(lái)，以研究促進(jìn)應(yīng)用，反過(guò)來(lái)又以應(yīng)用促進(jìn)研究，使其形成互動(dòng)機(jī)制，是保證CAI發(fā)展的正確途徑。計(jì)算機(jī)輔助教學(xué)的發(fā)展趨勢(shì)是：一是

28、網(wǎng)絡(luò)化。網(wǎng)絡(luò)化進(jìn)程的加快，信息資源無(wú)比豐富，我們可以利用網(wǎng)絡(luò)資源來(lái)制作自己的軟件和課件；視頻技術(shù)在教學(xué)中的應(yīng)用，我們可以把自己優(yōu)秀的課例通過(guò)視頻編</p><p>　　1.4系統(tǒng)建設(shè)的目的</p><p>　　科學(xué)技術(shù)越向前發(fā)展，人們?cè)饺菀撞僮骱婉{馭。計(jì)算機(jī)技術(shù)的迅速發(fā)展必將推動(dòng)CAI向著更先進(jìn)、更高水平的方向發(fā)展，在教育領(lǐng)域最終實(shí)現(xiàn)人——機(jī)之間的交互，對(duì)我國(guó)的教育事業(yè)最終起到大大的推動(dòng)作

29、用。計(jì)算機(jī)輔助教學(xué)系統(tǒng)——《數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)》建設(shè)的目的有以下幾點(diǎn)：</p><p>　　該系統(tǒng)可以使學(xué)員深入理解教材內(nèi)容、掌握基本的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)算法的實(shí)現(xiàn)過(guò)程有很好的幫助作用。</p><p>　　該系統(tǒng)不僅能呈現(xiàn)單純的文字、數(shù)字等字符教學(xué)信息，而且還能輸出動(dòng)畫(huà)、視頻、圖像和聲音，能非常容易做到教學(xué)信息的圖、文、聲并茂，這種多維立體的教育信息傳播，增強(qiáng)了信息的真實(shí)感和表現(xiàn)力。&

30、lt;/p><p>　　該系統(tǒng)可以使教學(xué)內(nèi)容化靜為動(dòng)，調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣；變難為易，提高學(xué)生學(xué)習(xí)興趣；使學(xué)生寓學(xué)于樂(lè),培養(yǎng)學(xué)生的學(xué)習(xí)興趣，與此同時(shí)，可以滿足學(xué)生的學(xué)習(xí)興趣。</p><p>　　根據(jù)以上3點(diǎn)可知該系統(tǒng)的建設(shè)是非常必要的。</p><p><b>　　本章小結(jié)</b></p><p>　　本章重點(diǎn)介紹了“基于C

31、#多線程技術(shù)的數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)”該課題的研究背景、國(guó)內(nèi)計(jì)算機(jī)輔助教學(xué)系統(tǒng)的現(xiàn)狀和發(fā)展趨勢(shì)以及建設(shè)該系統(tǒng)的目的。</p><p><b>　　需求分析</b></p><p>　　所謂需求分析是指研究問(wèn)題域，產(chǎn)生一個(gè)滿足用戶需求的系統(tǒng)模型。這個(gè)系統(tǒng)模型應(yīng)能正確地描述問(wèn)題域和系統(tǒng)責(zé)任，并使后續(xù)開(kāi)發(fā)階段的有關(guān)人員能根據(jù)這個(gè)模型繼續(xù)進(jìn)行工作。</p>&

32、lt;p>　　2.1功能性需求分析</p><p>　　本系統(tǒng)是一個(gè)動(dòng)態(tài)演示數(shù)據(jù)結(jié)構(gòu)算法執(zhí)行過(guò)程的輔助教學(xué)軟件，它可適應(yīng)讀者對(duì)算法的輸入數(shù)據(jù)和過(guò)程執(zhí)行的控制方式的不同需求，在計(jì)算機(jī)的屏幕上顯示算法執(zhí)行過(guò)程中數(shù)據(jù)的邏輯結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)的變化狀況或遞歸算法執(zhí)行過(guò)程中棧的變化狀況。整個(gè)系統(tǒng)使用菜單驅(qū)動(dòng)方式, 每個(gè)菜單包括若干菜單項(xiàng)。每個(gè)菜單項(xiàng)對(duì)應(yīng)一個(gè)動(dòng)作或一個(gè)子菜單。系統(tǒng)一直處于選擇菜單項(xiàng)或執(zhí)行動(dòng)作狀態(tài)，直到選擇了

33、退出動(dòng)作為止[5]。</p><p><b>　　2.1.1系統(tǒng)需求</b></p><p>　　經(jīng)過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)的基本需求分析后，該系統(tǒng)至少具備以下功能：</p><p>　　可以動(dòng)態(tài)演示順序表；</p><p><b>　　可以動(dòng)態(tài)演示鏈表；</b></p><

34、p>　　可以動(dòng)態(tài)演示二叉樹(shù)遍歷；</p><p>　　可以動(dòng)態(tài)演示二叉樹(shù)線索化；</p><p>　　可以動(dòng)態(tài)演示赫夫曼樹(shù)；</p><p>　　可以動(dòng)態(tài)演示拓?fù)渑判颍?lt;/p><p>　　可以動(dòng)態(tài)演示內(nèi)部排序；</p><p>　　可以顯示C語(yǔ)言編寫(xiě)的核心代碼；</p><p><

35、b>　　可以顯示變量；</b></p><p><b>　　可以跟蹤變量；</b></p><p>　　可以顯示算法設(shè)計(jì)思想；</p><p>　　可以暫停正在執(zhí)行的系統(tǒng)；</p><p>　　可以將暫停了的系統(tǒng)繼續(xù)執(zhí)行；</p><p>　　可以返回上一級(jí)菜單；</p&g

36、t;<p><b>　　可以跟蹤代碼；</b></p><p>　　可以恢復(fù)到演示的開(kāi)始；</p><p><b>　　可以重新設(shè)置數(shù)據(jù)；</b></p><p>　　可以顯示變動(dòng)態(tài)畫(huà)面。</p><p>　　上面每一行描述了一個(gè)功能，這種表達(dá)有利于測(cè)試需求的定義，因?yàn)槊恳恍忻枋龅墓δ?/p>

37、都是單獨(dú)可測(cè)的。由于分析設(shè)計(jì)是一個(gè)迭代的軟件開(kāi)發(fā)過(guò)程，所以需求也會(huì)在分析設(shè)計(jì)過(guò)程中不斷的補(bǔ)充、細(xì)化。上述的需求只是初步的基本需求，還有待不斷地細(xì)化、完善。</p><p>　　2.1.2識(shí)別參與者和用例</p><p>　　通過(guò)分析數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)的功能需求，由于它是一個(gè)單機(jī)版的系統(tǒng)，因此可識(shí)別出1個(gè)參與者，那就是操作該系統(tǒng)的人——操作者（OP）。</p><p

38、>　　用例是什么？其原始英文是use case，直譯過(guò)來(lái)就成了用例。這也是一個(gè)比較貼切的叫法了，從字面的直接理解就是使用的例子。另一種比較流行的定義是用例就是與使用者(actor)交互的，并且給使用者提供可觀測(cè)的有意義的結(jié)果的一系列活動(dòng)的集合。最具普遍意義的理解錯(cuò)誤是認(rèn)為用例就是功能的劃分和描述，認(rèn)為一個(gè)用例就是一個(gè)功能點(diǎn)。在這種理解下，用例變成了僅僅是較早前需求中功能框圖的翻版，很多人用用例來(lái)劃分子系統(tǒng)，功能模塊和功能點(diǎn)。如果這

39、樣，用例根本沒(méi)有存在的必要。</p><p>　　如果用例不是功能的話，它是什么呢？從定義上說(shuō)，能給使用者提供一個(gè)執(zhí)行結(jié)果的活動(dòng)，不就是功能嗎？我的回答是：錯(cuò)！功能是計(jì)算機(jī)術(shù)語(yǔ)，它是用來(lái)描述計(jì)算機(jī)的，而非定義需求的術(shù)語(yǔ)。功能實(shí)際描述的是輸入-->計(jì)算-->輸出。這讓你想到了什么？DFD圖？這可是典型的面向過(guò)程分析模式。實(shí)際上，把用例解釋為某個(gè)參與者(actor)要做的一件事可能更為合適。</p&

40、gt;<p>　　上面已經(jīng)識(shí)別出了參與者，通過(guò)對(duì)需求的進(jìn)一步分析，可以確定系統(tǒng)中有如下用例存在：</p><p>　　show sqList（演示順序表）</p><p>　　本用例提供了演示順序表的插入和刪除的功能</p><p>　　show linkList（演示鏈表）</p><p>　　本用例提供了演示鏈表的創(chuàng)建、插入

41、和刪除的功能。</p><p>　　show OrderTree（演示二叉樹(shù)遍歷）</p><p>　　本用例提供了演示二叉樹(shù)先序、中序和后序遍歷的功能。</p><p>　　show ThreTree（演示二叉樹(shù)線索化）</p><p>　　本用例提供了演示二叉樹(shù)先序、中序和后序線索化的功能。</p><p>　　由

42、于用例（3）和（4）有公共行為，因此可以抽象出一個(gè)父用例“create Tree”。</p><p>　　create Tree（創(chuàng)建二叉樹(shù)）</p><p>　　本用例描述了創(chuàng)建二叉樹(shù)的通用行為，是用例（3）和（4）的父用例。</p><p>　　show HuffmanCode（演示赫夫曼樹(shù)）</p><p>　　本用例提供了演示赫夫曼樹(shù)

43、創(chuàng)建的功能。</p><p>　　show TopoSort（演示拓?fù)渑判颍?lt;/p><p>　　本用例提供了演示拓?fù)渑判虻墓δ堋?lt;/p><p>　　show Sort（演示內(nèi)部排序）</p><p>　　本用例提供了演示內(nèi)部排序中的希爾排序和快速排序的功能。</p><p>　　系統(tǒng)的用例圖如圖2.2所示，參與者“

44、OP”與“show sqList”、“ show linkList”、“ show OrderTree“、”show ThreTree“、“create Tree”、”show HuffmanCode“、”show TopoSort“、”show Sort“交互。</p><p>　　圖2.2 系統(tǒng)用例圖</p><p>　　2.1.3用例的事件流描述</p><p&

45、gt;　　用例的事件流是對(duì)完成用例行為所需的事件的描述[4]。事件流描述了系統(tǒng)作什么，而不是描述系統(tǒng)應(yīng)該怎么做。下面對(duì)前面識(shí)別出的用例逐個(gè)進(jìn)行描述。</p><p>　　show sqList（演示順序表）</p><p>　　show linkList（演示鏈表）</p><p>　　show OrderTree（演示二叉樹(shù)遍歷）</p><p

46、>　　show ThreTree（演示二叉樹(shù)線索化）</p><p>　　show HuffmanCode（演示赫夫曼樹(shù)）</p><p>　　show TopoSort（演示拓?fù)渑判颍?lt;/p><p>　　show Sort（演示內(nèi)部排序）</p><p>　　2.2非功能性需求分析</p><p><b

47、>　　2.2.1設(shè)計(jì)思想</b></p><p>　　課件是教學(xué)內(nèi)容和教學(xué)處理兩大類(lèi)信息的有機(jī)結(jié)合，其目的是按某種學(xué)習(xí)理論和教學(xué)策略將教學(xué)中的重點(diǎn)和難點(diǎn)，教學(xué)上不容易講清楚的內(nèi)容借助計(jì)算機(jī)演示。CAI 系統(tǒng)在注重教學(xué)先進(jìn)性、科學(xué)性的同時(shí)更強(qiáng)調(diào)實(shí)用性。開(kāi)發(fā)滿足以下原則：</p><p>　　內(nèi)容覆蓋面寬：系統(tǒng)應(yīng)覆蓋該課程的主要內(nèi)容，并結(jié)合課程選用教材，用C語(yǔ)言來(lái)描述數(shù)據(jù)結(jié)構(gòu)

48、的算法。</p><p>　　功能實(shí)用化：為了能真正起到輔助教學(xué)的效果，系統(tǒng)使用多種演示手段如用單步跟蹤、連續(xù)執(zhí)行和跨越函數(shù)(或過(guò)程) 調(diào)用等方式來(lái)演示算法的具體執(zhí)行過(guò)程，且演示方式可隨時(shí)更換；演示的速度可隨時(shí)調(diào)節(jié)。</p><p>　　人機(jī)交互界面友好性：系統(tǒng)界面設(shè)計(jì)遵循實(shí)用、方便的原則，各種操作簡(jiǎn)潔明了。同時(shí)具備鼠標(biāo)接口和鍵盤(pán)接口，可接受來(lái)自于鼠標(biāo)或鍵盤(pán)的輸入；為了加深對(duì)算法的理解，允

49、許用戶通過(guò)輸入不同的初始數(shù)據(jù)來(lái)觀察算法的具體執(zhí)行情況。</p><p>　　中文字幕提示：系統(tǒng)演示插入了適當(dāng)?shù)恼f(shuō)明及注釋信息，以幫助系統(tǒng)使用者對(duì)演示過(guò)程的理解；為滿足不同層次用戶的需求，各種提示信息用中文給出。</p><p>　　系統(tǒng)運(yùn)行環(huán)境及可靠性：在保證系統(tǒng)功能的前提下，適當(dāng)?shù)亟档土讼到y(tǒng)對(duì)運(yùn)行環(huán)境的要求，以便系統(tǒng)可以在較低的配置系統(tǒng)軟件環(huán)境中正常運(yùn)行。對(duì)于各種有意或無(wú)意的錯(cuò)誤操作及錯(cuò)

50、誤的輸入數(shù)據(jù)，系統(tǒng)能正確處理，保證系統(tǒng)不會(huì)意外終止。</p><p>　　2.2.2可行性分析</p><p><b>　　技術(shù)可行性研究</b></p><p>　　在IT行業(yè)中從業(yè)的工作人員一般都要求懂計(jì)算機(jī)，具有一定軟硬件基礎(chǔ)，會(huì)使用各種管理軟件，熟悉IT產(chǎn)品。因?yàn)樵撓到y(tǒng)是針對(duì)數(shù)據(jù)結(jié)構(gòu)算法的進(jìn)行動(dòng)態(tài)的演示，使學(xué)生更能理解算法和培養(yǎng)學(xué)生的興

51、趣。又因?yàn)閷W(xué)數(shù)據(jù)結(jié)構(gòu)這門(mén)課的老師和學(xué)生一般都是計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生，所以在新系統(tǒng)投入使用時(shí)，用戶都能很快地使用該系統(tǒng)。</p><p><b>　　操作可行性研究</b></p><p>　　本系統(tǒng)采用Windows圖形界面，是大家熟悉的操作系統(tǒng)，對(duì)于用戶只需要具有一般的計(jì)算機(jī)知識(shí)的人員都可以輕松上手。而且整個(gè)系統(tǒng)采用最友好的交互界面，簡(jiǎn)潔明了，不需要對(duì)數(shù)據(jù)庫(kù)的了解。由此

52、，該系統(tǒng)的操作是可行的，有必要推廣該系統(tǒng)！</p><p>　　綜合以上二方面，該系統(tǒng)具有很高的開(kāi)發(fā)可行性，無(wú)論是從技術(shù)上還是操作上。</p><p><b>　　本章小結(jié)</b></p><p>　　本章重點(diǎn)介紹了基于C#多線程技術(shù)的數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)功能性需求分析和非功能性需求分析。前者主要是對(duì)系統(tǒng)需求、系統(tǒng)總體結(jié)構(gòu)圖、用例的事件流描

53、述和用例圖進(jìn)行分析，后者主要描述了系統(tǒng)的設(shè)計(jì)思想和可行性分析。</p><p><b>　　系統(tǒng)詳細(xì)設(shè)計(jì)</b></p><p>　　3.1系統(tǒng)總體結(jié)構(gòu)圖</p><p>　　根據(jù)系統(tǒng)的需求，將系統(tǒng)劃分為圖2.1的結(jié)構(gòu)圖：</p><p>　　圖3.1 系統(tǒng)結(jié)構(gòu)圖</p><p><b>

54、;　　3.2靜態(tài)結(jié)構(gòu)模型</b></p><p>　　進(jìn)一步分析系統(tǒng)需求，識(shí)別出類(lèi)以及類(lèi)之間的關(guān)系，確定它們的靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)行為，是面向?qū)ο蠓治龅幕救蝿?wù)。系統(tǒng)的靜態(tài)結(jié)構(gòu)模型主要用類(lèi)圖或?qū)ο髨D來(lái)描述[8]。</p><p>　　3.2.1定義系統(tǒng)對(duì)象類(lèi)</p><p>　　定義過(guò)系統(tǒng)需求，就可以根據(jù)系統(tǒng)需求來(lái)識(shí)別系統(tǒng)中所存在的對(duì)象[7]。系統(tǒng)對(duì)象的識(shí)別可

55、以通過(guò)尋找系統(tǒng)域描述和需求描述中的名詞來(lái)進(jìn)行，從前述的系統(tǒng)需求的描述中可以找到的名詞有順序表（sqList）、鏈表（linkList）、二叉樹(shù)遍歷（OrderTree）、二叉樹(shù)線索化（ThreTree）、赫夫曼樹(shù)（HuffmanCode）、拓?fù)渑判颍═opoSort）、內(nèi)部排序（Sort），這些都是對(duì)象圖中的候選對(duì)象，判斷是否應(yīng)該為這些候選對(duì)象創(chuàng)建類(lèi)的方法是：是否有與該對(duì)象相關(guān)的身份和行為？如果答案是肯定的，那么候選對(duì)象應(yīng)該是一個(gè)存在與

56、模型中的對(duì)象，就應(yīng)該為之創(chuàng)建類(lèi)。</p><p>　　順序表（sqList）</p><p>　　順序表是沒(méi)有身份的，但它具有相關(guān)的行為，系統(tǒng)要?jiǎng)?chuàng)建順序表，可以演示順序表的插入和刪除。所以順序表是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為sqList。</p><p>　　鏈表（linkList）</p><p>　　鏈表是沒(méi)有身份的，但它具有相關(guān)的行為，系統(tǒng)要

57、，可以演示鏈表的創(chuàng)建、插入和刪除。所以鏈表是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為linkList。</p><p>　　二叉樹(shù)遍歷（OrderTree）</p><p>　　二叉樹(shù)遍歷是沒(méi)有身份的，但它具有相關(guān)的行為，系統(tǒng)要?jiǎng)?chuàng)建二叉樹(shù)，可以演示二叉樹(shù)的先序、中序和后序遍歷。所以二叉樹(shù)遍歷是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為OrderTree。</p><p>　　二叉樹(shù)線索化（ThreTre

58、e）</p><p>　　二叉樹(shù)線索化是沒(méi)有身份的，但它具有相關(guān)的行為，系統(tǒng)要?jiǎng)?chuàng)建二叉樹(shù)，可以演示二叉樹(shù)的先序、中序和后序線索化。所以二叉樹(shù)線索化是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為T(mén)hreTree。</p><p>　　赫夫曼樹(shù)（HuffmanCode）</p><p>　　赫夫曼樹(shù)是沒(méi)有身份的，但它具有相關(guān)的行為，可以演示赫夫曼樹(shù)的創(chuàng)建。所以赫夫曼樹(shù)是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為

59、HuffmanCode。</p><p>　　拓?fù)渑判颍═opoSort）</p><p>　　拓?fù)渑判蚴菦](méi)有身份的，但它具有相關(guān)的行為，系統(tǒng)要?jiǎng)?chuàng)建有向圖，可以演示拓?fù)渑判颉Ｋ酝負(fù)渑判蚴窍到y(tǒng)中的一個(gè)類(lèi)，類(lèi)名為T(mén)opoSort。</p><p>　　內(nèi)部排序（Sort）</p><p>　　內(nèi)部排序是沒(méi)有身份的，但它具有相關(guān)的行為，可以演示希

60、爾排序和快速排序。所以內(nèi)部排序是系統(tǒng)中的一個(gè)類(lèi)，類(lèi)名為Sort。</p><p>　　從上述分析，可以看出系統(tǒng)至少有7個(gè)重要的類(lèi)：順序表（sqList）、鏈表（linkList）、二叉樹(shù)遍歷（OrderTree）、二叉樹(shù)線索化（ThreTree）、赫夫曼樹(shù)（HuffmanCode）、拓?fù)渑判颍═opoSort）、內(nèi)部排序（Sort）。接著要確定這些類(lèi)的屬性和方法。</p><p><

61、b>　　類(lèi)sqList</b></p><p>　　transfer(string: str, sqList: &L ): void</p><p>　　該函數(shù)方法將字符串轉(zhuǎn)化為數(shù)組存放。</p><p>　　ins_sqList(sqList: &L, char: x, int i): void</p><p&

62、gt;　　該操作是順序表進(jìn)行插入，以線性表，插入字符和位置作為參數(shù)。</p><p>　　del_sqList(sqList: &L, int i): void</p><p>　　該操作是順序表進(jìn)行刪除，以線性表，刪除的位置作為參數(shù)。</p><p><b>　　類(lèi)linkList</b></p><p>　　

63、crt_linkList(int: n, linkList: &L ): void</p><p>　　創(chuàng)建一個(gè)單鏈表，以鏈表元素個(gè)數(shù)和鏈表作為參數(shù)。</p><p>　　ins_linkList(linkList: &L, char: x, int i): void</p><p>　　該操作是鏈表進(jìn)行插入，以鏈表，插入字符和位置作為參數(shù)。<

64、/p><p>　　del_linkList(sqList: &L, int i): void</p><p>　　該操作是鏈表進(jìn)行刪除，以鏈表，刪除的位置作為參數(shù)。</p><p>　　類(lèi)OrderTree</p><p>　　pre_Order(bt: bitree): void</p><p>　　該操作是對(duì)二

65、叉樹(shù)進(jìn)行先序遍歷。</p><p>　　in_Order(bt: bitree): void</p><p>　　該操作是對(duì)二叉樹(shù)進(jìn)行中序遍歷。</p><p>　　Post_Order(bt: bitree): void</p><p>　　該操作是對(duì)二叉樹(shù)進(jìn)行后序遍歷。</p><p><b>　　類(lèi)Th

66、reTree</b></p><p>　　pre_Thre(bt: bitree): void</p><p>　　該操作是對(duì)二叉樹(shù)進(jìn)行先序線索化。</p><p>　　in_ Thre (bt: bitree): void</p><p>　　該操作是對(duì)二叉樹(shù)進(jìn)行中序線索化。</p><p>　　Post

67、_ Thre (bt: bitree): void</p><p>　　該操作是對(duì)二叉樹(shù)進(jìn)行后序線索化。</p><p>　　類(lèi)HuffmanCode</p><p>　　HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n): void</p><p>　

68、　該操作用于創(chuàng)建赫夫曼樹(shù)和赫夫曼樹(shù)編碼。</p><p><b>　　類(lèi)TopoSort</b></p><p>　　TopologicalSort(ALGRAPH G):void</p><p>　　該操作用于拓?fù)渑判颉?lt;/p><p><b>　　類(lèi)Sort</b></p><

69、;p>　　ShellSort(int a[],int n):void</p><p>　　該操作用于希爾排序。</p><p>　　QuickSort(int a[],int left,int right): void</p><p>　　該操作用于快速排序。</p><p><b>　　類(lèi)bitree</b>&l

70、t;/p><p>　　Crt_Tree(bt: bitree): void</p><p>　　該操作用于創(chuàng)建二叉樹(shù)。</p><p>　　由于每一個(gè)算法的演示都要這些操作，因此把它抽象出一個(gè)類(lèi)出來(lái)。類(lèi)名為Demonstration。</p><p>　　類(lèi)Demonstration</p><p>　　在確定類(lèi)Demon

71、stration的屬性和方法時(shí)，應(yīng)考慮如下需求：</p><p>　　可以顯示C語(yǔ)言編寫(xiě)的核心代碼</p><p>　　在顯示時(shí)，應(yīng)提供C語(yǔ)言編寫(xiě)的核心代碼，因此，提供這個(gè)功能的操作定義應(yīng)該如下：</p><p>　　ShowCode(str: string): void</p><p><b>　　可以顯示變動(dòng)態(tài)畫(huà)面</b&

72、gt;</p><p>　　在顯示時(shí)，應(yīng)提供動(dòng)態(tài)畫(huà)面，因此，提供這個(gè)功能的操作定義應(yīng)該如下：</p><p>　　ShowDemon(): void</p><p><b>　　可以顯示變量</b></p><p>　　在顯示時(shí)，應(yīng)提供變量，因此，提供這個(gè)功能的操作定義應(yīng)該如下：</p><p>

73、　　ShowBL(str: string): void</p><p>　　可以顯示算法設(shè)計(jì)思想</p><p>　　在顯示時(shí)，應(yīng)提供算法設(shè)計(jì)思想，因此，提供這個(gè)功能的操作定義應(yīng)該如下：</p><p>　　ShowThink(str: string): void</p><p><b>　　可以返回上一級(jí)菜單</b>&

74、lt;/p><p>　　根據(jù)這個(gè)需求，定義如下操作：</p><p>　　Return():void</p><p><b>　　可以重新設(shè)置數(shù)據(jù)</b></p><p>　　根據(jù)這個(gè)需求，定義如下操作：</p><p>　　SetData(str: string) : void</p>

75、<p>　　可以恢復(fù)到演示的開(kāi)始</p><p>　　根據(jù)這個(gè)需求，定義如下操作：</p><p>　　ReStart(): void</p><p>　　可以暫停正在執(zhí)行的系統(tǒng)</p><p>　　可以將暫停了的系統(tǒng)繼續(xù)執(zhí)行</p><p><b>　　可以跟蹤代碼</b></

76、p><p><b>　　可以跟蹤變量</b></p><p>　　上述4個(gè)需求涉及到C#中線程部分，在定義系統(tǒng)類(lèi)的時(shí)候就不多說(shuō)了。因?yàn)樵趯?shí)現(xiàn)部分（第4章）會(huì)詳細(xì)說(shuō)明。</p><p>　　3.2.2定義用戶界面類(lèi)</p><p>　　用戶與系統(tǒng)需要交互，一個(gè)用戶友好的系統(tǒng)通常采用直觀的圖形化界面，因此需要定義系統(tǒng)的用戶界面類(lèi)

77、。</p><p>　　通過(guò)對(duì)系統(tǒng)的不斷分析和細(xì)化，可識(shí)別出如下界面類(lèi)以及類(lèi)的屬性和方法。</p><p>　　用來(lái)建立動(dòng)態(tài)模型的時(shí)序圖對(duì)于定義類(lèi)、類(lèi)的屬性和方法是很有幫助的，類(lèi)圖和時(shí)序圖的建立是相輔相成的，因?yàn)闀r(shí)序圖中出現(xiàn)的消息基本上會(huì)成為類(lèi)中的方法。</p><p><b>　　類(lèi)DemonGUI</b></p><p&

78、gt;　　DemonGUI是系統(tǒng)的主界面，系統(tǒng)的主界面上含有幾個(gè)按鈕，當(dāng)選擇不同的按鈕時(shí)，系統(tǒng)可以執(zhí)行不同的操作。當(dāng)程序退出時(shí)，主界面窗口關(guān)閉。</p><p><b>　　私有屬性</b></p><p><b>　　待定。</b></p><p><b>　　公共方法</b></p>

79、<p>　　newDemonGUI():void</p><p><b>　　創(chuàng)建系統(tǒng)主界面。</b></p><p>　　SqList():void</p><p>　　當(dāng)按下按鈕“順序表”時(shí)，該方法被調(diào)用。</p><p>　　LinkList():void</p><p>　　當(dāng)

80、按下按鈕“鏈表”時(shí)，該方法被調(diào)用。</p><p>　　orderTree():void</p><p>　　當(dāng)按下按鈕“二叉樹(shù)遍歷”時(shí)，該方法被調(diào)用。</p><p>　　threTree():void</p><p>　　當(dāng)按下按鈕“二叉樹(shù)線索化”時(shí)，該方法被調(diào)用。</p><p>　　huffmanCode():

81、void</p><p>　　當(dāng)按下按鈕“赫夫曼樹(shù)”時(shí)，該方法被調(diào)用。</p><p>　　topoSort():void</p><p>　　當(dāng)按下按鈕“拓?fù)渑判颉睍r(shí)，該方法被調(diào)用。</p><p>　　sort():void</p><p>　　當(dāng)按下按鈕“內(nèi)部排序”時(shí)，該方法被調(diào)用。</p><

82、;p>　　類(lèi)ListDialog</p><p>　　界面類(lèi)ListDialog是用來(lái)演示順序表和鏈表所需的對(duì)話框，其界面如圖3.2所示。當(dāng)按下主窗口DemonGUI中的按鈕“順序表”或“鏈表”時(shí)，該對(duì)話框彈出。當(dāng)按下“順序表”時(shí)，“鏈表相關(guān)操作“不可用，如果選擇“插入”，相對(duì)應(yīng)的標(biāo)簽改為“插入元素”和“插入位置”；如果選擇“刪除”，把對(duì)應(yīng)的標(biāo)簽改為“刪除位置” ，并把“插入元素”對(duì)應(yīng)的編輯框變得不可用。當(dāng)

83、按下“鏈表表”時(shí)，“順序表相關(guān)操作“不可用，如果選擇“插入”，相對(duì)應(yīng)的標(biāo)簽改為“插入元素”和“插入位置”；如果選擇“刪除”，把對(duì)應(yīng)的標(biāo)簽改為“刪除位置” ，并把“插入元素”對(duì)應(yīng)的編輯框變得不可用；如果選擇“創(chuàng)建”，只有“建立數(shù)據(jù)”可用，其他都不可用。</p><p>　　圖3.2 界面ListDialog</p><p><b>　　私有屬性</b></p>

84、;<p><b>　　待定。</b></p><p><b>　　公共方法</b></p><p>　　newListDialog():void</p><p>　　創(chuàng)建用于填寫(xiě)順序表的插入、刪除和鏈表創(chuàng)建、插入、刪除信息的窗口。</p><p>　　ins_sqList(): voi

85、d</p><p>　　當(dāng)按下“順序表”，選擇“插入”時(shí)，該方法被調(diào)用。</p><p>　　del_sqList(): void</p><p>　　當(dāng)按下“順序表”，選擇“刪除”時(shí)，該方法被調(diào)用。</p><p>　　ins_linkList(): void</p><p>　　當(dāng)按下“鏈表”，選擇“插入”時(shí)，該方

86、法被調(diào)用。</p><p>　　del_linkList(): void</p><p>　　當(dāng)按下“鏈表”，選擇“刪除”時(shí)，該方法被調(diào)用。</p><p>　　crt_linkList():void</p><p>　　當(dāng)按下“鏈表”，選擇“創(chuàng)建”時(shí)，該方法被調(diào)用。</p><p>　　類(lèi)TreeDialog<

87、/p><p>　　界面類(lèi)TreeDialog是用來(lái)演示二叉樹(shù)的遍歷、線索化和拓?fù)渑判蛩璧膶?duì)話框，其界面如圖3.3所示。當(dāng)按下主窗口DemonGUI中的按鈕“二叉樹(shù)遍歷”、“二叉樹(shù)線索化”或“拓?fù)渑判颉睍r(shí)，該對(duì)話框彈出。由于二叉樹(shù)的三種遍歷和三種線索化都差不多，因此，在這我就以中序遍歷和中序線索化為例。彈出的對(duì)話框根據(jù)所選的按鈕不同，form的標(biāo)題也顯示不同，為“建立二叉樹(shù)”、“建立線索化二叉樹(shù)”或“輸入有向圖”。&

88、lt;/p><p>　　圖3.3界面TreeDialog</p><p><b>　　私有屬性</b></p><p><b>　　待定。</b></p><p><b>　　公共方法</b></p><p>　　newTreeDialog():void&l

89、t;/p><p>　　用于創(chuàng)建二叉樹(shù)或線索化二叉樹(shù)的窗口。</p><p>　　in_ Order (): void</p><p>　　當(dāng)按下“二叉樹(shù)遍歷”，選擇“確定”時(shí)，該方法被調(diào)用。</p><p>　　in_ Thre (): void</p><p>　　當(dāng)按下“二叉樹(shù)線索化”，選擇“確定”時(shí)，該方法被調(diào)用。&

90、lt;/p><p>　　TopoSort (): void</p><p>　　當(dāng)按下“拓?fù)渑判颉?，選擇“確定”時(shí)，該方法被調(diào)用。</p><p><b>　　類(lèi)HCDialog</b></p><p>　　界面類(lèi)HCDialog是用來(lái)演示赫夫曼樹(shù)所需的對(duì)話框，其界面如圖3.4所示。當(dāng)按下主窗口DemonGUI中的按鈕“赫夫

91、曼樹(shù)”時(shí)，該對(duì)話框彈出。</p><p><b>　　私有屬性</b></p><p><b>　　待定。</b></p><p>　　圖3.4界面HCDialog</p><p><b>　　公共方法</b></p><p>　　newHCDialog

92、():void</p><p>　　用于創(chuàng)建赫夫曼樹(shù)的窗口。</p><p>　　huffmanCode():void</p><p>　　當(dāng)按下按鈕“赫夫曼樹(shù)”，選擇“確定”時(shí)，該方法被調(diào)用。</p><p>　　類(lèi)SortDialog</p><p>　　界面類(lèi)HCDialog是用來(lái)演示內(nèi)部排序所需的對(duì)話框，其界面

93、如圖3.5所示。當(dāng)按下主窗口DemonGUI中的按鈕“內(nèi)部排序”時(shí)，該對(duì)話框彈出。</p><p>　　圖3.5界面SortDialog</p><p><b>　　私有屬性</b></p><p><b>　　待定。</b></p><p><b>　　公共方法</b><

94、;/p><p>　　newSortDialog():void</p><p>　　用于創(chuàng)建內(nèi)部排序的窗口。</p><p>　　ShellSort():void</p><p>　　當(dāng)按下按鈕“內(nèi)部排序”，選擇“希爾排序”時(shí)，該方法被調(diào)用。</p><p>　　QuickSort(): void</p>&l

95、t;p>　　當(dāng)按下按鈕“內(nèi)部排序”，選擇“快速排序”時(shí)，該方法被調(diào)用。</p><p><b>　　類(lèi)MainForm</b></p><p>　　界面類(lèi)MainForm是用于顯示各個(gè)算法的對(duì)話框。該對(duì)話框?qū)λ惴▌?dòng)態(tài)演示進(jìn)行控制。詳細(xì)部分會(huì)在第4章說(shuō)明。</p><p><b>　　私有屬性</b></p>

96、;<p><b>　　待定。</b></p><p><b>　　公共方法</b></p><p>　　newMainForm():void</p><p>　　用于創(chuàng)建演示的窗口。</p><p>　　ShowCode(): void</p><p>　　當(dāng)運(yùn)

97、行MainForm時(shí)，該方法被調(diào)用。</p><p>　　ShowDemon(): void</p><p>　　當(dāng)運(yùn)行MainForm時(shí)，該方法被調(diào)用。</p><p>　　ShowBL(): void</p><p>　　當(dāng)運(yùn)行MainForm時(shí)，該方法被調(diào)用。</p><p>　　ShowThink(): voi

98、d</p><p>　　當(dāng)按下按鈕“設(shè)計(jì)思想“時(shí)，該方法被調(diào)用。</p><p>　　Return():void</p><p>　　當(dāng)按下按鈕“返回“時(shí)，該方法被調(diào)用。</p><p>　　SetData() : void</p><p>　　當(dāng)按下按鈕“數(shù)據(jù)“時(shí)，該方法被調(diào)用。</p><p&g

99、t;　　ReStart(): void</p><p>　　當(dāng)按下按鈕“恢復(fù)“時(shí)，該方法被調(diào)用。</p><p>　　Run():void</p><p>　　當(dāng)按下按鈕“執(zhí)行“時(shí)，該方法被調(diào)用。</p><p>　　Stopped():void</p><p>　　當(dāng)按下按鈕“暫?！皶r(shí)，該方法被調(diào)用。</p&g

100、t;<p><b>　　3.2.3建立類(lèi)圖</b></p><p>　　識(shí)別出系統(tǒng)中的類(lèi)后，還要識(shí)別出類(lèi)間的關(guān)系，然后就可以建立類(lèi)圖了。ListDialog、TreeDialog、HCDialog、SortDialog是DemonGUI的一部分，因此它們與類(lèi)DemonGUI之間是組合關(guān)系，同理，MainFrom與類(lèi)ListDialog、TreeDialog、HCDialog、S

101、ortDialog之間也是組合關(guān)系。sqList、linkList、Tree、HuffmanCode、TopoSort、Sort與類(lèi)MainFrom之間是依賴關(guān)系。類(lèi)OrderTree、ThreTree繼承了類(lèi)bitree類(lèi)間的關(guān)系如圖3.6所示。</p><p><b>　　3.3動(dòng)態(tài)行為模型</b></p><p>　　系統(tǒng)的動(dòng)態(tài)行為模型可以用交互作用圖、狀態(tài)圖和

102、活動(dòng)圖來(lái)描述。活動(dòng)圖強(qiáng)調(diào)了從活動(dòng)到活動(dòng)的控制流，而交互圖則強(qiáng)調(diào)從對(duì)象到對(duì)象的控制流，本人采用時(shí)序圖來(lái)描述為完成某個(gè)特定功能發(fā)生在系統(tǒng)對(duì)象之間的信息交換。</p><p>　　描述本系統(tǒng)用例場(chǎng)景的時(shí)序圖如下：</p><p><b>　　圖3.6系統(tǒng)類(lèi)圖</b></p><p>　　“演示順序表”的時(shí)序圖如圖3.7所示:</p>&

103、lt;p>　　圖3.7“演示順序表“的時(shí)序圖</p><p>　　由于演示鏈表的時(shí)序圖和演示順序表的時(shí)序圖相類(lèi)似，在此就不多畫(huà)了。演示鏈表的時(shí)序圖主要比演示順序表的時(shí)序圖多了一個(gè)創(chuàng)建部分。</p><p>　　“演示二叉樹(shù)遍歷“的時(shí)序圖，如圖3.8所示：</p><p>　　圖3.8“演示二叉樹(shù)遍歷“的時(shí)序圖</p><p>　　“演示

104、二叉樹(shù)線索化“的時(shí)序圖，如圖3.9所示：</p><p>　　圖3.9“演示二叉樹(shù)線索化“的時(shí)序圖</p><p>　　“演示赫夫曼樹(shù)“的時(shí)序圖，如圖3.10所示：</p><p>　　圖3.10“演示赫夫曼樹(shù)“的時(shí)序圖</p><p>　　“演示拓?fù)渑判颉暗臅r(shí)序圖，如圖3.11所示</p><p>　　圖3.11“演

105、示拓?fù)渑判颉暗臅r(shí)序圖</p><p>　　“演示內(nèi)部排序“的時(shí)序圖，如圖3.12所示</p><p>　　圖3.12“演示內(nèi)部排序“的時(shí)序圖</p><p><b>　　本章小結(jié)</b></p><p>　　本章節(jié)主要是進(jìn)一步對(duì)系統(tǒng)的功能性需求分析，將用戶的需求逐步轉(zhuǎn)化為代碼。從設(shè)計(jì)者的角度來(lái)設(shè)計(jì)系統(tǒng)，畫(huà)出了系統(tǒng)中的靜態(tài)

106、結(jié)構(gòu)模型和動(dòng)態(tài)行為模型。靜態(tài)結(jié)構(gòu)模型主要實(shí)現(xiàn)了定義系統(tǒng)對(duì)象類(lèi)、定義用戶界面類(lèi)和建立類(lèi)圖。動(dòng)態(tài)行為模型采用時(shí)序圖來(lái)實(shí)現(xiàn)。</p><p><b>　　系統(tǒng)實(shí)現(xiàn)</b></p><p>　　系統(tǒng)的核心部分是動(dòng)畫(huà)演示、變量跟蹤和源代碼同步演示的實(shí)現(xiàn)，由于每一個(gè)算法的演示都要求實(shí)現(xiàn)這部分，因此，在這我以演示鏈表的創(chuàng)建為例說(shuō)明該部分的實(shí)現(xiàn)。</p><p&g

107、t;<b>　　4.1多線程簡(jiǎn)介</b></p><p>　　首先介紹數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示的關(guān)鍵技術(shù)——c#的多線程技術(shù)。</p><p>　　4.1.1線程、多線程概念</p><p>　　線程(Thread)是線程控制(Thread Control)的簡(jiǎn)寫(xiě)，是程序中的一個(gè)執(zhí)行流。線程像進(jìn)程一樣是動(dòng)態(tài)的，也有一個(gè)從生成、生存到消亡的過(guò)程。但線

108、程是比進(jìn)程更小的執(zhí)行單位，有時(shí)稱為輕量級(jí)進(jìn)程(LWP——lightweight process) [1]。</p><p>　　單線程(Single Thread)是指程序只含有單個(gè)執(zhí)行流。單個(gè)執(zhí)行流是指一個(gè)程序只有一條從頭到尾的執(zhí)行路線，即在程序執(zhí)行期間的任一時(shí)刻，僅有一個(gè)執(zhí)行點(diǎn)[1]。</p><p>　　多線程(Muhithread)是指程序含有多個(gè)執(zhí)行流。多線程機(jī)制允許單個(gè)程序通過(guò)

109、建立多個(gè)并行執(zhí)行的線程來(lái)完成各自的任務(wù)。這些并行執(zhí)行的線程可以執(zhí)行相同的代碼，也可以執(zhí)行不同的代碼[1]。</p><p>　　4.1.2實(shí)現(xiàn)多線程的方法</p><p>　　在dotNET類(lèi)庫(kù)中，System.Threading命名空間下包含了各種線程組件、接口來(lái)幫助程序員使用c#編寫(xiě)多線程程序。在這個(gè)命名空間中最重要的就是Thread類(lèi)，它是c#多線程程序設(shè)計(jì)的基礎(chǔ)。Thread類(lèi)提供

110、了創(chuàng)建線程、控制線程的方法，它主要有以下幾種重要的成員：</p><p>　　啟動(dòng)線程：Start()</p><p>　　終止線程：Abort()</p><p>　　線程休眠：Sleep()</p><p>　　掛起線程：Suspend()</p><p>　　恢復(fù)線程：Resume()</p>&l

111、t;p>　　具體的線程設(shè)計(jì)如下[2]：</p><p>　　public class AlgorithmThread//開(kāi)始用戶自定義線程類(lèi)AlgorithmThread．</p><p>　　{//類(lèi)成員變量聲明處</p><p>　　public AlgorithmThread() </p><p><b>　　{//構(gòu)造

112、函數(shù)體</b></p><p>　　} //類(lèi)AlgorithmThread的構(gòu)造函數(shù)</p><p>　　public void Run(){//定義線程體，以實(shí)現(xiàn)自定義線程類(lèi)AlgorithmThread的功能</p><p>　　int i;　String str;</p><p>　　for(i=0;i<=10;i+

113、+)</p><p><b>　　{ </b></p><p>　　str ="Step number"+ i.ToString()+"executed"; </p><p>　　Thread.Sleep(500); /

114、/當(dāng)前線程休眠(暫停)500ms </p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　主程序中建立和啟動(dòng)線程： </p><p>　　public class m

115、ainForm</p><p><b>　　{ </b></p><p>　　public delegate void DelegateStep(int s); </p><p>　　public void startAlgorithmThread()</p><p><b>　　{ </b>&

116、lt;/p><p>　　m_algotithmThread=new Thread(new ThreadStart (this.ThreadFunction));</p><p><b>　　//創(chuàng)建線程實(shí)例 </b></p><p>　　m_algotithmThread.Start();//啟動(dòng)線程，即調(diào)用ThreadFunction線程函數(shù)

117、 </p><p><b>　　} </b></p><p>　　private void ThreadFunction()</p><p><b>　　{ </b></p><p><b>　　//線程函數(shù) </b></p>

118、<p>　　AlgorithmThread algorithmThread; </p><p>　　algorithmThread=new AlgorithmThread();</p><p>　　algorithmThread.run();//調(diào)用AlgorithmThread的run函數(shù)，執(zhí)行線程體 </p>

119、;<p><b>　　}</b></p><p><b>　　} </b></p><p>　　這樣就在主線程mainForm中建立并啟動(dòng)了用戶自定義線程m_algotithmThread。 </p><p><b>　　線程同步</b></p><p>　　若

120、一個(gè)對(duì)象同時(shí)被多個(gè)其他線程訪問(wèn)，則這多個(gè)線程之間在微觀上存在先后執(zhí)行順序的關(guān)聯(lián)關(guān)系，這就是線程同步。在C#里面用于實(shí)現(xiàn)線程同步的常用類(lèi)有如下幾類(lèi)：</p><p>　　Mutex類(lèi)，Monitor類(lèi)，lock方法。</p><p>　　Manual(Auto)ResetEvent類(lèi)。</p><p>　　ReaderWriterLock類(lèi)。</p>&

121、lt;p>　　c# Windows應(yīng)用程序中，在窗體上顯示線程中處理的信息，需要在一個(gè)線程中引用另一個(gè)線程中的窗體控件。常用辦法是使用委托(delegate)完成這個(gè)工作，即在不是創(chuàng)建控件的線程中直接創(chuàng)建一個(gè)委托實(shí)例，調(diào)用控件對(duì)象的Invoke方法，并傳入需要的參數(shù)，完成對(duì)其他線程中的控件的操作。</p><p>　　4.2動(dòng)態(tài)算法演示模板</p><p>　　數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)采