數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)

1、<p><b>　　河北農(nóng)業(yè)大學(xué)</b></p><p>　　本科畢業(yè)論文(設(shè)計(jì))</p><p>　　題目： 數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng) </p><p>　　學(xué) 院： 信息科學(xué)與技術(shù)學(xué)院 </p><p>　　專業(yè)班級(jí)： 軟件工程1001班 </p>

2、<p>　　學(xué) 號(hào)： 2010234030312 </p><p>　　學(xué)生姓名： 李丙志 </p><p>　　指導(dǎo)教師姓名： 常淑惠 </p><p>　　指導(dǎo)教師職稱： 副教授 </p><p><b>　　201

3、4年6月1日</b></p><p><b>　　摘要</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》不僅是大學(xué)計(jì)算機(jī)專業(yè)的核心課程之一,也是非計(jì)算機(jī)專業(yè)的主要選修課程之一。該課程理論性強(qiáng)又較為抽象,尤其是對(duì)算法描述的執(zhí)行過(guò)程的理解是難點(diǎn)和重點(diǎn)。利用可視化圖形效果來(lái)動(dòng)態(tài)演示算法的執(zhí)行過(guò)程,對(duì)學(xué)員深入理解教材內(nèi)容、掌握基本的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)算法的實(shí)現(xiàn)過(guò)程有很好的幫助

4、作用,同時(shí)該系統(tǒng)可用于各種不同層次的教學(xué)，便于課上教師的講解和課下學(xué)生的復(fù)習(xí)、自修。</p><p>　　本文簡(jiǎn)要介紹了數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)的項(xiàng)目開(kāi)發(fā)背景和意義，著重闡述了該系統(tǒng)開(kāi)發(fā)實(shí)現(xiàn)過(guò)程，從系統(tǒng)的需求分析、方案設(shè)計(jì)、模塊設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)等各個(gè)環(huán)節(jié)都進(jìn)行了詳盡的分析和描述。該系統(tǒng)采用匯編、C/C++等技術(shù)開(kāi)發(fā)，具有操作便捷、形象生動(dòng)等特點(diǎn)，對(duì)于深化對(duì)數(shù)據(jù)結(jié)構(gòu)算法的理解，提高計(jì)算機(jī)程序設(shè)計(jì)水平具

5、有很好的促進(jìn)作用，而且具有一定的實(shí)用價(jià)值。</p><p>　　關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)，算法演示，C++，圖形</p><p><b>　　Abstract</b></p><p>　　"Data structure" is not only one of the core courses in university comput

6、er professional, is also one of the main elective course for non computer majors. The course theory and abstract, especially the execution process of the algorithm described the understanding is the emphasis and difficul

7、ty in. The implementation process using visual effects to the algorithm dynamic demonstration, the realization process master the basic data structure and the corresponding algorithm are very helpful for stu</p>&

8、lt;p>　　This paper briefly introduces the project development background and significance of data structure algorithm demonstration system, emphatically elaborated the system development process, from the system needs

9、analysis, program design, module design, data structure design, detailed design and implementation of all aspects of a detailed analysis and description. The system uses the assembly, C/C++ technology, has convenient ope

10、ration, vivid image characteristics, to deepen the understanding of da</p><p>　　Keywords：Data structure, algorithm demo, C++,graphics</p><p><b>　　目錄</b></p><p><b>

11、　　1 緒論1</b></p><p>　　1.1 背景和意義1</p><p><b>　　1.2系統(tǒng)目標(biāo)1</b></p><p>　　1.3 可行性分析1</p><p>　　1.3.1. 經(jīng)濟(jì)可行性分析1</p><p>　　1.3.2. 技術(shù)可行性分析2</

12、p><p>　　1.3.3. 社會(huì)可行性分析2</p><p>　　2技術(shù)介紹及開(kāi)發(fā)環(huán)境2</p><p>　　2.1匯編技術(shù)簡(jiǎn)介2</p><p>　　2.2圖形學(xué)技術(shù)簡(jiǎn)介3</p><p>　　2.3 C/C++語(yǔ)言簡(jiǎn)介3</p><p><b>　　2.4開(kāi)發(fā)環(huán)境4<

13、;/b></p><p>　　2.4.1 Broland C++編譯器4</p><p>　　2.4.2 Editplus4</p><p>　　2.4.3 make工具4</p><p>　　2.4.4 操作系統(tǒng)4</p><p><b>　　3 系統(tǒng)分析4</b></p&

14、gt;<p>　　3.1 需求分析4</p><p>　　3.2 系統(tǒng)功能5</p><p>　　3.2.1系統(tǒng)功能描述5</p><p>　　3.2.2系統(tǒng)功能圖5</p><p><b>　　4 系統(tǒng)設(shè)計(jì)6</b></p><p>　　4.1圖形庫(kù)設(shè)計(jì)6</p&

15、gt;<p>　　4.1.1圖形庫(kù)需求分析6</p><p>　　4.1.2圖形庫(kù)設(shè)計(jì)6</p><p><b>　　4.2類圖設(shè)計(jì)7</b></p><p>　　4.3 UI界面設(shè)計(jì)8</p><p><b>　　5 系統(tǒng)實(shí)現(xiàn)9</b></p><p&g

16、t;　　5.1鏈表算法演示9</p><p>　　5.1.1 創(chuàng)建9</p><p>　　5.1.2遍歷13</p><p>　　5.1.3插入14</p><p>　　5.1.4刪除15</p><p>　　5.2二叉樹(shù)算法演示17</p><p>　　5.2.1 創(chuàng)建17<

17、;/p><p>　　5.2.2遍歷19</p><p><b>　　總結(jié)21</b></p><p><b>　　致謝22</b></p><p><b>　　參考文獻(xiàn)23</b></p><p><b>　　1 緒論</b>&

18、lt;/p><p><b>　　1.1 背景和意義</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)

19、據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。數(shù)據(jù)結(jié)構(gòu)課程的主要目的是介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論對(duì)它們實(shí)行的各種運(yùn)算的實(shí)現(xiàn)算法。很多算法實(shí)際上是對(duì)某種數(shù)據(jù)結(jié)構(gòu)施行的一種變換，研究算法也就是研究在實(shí)施變換過(guò)程中數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)性質(zhì)。</p&

20、gt;<p>　　數(shù)據(jù)結(jié)構(gòu)，作為計(jì)算機(jī)學(xué)科的基礎(chǔ)性專業(yè)課程，其在計(jì)算機(jī)科學(xué)中的及其重要，課程學(xué)習(xí)的好壞，直接關(guān)系到學(xué)員后期計(jì)算機(jī)水平的高低。而這門課程一直因?yàn)檫^(guò)于抽象，難以理解，而讓人望而止步。如果能夠把這門抽象的課程變得具體而生動(dòng)，必將提高學(xué)習(xí)人員興趣，增加其積極性和主動(dòng)性，也有利于人員的對(duì)此課程的學(xué)習(xí)。</p><p>　　基于這些目的，我開(kāi)發(fā)了這個(gè)數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)，數(shù)據(jù)結(jié)構(gòu)是我所做的系統(tǒng)的

21、主要理論基礎(chǔ)，我完成了線性表、堆棧、隊(duì)列、樹(shù)、圖幾個(gè)主要結(jié)構(gòu)，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程的時(shí)候，我了解了這些結(jié)構(gòu)的算法，當(dāng)時(shí)也做過(guò)一些相關(guān)的程序，在此基礎(chǔ)之上，我運(yùn)用BrolandC++開(kāi)發(fā)工具，把這些算法演示出來(lái)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)可以演示線性表、堆棧、隊(duì)列、樹(shù)、圖等幾個(gè)基礎(chǔ)結(jié)構(gòu)的算法，輔助一些算法說(shuō)明，讓使用者更好地掌握算法，在幫助中把演示的具體過(guò)程和操作做詳細(xì)的介紹。</p>

22、<p>　　該系統(tǒng)具有操作簡(jiǎn)單、形象生動(dòng)，能很好地改善人員對(duì)數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)理解，從很大程度上提高人員的學(xué)習(xí)質(zhì)量和效率。</p><p><b>　　1.2系統(tǒng)目標(biāo)</b></p><p>　　課題實(shí)現(xiàn)一個(gè)基于dos系統(tǒng)（windows的模擬dos）的數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)。系統(tǒng)主要要求模擬演示單鏈表、棧、隊(duì)列、二叉樹(shù)、圖、查找、排序等數(shù)據(jù)結(jié)構(gòu)中典型算法

23、的執(zhí)行過(guò)程。根據(jù)此要求每一個(gè)算法設(shè)計(jì)為一個(gè)模塊，每一模塊中都通過(guò)動(dòng)畫(huà)詳細(xì)演示了算法的執(zhí)行過(guò)程。</p><p><b>　　1.3 可行性分析</b></p><p>　　1.3.1. 經(jīng)濟(jì)可行性分析</p><p>　　主要是對(duì)項(xiàng)目的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)，一方面是支出的費(fèi)用，其中包括設(shè)備購(gòu)置費(fèi)，軟件開(kāi)發(fā)費(fèi)，管理和維護(hù)費(fèi)，人員工資和培訓(xùn)費(fèi)等。另一方

24、面是取得的收益中可以用錢來(lái)衡量的那部分（收益的另一部分難以用錢來(lái)表示）?；谄髽I(yè)的現(xiàn)有計(jì)算機(jī)及配套設(shè)備，部署系統(tǒng)，可以在教學(xué)中減少很大的工作量，所以從人力、物力、財(cái)力方面來(lái)說(shuō)都是可行的。</p><p>　　1.3.2. 技術(shù)可行性分析</p><p>　　技術(shù)上的可行性分析主要分析現(xiàn)有技術(shù)條件能否順利完成開(kāi)發(fā)工作，軟硬件配置能否滿足開(kāi)發(fā)者需要等，這一特點(diǎn)非常適合計(jì)算機(jī)的特點(diǎn)，發(fā)揮計(jì)算機(jī)的

25、數(shù)據(jù)處理速度快，準(zhǔn)確率高的優(yōu)勢(shì)，現(xiàn)代計(jì)算機(jī)硬件和軟件技術(shù)的飛速發(fā)展，為系統(tǒng)的建設(shè)提供了技術(shù)條件。由于對(duì)算法演示這一類的教學(xué)系統(tǒng)進(jìn)行開(kāi)發(fā)已有一定的時(shí)期，有很多成功的實(shí)例，技術(shù)基礎(chǔ)也已經(jīng)非常雄厚，因而技術(shù)上的準(zhǔn)備應(yīng)該不成問(wèn)題。</p><p>　　1.3.3. 社會(huì)可行性分析</p><p>　　社會(huì)可行性有時(shí)也稱為操作可行性，主要論證新系統(tǒng)在機(jī)構(gòu)開(kāi)發(fā)和運(yùn)行的可能性以及運(yùn)行后可能一起的對(duì)教學(xué)的

26、影響，即組織內(nèi)外是否具備接受和使用新系統(tǒng)的條件。在當(dāng)前信息技術(shù)飛速發(fā)展的大環(huán)境下，計(jì)算機(jī)技術(shù)和軟件技術(shù)的更新使人們完全有可能也有能力采用這樣先進(jìn)的技術(shù)。在某種意義上，信息與科技在現(xiàn)代化建設(shè)中顯現(xiàn)出越來(lái)越重要的地位。好的演示系統(tǒng)對(duì)教學(xué)效果有很大的促進(jìn)意義。</p><p>　　2技術(shù)介紹及開(kāi)發(fā)環(huán)境</p><p><b>　　2.1匯編技術(shù)簡(jiǎn)介</b></p>

27、;<p>　　為了克服機(jī)器語(yǔ)言的缺點(diǎn)，人們采用便于記憶、并能描述指令功能的符號(hào)來(lái)表示指令的操作碼。這些符號(hào)被稱為指令助記符。助記符一般是說(shuō)明指令功能的英語(yǔ)詞匯或者詞匯的縮寫(xiě)。同時(shí)也用符號(hào)表示操作數(shù)，如CPU的寄存器、存儲(chǔ)單元地址等。</p><p>　　由于匯編語(yǔ)言使用指令助記符和符號(hào)地址，所以它要比機(jī)器語(yǔ)言容易掌握得多。與高級(jí)語(yǔ)言相比較，匯編語(yǔ)言有如下特點(diǎn)：</p><p>

28、;　　匯編語(yǔ)言與機(jī)器關(guān)系密切</p><p>　　匯編語(yǔ)言與機(jī)器所帶飛CPU有著十分密切的關(guān)系。對(duì)于各種不同類型的CPU，要使用各種不同的匯編語(yǔ)言，此系統(tǒng)使用的是8086匯編。匯編語(yǔ)言可以直接操作硬件進(jìn)行工作。</p><p><b>　　匯編程序效率高</b></p><p>　　用匯編語(yǔ)言編寫(xiě)的源程序在匯編后所得的目標(biāo)程序效率高。這種目標(biāo)程

29、序的高效率反應(yīng)在時(shí)間和空間兩個(gè)方面：其一是運(yùn)行速度快；其二是目標(biāo)程序短。在采用相同算法的前提下，任何高級(jí)語(yǔ)言程序在這兩方面的效率都不如匯編程序，許多情況下更是遠(yuǎn)遠(yuǎn)不及。</p><p>　　匯編程序能獲得“時(shí)空”高效率的主要原因是：構(gòu)成匯編語(yǔ)言主體的匯編格式指令是機(jī)器指令的符號(hào)表示，每一條匯編格式指令都是所對(duì)應(yīng)的某條機(jī)器指令的“化身”;另一個(gè)重要原因是匯編程序能直接并充分利用機(jī)器硬件系統(tǒng)的許多特性。</p&

30、gt;<p><b>　　編寫(xiě)繁瑣、調(diào)試?yán)щy</b></p><p>　　程序員在利用匯編語(yǔ)言編程程序時(shí)，必須考慮包括寄存器、存儲(chǔ)單元和尋址方式在內(nèi)的幾乎所有細(xì)節(jié)問(wèn)題。例如：指令執(zhí)行對(duì)標(biāo)志的影響，堆棧設(shè)置的位置等。</p><p>　　調(diào)試匯編程序往往要比調(diào)試高級(jí)語(yǔ)言程序困難。匯編格式指令的功能有限和程序員要注意太多的細(xì)節(jié)問(wèn)題是造成這種困難的兩個(gè)客觀原因

31、；匯編語(yǔ)言提供給了程序員最大的“舞臺(tái)”而程序員往往為了追求“時(shí)空”上的高效而不顧程序的結(jié)構(gòu)，這是在成調(diào)試?yán)щy的主觀原因。</p><p>　　2.2圖形學(xué)技術(shù)簡(jiǎn)介</p><p>　　算機(jī)圖形學(xué)（Computer Graphics，簡(jiǎn)稱CG），狹義上是一種研究基于物理定律、經(jīng)驗(yàn)方法以及認(rèn)知原理，使用各種數(shù)學(xué)算法處理二維或三維圖形數(shù)據(jù)，生成可在計(jì)算機(jī)等顯示設(shè)備上顯示的可視化數(shù)據(jù)的科學(xué)。它是計(jì)

32、算機(jī)科學(xué)的一個(gè)分支領(lǐng)域與應(yīng)用方向。廣義上來(lái)看，計(jì)算機(jī)圖形學(xué)不僅包含了從三維圖形建模、繪制，到生成動(dòng)畫(huà)的過(guò)程，同時(shí)也包含了對(duì)二維向量圖形以及圖像視頻融合處理的研究。</p><p>　　計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容非常廣泛，如圖形硬件、圖形標(biāo)準(zhǔn)、圖形交互技術(shù)、光柵圖形生成算法、曲線曲面造型、實(shí)體造型、真實(shí)感圖形計(jì)算與顯示算法、非真實(shí)感繪制，以及科學(xué)計(jì)算可視化、計(jì)算機(jī)動(dòng)畫(huà)、自然景物仿真、虛擬現(xiàn)實(shí)等。簡(jiǎn)單地說(shuō)，計(jì)算機(jī)圖形學(xué)的

33、主要研究?jī)?nèi)容就是研究如何在計(jì)算機(jī)中表示圖形、以及利用計(jì)算機(jī)進(jìn)行圖形的計(jì)算、處理和顯示的相關(guān)原理與算法。圖形通常由點(diǎn)、線、面、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。從處理技術(shù)上來(lái)看，圖形主要分為兩類，一類是基于線條信息表示的，如工程圖、等高線地圖、曲面的線框圖等，另一類是明暗圖，也就是通常所說(shuō)的真實(shí)感圖形。</p><p>　　計(jì)算機(jī)圖形學(xué)一個(gè)主要的目的就是要利用計(jì)算機(jī)產(chǎn)生令人賞心悅目的真實(shí)感圖形。

34、為此，必須建立圖形所描述的場(chǎng)景的幾何表示，再用某種光照模型，計(jì)算在假想的光源、紋理、材質(zhì)屬性下的光照明效果。所以計(jì)算機(jī)圖形學(xué)與另一門學(xué)科計(jì)算機(jī)輔助幾何設(shè)計(jì)有著密切的關(guān)系。事實(shí)上，圖形學(xué)也把可以表示幾何場(chǎng)景的曲線曲面造型技術(shù)和實(shí)體造型技術(shù)作為其主要的研究?jī)?nèi)容。同時(shí)，真實(shí)感圖形計(jì)算的結(jié)果是以數(shù)字元元圖像的方式提供的，計(jì)算機(jī)圖形學(xué)也就和圖像處理有著密切的關(guān)系。</p><p>　　2.3 C/C++語(yǔ)言簡(jiǎn)介</p

35、><p>　　C語(yǔ)言是當(dāng)今最流行的程序設(shè)計(jì)語(yǔ)言之一，它的功能豐富、表達(dá)力強(qiáng)、使用靈活方便、應(yīng)用面廣、目標(biāo)程序高、可植入性好，既有高級(jí)語(yǔ)言的特點(diǎn)，又有低級(jí)語(yǔ)言的許多特點(diǎn)，適合作為系統(tǒng)描述語(yǔ)言，既可以用來(lái)編寫(xiě)系統(tǒng)軟件，也可以用來(lái)編寫(xiě)應(yīng)用軟件。C語(yǔ)言誕生后，許多原來(lái)用匯編語(yǔ)言編寫(xiě)的軟件，現(xiàn)在都可以用C語(yǔ)言編寫(xiě)了（如UNIX操作系統(tǒng)），而學(xué)習(xí)和適用C語(yǔ)言要比學(xué)習(xí)和適用匯編語(yǔ)言容易得多。</p><p>

36、;　　C語(yǔ)言是一種結(jié)構(gòu)化語(yǔ)言。它層次清晰，便于按模塊化方式組織程序，易于調(diào)試和維護(hù)。C語(yǔ)言的表現(xiàn)能力和處理能力極強(qiáng)。它不僅具有豐富的運(yùn)算符和數(shù)據(jù)類型，便于實(shí)現(xiàn)各類復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。它還可以直接訪問(wèn)內(nèi)存的物理位元址，進(jìn)行位(bit)一級(jí)的操作。由于C語(yǔ)言實(shí)現(xiàn)了對(duì)硬件的編程操作，因此C語(yǔ)言集高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的功能于一體。既可用于系統(tǒng)軟件的開(kāi)發(fā)，也適合于應(yīng)用軟件的開(kāi)發(fā)</p><p>　　在C的基礎(chǔ)上，一九八三年又由貝

37、爾實(shí)驗(yàn)室的Bjarne Strou-strup推出了C++。C++進(jìn)一步擴(kuò)充和完善了C語(yǔ)言，成為一種面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言。C++目前流行的編譯器最新版本是BorlandC++4.5,SymantecC++6.1,和MicrosoftVisualC++2012。C++提出了一些更為深入的概念，它所支持的這些面向?qū)ο蟮母拍钊菀讓?wèn)題空間直接地映像到程序空間，為程序員提供了一種與傳統(tǒng)結(jié)構(gòu)程序設(shè)計(jì)不同的思維方式和編程方法。因而也增加了整個(gè)語(yǔ)言

38、的復(fù)雜性，掌握起來(lái)有一定難度。</p><p>　　但是，C是C++的基礎(chǔ)，C++語(yǔ)言和C語(yǔ)言在很多方面是兼容的。因此，掌握了C語(yǔ)言，再進(jìn)一步學(xué)習(xí)C++就能以一種熟悉的語(yǔ)法來(lái)學(xué)習(xí)面向?qū)ο蟮恼Z(yǔ)言，從而達(dá)到事半功倍的目的。</p><p><b>　　2.4開(kāi)發(fā)環(huán)境</b></p><p>　　此次的開(kāi)發(fā)并未使用一套完整的IDE開(kāi)發(fā)環(huán)境，通過(guò)一些工

39、具的拼合組成了此系統(tǒng)的開(kāi)發(fā)環(huán)境</p><p>　　2.4.1 Broland C++編譯器</p><p>　　Broland C++，一個(gè)當(dāng)年在dos平臺(tái)叱咤風(fēng)云的編譯器，具有高速的編譯，連接和執(zhí)行速度，但其自帶的集成開(kāi)發(fā)環(huán)境不是太好用</p><p>　　2.4.2 Editplus</p><p>　　EditPlus（文字編輯器）是

40、一套功能強(qiáng)大，可取代記事本的文字編輯器，擁有無(wú)限制的撤銷與重做、英文拼字檢查、自動(dòng)換行、列數(shù)標(biāo)記、搜尋取代、同時(shí)編輯多文件、全屏幕瀏覽功能</p><p>　　2.4.3 make工具</p><p>　　當(dāng)源文件很多時(shí)，我不想在修改了一個(gè)檔后，還要重新編譯所有的源文件，這是make這個(gè)小工具可以幫到我。這個(gè)檔決定了源文件之間的依賴關(guān)系。而且決定了源文件什么時(shí)候該編譯什么時(shí)候不應(yīng)該編譯。&

41、lt;/p><p>　　2.4.4 操作系統(tǒng)</p><p>　　演示系統(tǒng)運(yùn)行于dos5.0及其以上的兼容系統(tǒng)中</p><p><b>　　3 系統(tǒng)分析</b></p><p><b>　　3.1 需求分析</b></p><p>　　做為一個(gè)數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)，首先我確定要演示

42、的內(nèi)容，在本系統(tǒng)中，我對(duì)線性表、堆棧和隊(duì)列、樹(shù)、圖幾個(gè)主要數(shù)據(jù)結(jié)構(gòu)做了講解；接著，對(duì)這幾種算法的說(shuō)明也是必不可少的，這樣配合演示，可以達(dá)到更好地效果；最后，作為我設(shè)計(jì)的演示過(guò)程，使用者對(duì)操作不是太了解，我有必要做個(gè)詳細(xì)的操作過(guò)程，讓使用者更好地使用系統(tǒng)。</p><p><b>　　3.2 系統(tǒng)功能</b></p><p>　　系統(tǒng)由數(shù)據(jù)結(jié)構(gòu)、操作、幫助、程序四個(gè)部分

43、組成?，F(xiàn)分述如下：</p><p>　　數(shù)據(jù)結(jié)構(gòu)由線性表、堆棧和隊(duì)列、樹(shù)、圖、查找、排序7個(gè)部分組成，分別對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)的各個(gè)部分。線性表又分為鏈表概念、鏈表模型、鏈表操作、雙向鏈表四個(gè)部分，堆棧和隊(duì)列分為基本堆棧、基本隊(duì)列、循環(huán)隊(duì)列三個(gè)部分，樹(shù)分為數(shù)據(jù)二叉樹(shù)、結(jié)構(gòu)二叉樹(shù)、類二叉樹(shù)，圖分為圖表示、圖搜索、最短路徑。</p><p>　　操作由線性表說(shuō)明、堆棧說(shuō)明、隊(duì)列說(shuō)明、樹(shù)說(shuō)明、圖說(shuō)明組成

44、，對(duì)各數(shù)據(jù)結(jié)構(gòu)的算法說(shuō)明。</p><p>　　幫助由關(guān)于和幫助組成，是本系統(tǒng)的一些說(shuō)明和對(duì)演示過(guò)程的操作詳細(xì)說(shuō)明。</p><p>　　程序部分由主接口和退出組成，完成系統(tǒng)的起始和終止。</p><p>　　3.2.1系統(tǒng)功能描述</p><p>　　此系統(tǒng)需要完成功能主要有：</p><p>　　鏈表演算法演示，包

45、括創(chuàng)建、插入、刪除、查找，遍歷。</p><p>　　棧算法演示，包括創(chuàng)建，出棧，入棧。</p><p>　　●隊(duì)列算法演示，包括創(chuàng)建、入隊(duì)、出隊(duì)。</p><p>　　●二叉樹(shù)算法演示，包括創(chuàng)建，遍歷，線索化，查找，刪除，插入。</p><p>　　●圖算法演示，包括創(chuàng)建、增加、刪除、遍歷。</p><p>　　●查

46、找和排序，包括基本的排序和查找算法。</p><p>　　3.2.2系統(tǒng)功能圖</p><p><b>　　圖3-1系統(tǒng)功能圖</b></p><p><b>　　4 系統(tǒng)設(shè)計(jì)</b></p><p><b>　　4.1圖形庫(kù)設(shè)計(jì)</b></p><p>

47、;　　4.1.1圖形庫(kù)需求分析</p><p>　　圖形庫(kù)支持基本繪圖、多種格式圖形顯示、鼠標(biāo)操作、時(shí)鐘、音頻播放、多種字體的漢字及英文顯示等等特性；可以工作于高分辨率下（比如800X600、1024X768甚至1280X1024）；而且，它支持最高24位的各種色深！并擁有不錯(cuò)的處理速度。它主要擁有以下特性：</p><p>　　支持320X200，640X400，640X480，800X

48、600，1024X768，1280X1024等各種標(biāo)準(zhǔn)分辨率，以及各種諸如320X240，320X400，512X512等ModeX分辨率；</p><p>　　全面支持8位256色，15位32768色，16位即65536色三種色深模式，</p><p>　　較為齊全的基本的繪圖函數(shù)，讓你輕松繪制象點(diǎn)、線、方、圓等各種簡(jiǎn)單的圖形；</p><p>　　支持多種格式圖

49、形的顯示，在這一版里，支持BMP、ICO和CUR的顯示。</p><p>　　支持鼠標(biāo)操作，并集成一套功能強(qiáng)大高級(jí)鼠標(biāo)控制函數(shù)，譬如能夠檢測(cè)雙擊，還支持使用ICO\CUR文件作為鼠標(biāo)游標(biāo)；</p><p>　　擁有一套高級(jí)鍵盤處理函數(shù)，用戶可以通過(guò)安裝鍵盤中斷來(lái)使用它們；</p><p><b>　　集成時(shí)鐘控制模塊；</b></p>

50、;<p>　　可以顯示多種字體的英文和中文，并支持一些常用的文字特效；</p><p>　　支持矩形輸出裁剪，讓動(dòng)畫(huà)等各種顯示特效均成為可能；</p><p>　　支持類似Borlandgraphics.h中庫(kù)函數(shù)的作圖模式，譬如XOR異或模式；</p><p>　　相容Borlandgraphics.h中的大部分函數(shù)以方便將原來(lái)使用graphics.

51、h的程序移植過(guò)來(lái)；</p><p>　　強(qiáng)大的錯(cuò)誤處理系統(tǒng)，能根據(jù)用戶的設(shè)置決定輸出錯(cuò)誤信息的方式，譬如直接在屏幕上顯示還是輸出到錯(cuò)誤日志，或者僅僅只用喇叭報(bào)一下警；</p><p>　　強(qiáng)大快速的調(diào)色板操作函數(shù)，可以實(shí)現(xiàn)淡出淡入特效，還能夠使用8位色彩分量長(zhǎng)的調(diào)色板，還可以實(shí)現(xiàn)64級(jí)調(diào)色板之間的過(guò)渡；</p><p>　　提供了多圖形緩沖頁(yè)架構(gòu)，并支持高效率的硬件

52、換頁(yè)機(jī)制和滾屏機(jī)制；</p><p>　　支持諸如翻折，灰度，半透明，模糊，反色，顏色加強(qiáng)等多種圖形顯示特效；</p><p>　　全面支持Borland全系列C\C++編譯器。</p><p>　　4.1.2圖形庫(kù)設(shè)計(jì)</p><p>　　圖形庫(kù)這一部分代碼可以用匯編好C語(yǔ)言進(jìn)行編寫(xiě)，主要模塊如下：</p><p>

53、<b>　　圖形模式</b></p><p>　　通過(guò)調(diào)用vbe提供的dos中斷，我可以修改屏幕的分辨率為300*200、640*480、1024*768等模式。例如調(diào)用int10h的0X117子功能可以設(shè)置屏幕為1024*76824bit色模式下。</p><p><b>　　基本繪圖函數(shù)</b></p><p>　　基

54、本繪圖，都是可以通過(guò)點(diǎn)來(lái)的不同排列來(lái)實(shí)現(xiàn)。故畫(huà)點(diǎn)函數(shù)的實(shí)現(xiàn)需要重點(diǎn)優(yōu)化，畫(huà)線使用Bresenham算法。</p><p><b>　　位圖顯示</b></p><p>　　通過(guò)對(duì)位圖檔格式的分析，獲取其分辨率、色深、寬度和長(zhǎng)度等基本信息，然后將顯卡切換到對(duì)應(yīng)的顯示模式，讀取位圖像素點(diǎn)數(shù)據(jù)顯示到屏幕上。</p><p><b>　　文字

55、輸出</b></p><p>　　從字庫(kù)檔中中查找對(duì)應(yīng)的字模，獲取其點(diǎn)陣信息，通過(guò)畫(huà)點(diǎn)函數(shù)將其信息顯示到屏幕上。</p><p><b>　　鼠標(biāo)例程</b></p><p>　　設(shè)置8253中斷控制器，定時(shí)執(zhí)行重繪鼠標(biāo)圖案例程。當(dāng)鼠標(biāo)點(diǎn)擊時(shí)會(huì)觸發(fā)對(duì)應(yīng)的中斷例程，可以重寫(xiě)中斷例程實(shí)現(xiàn)類window的消息機(jī)制。</p>

56、<p><b>　　鍵盤例程</b></p><p>　　通過(guò)重寫(xiě)int9等鍵盤中斷例程，實(shí)現(xiàn)一些自己想要的功能。</p><p><b>　　4.2類圖設(shè)計(jì)</b></p><p>　　在鏈表、棧、隊(duì)列、二叉樹(shù)、圖的算法操作中都會(huì)有相應(yīng)結(jié)構(gòu)的節(jié)點(diǎn)。這些節(jié)點(diǎn)在結(jié)構(gòu)上有很多的相似性，故而可以把他們抽象到Node類，

57、然后根據(jù)不同的結(jié)構(gòu)泛華出具體的節(jié)點(diǎn)類型。另外這些結(jié)構(gòu)還不具有顯示的功能，因此它們都需要實(shí)現(xiàn)一個(gè)IShow顯示接口。具體類圖如圖4-1所示。</p><p><b>　　圖4-1類圖結(jié)構(gòu)</b></p><p>　　4.3 UI界面設(shè)計(jì)</p><p>　　界面主題為黑板風(fēng)格，素材由常見(jiàn)的粉筆、板擦、黑板等組成，見(jiàn)：圖4-2 —— 圖4-5<

58、;/p><p>　　圖4-2粉筆圖4-3板擦圖4-4黑板圖4-5彩筆</p><p>　　這些素材來(lái)自日常教學(xué)，符合教學(xué)場(chǎng)景，同時(shí)也會(huì)給人一種親切感。</p><p>　　C語(yǔ)言是當(dāng)今最流行的程序設(shè)計(jì)語(yǔ)言之一，它的功能豐富、表達(dá)力強(qiáng)、使用靈活方便、應(yīng)用面廣、目標(biāo)程序高、可植入性好，既有高級(jí)語(yǔ)言的特點(diǎn)，又有低級(jí)語(yǔ)言的許多特點(diǎn)，適合作為系統(tǒng)描述語(yǔ)言，

59、既可以用來(lái)編寫(xiě)系統(tǒng)軟件，也可以用來(lái)編寫(xiě)應(yīng)用軟件。C語(yǔ)言誕生后，許多原來(lái)用匯編語(yǔ)言編寫(xiě)的軟件，現(xiàn)在都可以用C語(yǔ)言編寫(xiě)了（如UNIX操作系統(tǒng)），而學(xué)習(xí)和適用C語(yǔ)言要比學(xué)習(xí)和適用匯編語(yǔ)言容易得多。</p><p>　　C語(yǔ)言是一種結(jié)構(gòu)化語(yǔ)言。它層次清晰，便于按模塊化方式組織程序，易于調(diào)試和維護(hù)。C語(yǔ)言的表現(xiàn)能力和處理能力極強(qiáng)。它不僅具有豐富的運(yùn)算符和數(shù)據(jù)類型，便于實(shí)現(xiàn)各類復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。它還可以直接訪問(wèn)內(nèi)存的物理位元址

60、，進(jìn)行位(bit)一級(jí)的操作。由于C語(yǔ)言實(shí)現(xiàn)了對(duì)硬件的編程操作，因此C語(yǔ)言集高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的功能于一體。既可用于系統(tǒng)軟件的開(kāi)發(fā)，也適合于應(yīng)用軟件的開(kāi)發(fā)</p><p>　　在C的基礎(chǔ)上，一九八三年又由貝爾實(shí)驗(yàn)室的BjarneStrou-strup推出了C++。C++進(jìn)一步擴(kuò)充和完善了C語(yǔ)言，成為一種面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言。C++目前流行的編譯器最新版本是BorlandC++4.5,SymantecC++6.1

61、,和MicrosoftVisualC++2012。C++提出了一些更為深入的概念，它所支持的這些面向?qū)ο蟮母拍钊菀讓?wèn)題空間直接地映像到程序空間，為程序員提供了一種與傳統(tǒng)結(jié)構(gòu)程序設(shè)計(jì)不同的思維方式和編程方法。因而也增加了整個(gè)語(yǔ)言的復(fù)雜性，掌握起來(lái)有一定難度。</p><p>　　但是，C是C++的基礎(chǔ)，C++語(yǔ)言和C語(yǔ)言在很多方面是兼容的。因此，掌握了C語(yǔ)言，再進(jìn)一步學(xué)習(xí)C++就能以一種熟悉的語(yǔ)法來(lái)學(xué)習(xí)面向?qū)ο蟮?/p>

62、語(yǔ)言，從而達(dá)到事半功倍的目的。</p><p><b>　　圖4-6主頁(yè)</b></p><p>　　圖4-6是進(jìn)入軟件后的主頁(yè)，主頁(yè)上有4個(gè)熱點(diǎn)，當(dāng)鼠標(biāo)進(jìn)入熱點(diǎn)后會(huì)光標(biāo)圖案會(huì)變成一個(gè)“手指”，整個(gè)界面是由綠色和棕色構(gòu)成。</p><p><b>　　圖4-7功能選擇頁(yè)</b></p><p>　　

63、在這個(gè)界面上有“鏈表”、“棧”、“隊(duì)列”、“二叉樹(shù)”、“圖”、“排列”、“查找”7個(gè)熱區(qū)，這里是系統(tǒng)主要的功能入口，每個(gè)選項(xiàng)才用標(biāo)簽方式展示，就想教室里的一張張表單。</p><p>　　由于頁(yè)面較多，不在一一介紹，詳細(xì)內(nèi)容見(jiàn)軟件運(yùn)行效果圖。</p><p><b>　　5 系統(tǒng)實(shí)現(xiàn)</b></p><p>　　本系統(tǒng)包括：鏈表、棧、隊(duì)列、二叉

64、樹(shù)、圖、查找、排序7個(gè)功能模塊。由于時(shí)間倉(cāng)促這些功能并未全部完成，下面以鏈表和二叉樹(shù)為例說(shuō)明一下功能的實(shí)現(xiàn)。</p><p><b>　　5.1鏈表算法演示</b></p><p><b>　　5.1.1 創(chuàng)建</b></p><p>　　點(diǎn)擊創(chuàng)建后，會(huì)出現(xiàn)一個(gè)輸入框，提示用戶輸入要?jiǎng)?chuàng)建的節(jié)點(diǎn)內(nèi)容。此輸入框的實(shí)現(xiàn)是基于基礎(chǔ)

65、圖形庫(kù)的。在提示框顯示前需要保存當(dāng)前區(qū)域，以便提示框消失時(shí)恢復(fù)以前的內(nèi)容。</p><p>　　創(chuàng)建過(guò)程：根據(jù)用戶輸入的內(nèi)容，向帶頭結(jié)點(diǎn)的鏈表中依次追加節(jié)點(diǎn)。</p><p><b>　　圖4-8輸入框</b></p><p>　　輸入框的實(shí)現(xiàn)代碼如下：</p><p>　　char *GetInput(char *st

66、rTitle, char *strContent)</p><p><b>　　{</b></p><p>　　int charCount = 0;//行內(nèi)字符數(shù)</p><p>　　int line = 0;//行數(shù)</p><p>　　int a = 0;</p><p>　　int iSiz

67、e = 16;</p><p>　　char *in = (char *)malloc(128);</p><p>　　char ch[2] = {'\0'};</p><p>　　union REGS regs;</p><p>　　int height = 320;</p><p>　　int wi

68、dth = 480;</p><p>　　int col = (1024 - width) / 2;</p><p>　　int row = (768 - height) / 2;</p><p>　　int border = 20;</p><p>　　int title = 40;</p><p>　　int in

69、Col = col + border + 110;</p><p>　　int inRow = row + title + 80;</p><p>　　BITMAP *image;</p><p>　　image = get_image(col,row,col+width,row+height);/*獲取指定屏幕內(nèi)容*/</p><p>　　

70、setcolor(makecol(200,250, 200));</p><p>　　bar(col, row, col + width, row + height);/*外邊界*/</p><p>　　setcolor(makecol(175, 250, 240));</p><p>　　bar(col + border, row + border + title

71、, col + width - border,</p><p>　　row + height - border);/*內(nèi)邊界*/</p><p>　　set_cn_font(12,"Font\\Hzk12");</p><p>　　set_text_blank(3);</p><p>　　string_out(strTit

72、le,col+35,row+15);//標(biāo)題</p><p>　　string_out(strContent,col+border+((width - strlen(strContent)*10) /2),</p><p>　　row+title+height/3+100);//內(nèi)容</p><p>　　set_text_color(makecol(255, 0,

73、0));</p><p>　　cur_asc_rom(&iSize);</p><p>　　setcolor(makecol(255, 255, 255));</p><p>　　bar(inCol-5,inRow-4,inCol+240,inRow+30);</p><p>　　regs.h.ah = 0x0c;</p>

74、<p>　　regs.h.al = 7;</p><p>　　ch[0] = intdos(&regs,&regs);/*先清除緩沖區(qū)，再返回新進(jìn)入的一個(gè)字符*/</p><p>　　save_screen("box.bmp");</p><p>　　while(ch[0] != 13 && ch[0

75、] != 27)/*13代表回車*/</p><p><b>　　{</b></p><p>　　if(charCount >= 23)</p><p><b>　　{</b></p><p><b>　　line ++;</b></p><p>

76、　　inCol -= 230;</p><p>　　inRow+=30;</p><p>　　if(line >= 3)</p><p><b>　　break;</b></p><p>　　setcolor(makecol(255, 255, 255));</p><p>　　bar(in

77、Col-5,inRow-4,inCol+240,inRow+30);</p><p>　　charCount = 0;</p><p><b>　　}</b></p><p>　　if(ch[0] == '\b'&& a>0)</p><p><b>　　{</b&g

78、t;</p><p>　　inCol-=10;</p><p>　　setcolor(8);</p><p>　　ch[0] = 219;</p><p>　　set_text_color(makecol(255,255,255));</p><p>　　textout(ch,inCol,inRow);</p&g

79、t;<p><b>　　a --;</b></p><p>　　charCount --;</p><p><b>　　}</b></p><p>　　else if(ch[0] == ' ')</p><p><b>　　{</b></p&

80、gt;<p>　　charCount ++;</p><p>　　inCol+=10;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　in[

81、a++] = ch[0];</p><p>　　charCount ++;</p><p>　　set_text_color(makecol(255,0,0));</p><p>　　outtextxy(inCol,inRow+5,ch);</p><p>　　inCol+=10;</p><p><b>　

82、　}</b></p><p>　　ch[0] = getch();</p><p><b>　　}</b></p><p>　　if (ch[0] == 13)</p><p><b>　　{</b></p><p>　　in[a] = 0;</p>

83、<p><b>　　}</b></p><p>　　else if(ch[0] == 27)</p><p><b>　　{</b></p><p><b>　　free(in);</b></p><p>　　in = NULL;</p><p&

84、gt;<b>　　}</b></p><p>　　if (image)</p><p><b>　　{</b></p><p><b>　　vsync();</b></p><p>　　scare_mouse();</p><p>　　put_image

85、(image,col-1,row-1);</p><p>　　unscare_mouse();</p><p>　　destroy_bitmap(image);/*釋放內(nèi)存*/</p><p><b>　　}</b></p><p>　　return in;</p><p><b>　　

86、}</b></p><p><b>　　5.1.2遍歷</b></p><p>　　遍歷時(shí)，會(huì)從頭結(jié)點(diǎn)開(kāi)始。遍歷到一個(gè)節(jié)點(diǎn)時(shí)所做的操作是把這個(gè)節(jié)點(diǎn)中的字符由紅色變成綠色，</p><p><b>　　圖4-9遍歷</b></p><p>　　延時(shí)一段時(shí)間后在變回紅色。具體實(shí)現(xiàn)的效果如圖4

87、-9所示。</p><p><b>　　主要代碼如下：</b></p><p>　　while (pNode)</p><p><b>　　{</b></p><p>　　pNode->Show(pos);</p><p>　　if (pNode == head) &l

88、t;/p><p><b>　　{</b></p><p>　　col = pNode->GetPosition().col + RCOL;</p><p>　　row = pNode->GetPosition().row + RROW;</p><p><b>　　}</b></p&g

89、t;<p><b>　　else</b></p><p><b>　　{</b></p><p>　　col = pNode->GetPosition().col + RCOL;</p><p>　　row = pNode->GetPosition().row + RROW;</p>

90、<p><b>　　}</b></p><p>　　pNode = pNode->GetNext();</p><p><b>　　}</b></p><p><b>　　5.1.3插入</b></p><p>　　插入時(shí)也會(huì)有一個(gè)輸入框顯示出來(lái)，用戶輸入要?jiǎng)h

91、除的代碼后。先通過(guò)查找函數(shù)找到節(jié)點(diǎn)位置，然后從鏈表中移除節(jié)點(diǎn)，如果查找失敗則報(bào)錯(cuò)刪除失敗。</p><p><b>　　圖4-10錯(cuò)誤提示</b></p><p>　　bool List::Insert(unsigned uNum, const Data chEle, bool bFlag)</p><p><b>　　{</b

92、></p><p>　　if (uNum < length)</p><p><b>　　{</b></p><p>　　if (bFlag)//true，在uNum的前面插入</p><p><b>　　{</b></p><p>　　if (InnerIns

93、ert((*this)[uNum - 1], chEle))</p><p><b>　　{</b></p><p>　　return true;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b

94、>　　else</b></p><p><b>　　{</b></p><p>　　ListNode* qNode = ((*this)[uNum - 1]);</p><p>　　ListNode* pNode = new ListNode(chEle);</p><p>　　if (pNode &a

95、mp;& qNode)</p><p><b>　　{</b></p><p>　　ListNode* pTemp = qNode->GetNext();</p><p>　　pNode->SetNext(pTemp);</p><p>　　qNode->SetNext(pNode);</

96、p><p><b>　　length++;</b></p><p>　　return true;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

97、<p>　　else if (uNum == length)</p><p><b>　　{</b></p><p>　　if (bFlag)//true，在uNum的前面插入</p><p><b>　　{</b></p><p>　　if (InnerInsert((*this)

98、[uNum - 1], chEle))</p><p><b>　　{</b></p><p>　　return true;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else&

99、lt;/b></p><p><b>　　{</b></p><p>　　if (Append(chEle))</p><p><b>　　{</b></p><p>　　return true;</p><p><b>　　}</b></p

100、><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return false;</p><p><b>　　}</b></p><p><b>　　5.1.4刪除</b></p>

101、<p>　　刪除時(shí)，需要先調(diào)用查找函數(shù)，找到指定的節(jié)點(diǎn)后就可以刪除了。如果查找失敗就報(bào)“刪除失敗”的錯(cuò)誤。</p><p>　　bool List::Delete(unsigned int index)</p><p><b>　　{</b></p><p>　　if (index < length && ind

102、ex != 0)</p><p><b>　　{</b></p><p>　　ListNode* pNode = (*this)[index - 1];//需要?jiǎng)h除的節(jié)點(diǎn)</p><p>　　ListNode* qNode = pNode->GetNext();//實(shí)際刪掉的節(jié)點(diǎn)</p><p>　　pNod

103、e->SetNext(qNode->GetNext());//從鏈條中去掉qNode</p><p>　　pNode->SetData(qNode->GetData());//復(fù)制數(shù)據(jù)</p><p>　　if (qNode == tail)//刪除倒數(shù)第二個(gè)的時(shí)候需要加一步判斷</p><p><b>　　{<

104、/b></p><p>　　tail = pNode;</p><p><b>　　}</b></p><p>　　delete qNode;</p><p>　　length --;</p><p>　　return true;</p><p><b>　

105、　}</b></p><p>　　else if (index == length)</p><p><b>　　{</b></p><p>　　ListNode* p = head->GetNext();</p><p>　　while (p && p->GetNext() !=

106、 tail)</p><p><b>　　{</b></p><p>　　p = p->GetNext();</p><p><b>　　}</b></p><p>　　p->SetNext(NULL);</p><p>　　delete tail;</p&

107、gt;<p><b>　　tail = p;</b></p><p><b>　　length--;</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　return false;</p>

108、<p><b>　　}</b></p><p><b>　　圖4-11查找</b></p><p>　　5.2二叉樹(shù)算法演示</p><p>　　二叉樹(shù)的插入、刪除操作原理基本相同：先通過(guò)查找函數(shù)找到父節(jié)點(diǎn)，然后在操作父節(jié)點(diǎn)進(jìn)行刪除或插入。查找的方式是借助遍歷進(jìn)行字符比較。故比較重要的是創(chuàng)建和遍歷。</p

109、><p><b>　　5.2.1 創(chuàng)建</b></p><p>　　從用戶獲取輸入后，先序遞歸創(chuàng)建二叉樹(shù)。</p><p>　　bool BTree::InitBTree(BTreeNode** root, const Data* str, int row, int col,</p><p>　　int ColWidth,

110、int height)</p><p><b>　　{</b></p><p>　　/*static int num = 0;用于記錄當(dāng)前要操作的數(shù)據(jù)的下標(biāo)*/</p><p>　　if (!str[num])/**/</p><p><b>　　{</b></p><p>

111、　　//MessageBox("數(shù)據(jù)輸入有誤，初始化失敗",0);</p><p>　　return false;</p><p><b>　　}</b></p><p>　　if (str[num] == '.')</p><p><b>　　{</b><

112、/p><p>　　*root = NULL;</p><p><b>　　num++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p&g

113、t;<p>　　if (height >= 6)</p><p><b>　　{</b></p><p>　　//MessageBox("樹(shù)高超過(guò)了５，請(qǐng)重新輸入．",0);</p><p>　　return false;</p><p><b>　　}</b>

114、;</p><p>　　*root = new BTreeNode(str[num], row, col, ColWidth, height);</p><p>　　if (!(*root))</p><p><b>　　{</b></p><p>　　//MessageBox("堆棧溢出，初始化失敗"

115、;,0);</p><p>　　return false;</p><p><b>　　}</b></p><p><b>　　num++;</b></p><p>　　if (!InitBTree(&((*root)->LeftChild), str, row + ROWH, col

116、 - ColWidth,</p><p>　　ColWidth / 2, height + 1))</p><p>　　return false;</p><p>　　if (!InitBTree(&((*root)->RightChild), str, row + ROWH,</p><p>　　col + ColWidth,

117、 ColWidth / 2, height + 1))</p><p>　　return false;</p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　圖4-11創(chuàng)建二叉樹(shù)<

118、;/p><p><b>　　5.2.2遍歷</b></p><p>　　創(chuàng)建二叉樹(shù)時(shí)，可以從磁盤中的文本文件中讀取“擴(kuò)展先序遍歷”的字符串序列，也可以在軟件運(yùn)行過(guò)程中通過(guò)輸入框手動(dòng)輸入新的“擴(kuò)展先序遍歷”字符串序列。</p><p>　　bool BTree:: PerOrderTraverse(BTreeNode* root, Function

119、fun)</p><p><b>　　{</b></p><p><b>　　if (root)</b></p><p><b>　　{</b></p><p>　　if (!(this->*fun) (root))</p><p>　　retur

120、n false;</p><p>　　if (!LeftIsEmpty(root))/*如果有左子樹(shù)*/</p><p><b>　　{</b></p><p>　　if (!PerOrderTraverse(root->LeftChild, fun))</p><p>　　return false;</p&

121、gt;<p><b>　　}</b></p><p>　　if (!RightIsEmpty(root))/*如果有右子樹(shù)*/</p><p><b>　　{</b></p><p>　　if (!PerOrderTraverse(root->RightChild, fun))</p>&

122、lt;p>　　return false;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　由于具體項(xiàng)目較大，代

123、碼部分就不在此一一寫(xiě)出了，詳見(jiàn)具體項(xiàng)目部分。</p><p><b>　　總結(jié)</b></p><p>　　這是我第一次獨(dú)立完成這種較大項(xiàng)目的設(shè)計(jì)，包括前期的需求分析，系統(tǒng)各個(gè)部分的分模塊設(shè)計(jì)，圖形庫(kù)的設(shè)計(jì)等等。鑒于以前有過(guò)這種方面的小組合作經(jīng)驗(yàn)，相對(duì)來(lái)說(shuō)不是很難。</p><p>　　首先，一定要對(duì)自己做的項(xiàng)目有一個(gè)全面透徹的了解，它的主要流

124、程，圖形顯示、算法設(shè)計(jì)的等等。這些我是通過(guò)以往的經(jīng)驗(yàn)和翻閱資料獲得的。在明確了需求分析這個(gè)基礎(chǔ)上，建立好圖形庫(kù)，編寫(xiě)需要的算法。這些工作完成了，剩下的就主要演示代碼部分的實(shí)現(xiàn)了，這是一個(gè)程序員的基本素質(zhì)，相對(duì)來(lái)說(shuō)要容易一些。</p><p>　　由于采用的是自己以前比較熟悉的dos平臺(tái)，整個(gè)代碼部分相對(duì)來(lái)說(shuō)要簡(jiǎn)潔明了一些。對(duì)于這個(gè)相較以往較大一點(diǎn)的項(xiàng)目來(lái)說(shuō)，編程的第一步是搭建好框架。就是以分層的形式將程序分工，包

125、括數(shù)據(jù)層，業(yè)務(wù)邏輯層和控制層。</p><p>　　這種分包結(jié)構(gòu)的編寫(xiě)使得整個(gè)程序的安全性得到了提高，而且可重用性得到了加強(qiáng)。由于時(shí)間倉(cāng)促和經(jīng)驗(yàn)匱乏，所以對(duì)整個(gè)系統(tǒng)演示顯得有點(diǎn)簡(jiǎn)單，跟實(shí)際有點(diǎn)脫軌，但基本上功能都能實(shí)現(xiàn)，這將是一次很好的鍛煉機(jī)會(huì)。通過(guò)這次實(shí)訓(xùn)，我對(duì)C++編程思想有了更深一點(diǎn)的了解，編寫(xiě)代碼的熟練程度以及發(fā)現(xiàn)錯(cuò)誤的速度和修改能力都有了很大程度的提升，我知道自己相對(duì)來(lái)說(shuō)缺乏的是實(shí)際的工作經(jīng)驗(yàn)，面臨具體

126、的項(xiàng)目需求，這是需要改進(jìn)的地方。</p><p><b>　　致謝</b></p><p>　　大學(xué)學(xué)習(xí)生涯就要結(jié)束了，首先我要向我的母?！颖鞭r(nóng)業(yè)大學(xué)致以深深的謝意。在這里度過(guò)了一段美好的、令我難忘的日子。</p><p>　　感謝常淑惠老師，是她在繁忙的工作與教學(xué)之余，一次次不厭其煩地幫我分析相關(guān)技術(shù)，解決技術(shù)難題，并教給我正確的研究方法