數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-- 漢諾威塔

1、<p>　　數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程設(shè)計(jì)報(bào)告</p><p>　　題 目： 漢諾威塔 </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號(hào)： </p><p>　　專業(yè)班級(jí)： &

2、lt;/p><p>　　同組姓名： </p><p>　　指導(dǎo)教師： </p><p>　　設(shè)計(jì)時(shí)間： 大二上學(xué)期十七周 </p><p><b>　　目錄</b></p><p>　　一. 設(shè)計(jì)目的與要求……………

3、…………………………………… 02</p><p>　　1.1設(shè)計(jì)目的……………………………………………… 02</p><p>　　1.2設(shè)計(jì)要求……………………………………………… 02</p><p>　　二. 設(shè)計(jì)分析………………………………………………………… 02</p><p>　　2.1漢諾威塔問(wèn)題…………………………

4、……………… 02</p><p>　　2.2算法分析……………………………………………… 03</p><p>　　2.3流程圖………………………………………………… 06</p><p>　　2.4模塊及其功能介紹…………………………………… 07</p><p>　　三. 設(shè)計(jì)實(shí)現(xiàn)…………………………………………………………

5、08</p><p>　　四. 心得體會(huì)………………………………………………………… 09</p><p>　　五. 參考文獻(xiàn)………………………………………………………… 10</p><p><b>　　1.設(shè)計(jì)目的與要求</b></p><p><b>　　1.1設(shè)計(jì)目的</b></p

6、><p>　　隨著計(jì)算機(jī)技術(shù)以及外圍設(shè)備的發(fā)展，計(jì)算機(jī)在輔助設(shè)計(jì)制造，計(jì)算機(jī)教育，計(jì)算機(jī)信息化應(yīng)用中，圖形的作用和魅力愈加顯現(xiàn)。</p><p>　　如何運(yùn)用計(jì)算機(jī)技術(shù)、運(yùn)用算法編程來(lái)優(yōu)化解決低階漢諾威塔問(wèn)題對(duì)我們學(xué)生來(lái)說(shuō)具有可實(shí)現(xiàn)和可操作性。本次課程設(shè)計(jì)的目的就是利用所學(xué)習(xí)到得算法知識(shí)和編程語(yǔ)言知識(shí)來(lái)解決、實(shí)現(xiàn)低階漢諾威塔問(wèn)題。</p><p><b>　　

7、1.2設(shè)計(jì)要求</b></p><p>　　功能：編程序顯示n（n<=9）層漢諾威塔的調(diào)整過(guò)程。</p><p><b>　　分步實(shí)施：</b></p><p>　　1.初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對(duì)話的界面，確定函數(shù)個(gè)數(shù)；</p><p>　　2.完成最低要求：實(shí)現(xiàn)5層漢諾威塔的調(diào)整過(guò)程；&l

8、t;/p><p>　　3.進(jìn)一步要求：直至實(shí)現(xiàn)n＝9時(shí)的情況。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。</p><p>　　要求：1）界面友好，函數(shù)功能要?jiǎng)澐趾?lt;/p><p>　　2）總體設(shè)計(jì)應(yīng)畫一流程圖</p><p>　　3）程序要加必要的注釋</p><p>　　4）要提供程序測(cè)試方案</p><p&

9、gt;　　5）程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來(lái)，不能運(yùn)行的程序是沒(méi)有價(jià)值的。</p><p><b>　　2.設(shè)計(jì)分析</b></p><p><b>　　2.1漢諾威塔問(wèn)題</b></p><p>　　n階漢諾威塔問(wèn)題：有三個(gè)柱子A, B, C。A柱子上疊放有n個(gè)盤子，每個(gè)盤子都比它下面的盤子要小一點(diǎn)

10、，可以從上到下用1, 2, ..., n編號(hào)。要求借助柱子C，把柱子A上的所有的盤子移動(dòng)到柱子B上。移動(dòng)條件為：</p><p>　　1、一次只能移一個(gè)盤子；</p><p>　　2、移動(dòng)過(guò)程中大盤子不能放在小盤子上，只能小盤子放在大盤子上</p><p>　　如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C</p><

11、p><b>　　2.2算法分析</b></p><p>　　為滿足題目中盤子的移動(dòng)問(wèn)題，必須遵循的條件是：一次僅能移動(dòng)一個(gè)盤，且不允許大盤放在小盤的上面。</p><p>　　設(shè)A上有n個(gè)盤子。 </p><p>　　當(dāng)n=1時(shí)，則將圓盤從A直接移動(dòng)到C。 </p><p>　　當(dāng)n>=2時(shí)，移動(dòng)的過(guò)程可分解

12、為三個(gè)步驟： </p><p>　　1) 把A上的n-1個(gè)圓盤移到B上； </p><p>　　2) 把A上的一個(gè)圓盤移到C上； </p><p>　　3) 把B上的n-1個(gè)圓盤移到C上；其中第一步和第三步是相同的。 </p><p>　　為了更清楚地描述算法，用圖示法描述如下：</p><p>　　要將N個(gè)盤子從A桿

13、上借助C桿移動(dòng)到B桿上。這樣移動(dòng)N個(gè)盤子的工作就可以按照以下過(guò)程進(jìn)行：</p><p><b>　　第一次調(diào)用遞歸 </b></p><p>　　②將一個(gè)盤子從A移動(dòng)到B上；</p><p><b>　?、鄣诙握{(diào)用遞歸</b></p><p>　　重復(fù)以上過(guò)程，直到將全部的盤子移動(dòng)到位時(shí)為止。&l

14、t;/p><p>　　由遞歸算法我們可以得到遞推關(guān)系：</p><p>　　移動(dòng)n個(gè)圓盤需要步，如：移動(dòng)4個(gè)圓盤需要15步，移動(dòng)64個(gè)圓盤需要264-1</p><p><b>　　示意圖:</b></p><p>　　當(dāng)N=3時(shí)的遞歸調(diào)用樹狀圖，可以使我們更清楚的了解遞歸的調(diào)用過(guò)程。</p><p>

15、;<b>　　2.3流程圖</b></p><p>　　實(shí)現(xiàn)遞歸的部分如下：</p><p>　　2.4模塊及其功能介紹</p><p>　　首先定義隊(duì)列的結(jié)構(gòu)體和的函數(shù)，void Init(Queue &que)；void Clear(Queue &que)；bool Empty(Queue que)；void Pop(Que

16、ue &que)；Node *Front(Queue &que)；void Push(Queue &que,Node e)；然后定義隊(duì)列變量que，用來(lái)存放移動(dòng)時(shí)開始和終止的盤子，并且記下相應(yīng)的步驟，；調(diào)用遞歸函數(shù)，當(dāng)遞歸函數(shù)運(yùn)行結(jié)束之后，就輸出隊(duì)列中所有的步驟。</p><p><b>　　3. 設(shè)計(jì)實(shí)現(xiàn)</b></p><p>　　3.1系

17、統(tǒng)運(yùn)行界面：當(dāng)n=5時(shí)，</p><p>　　當(dāng)n=9時(shí)，結(jié)果如下：</p><p><b>　　4. 心得體會(huì)</b></p><p>　　程序的算法設(shè)計(jì)與分析，是我在本階段學(xué)完理論課程之后對(duì)自己該方面的能力的一次很好的檢驗(yàn)，從開始的算法思路到運(yùn)行調(diào)試后的運(yùn)行結(jié)果以及另人興奮的可用程序，都是一個(gè)很好的學(xué)習(xí)和鍛煉的過(guò)程。</p>

18、<p>　　通過(guò)這次課程設(shè)計(jì)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有了新一層的了解，讓我明白各種函數(shù)以及類的應(yīng)用，明白了算法對(duì)程序的重要性。通過(guò)這次課程設(shè)計(jì)，使我認(rèn)識(shí)到，僅僅是學(xué)會(huì)書面知識(shí)是不行的，一方面，對(duì)程序設(shè)計(jì)語(yǔ)言本身的理解不夠透徹，另一方面，由于對(duì)數(shù)據(jù)結(jié)構(gòu)及常用算法的理解上的欠缺，再加上我自己在這方面的練習(xí)相當(dāng)少，這些都不同程度地添加了我完成這個(gè)題目的困難度。</p><p>　　要做算法的設(shè)計(jì)首先是對(duì)程序設(shè)計(jì)語(yǔ)言的

19、相當(dāng)?shù)氖煜?，而且能夠?qū)嶋H熟練地運(yùn)用，要能夠把自己的想法，轉(zhuǎn)換為由程序設(shè)計(jì)語(yǔ)言來(lái)表達(dá)。這就要求自己不僅僅要會(huì)解決實(shí)際問(wèn)題，而且要有能夠?qū)?shí)際問(wèn)題抽象化，數(shù)學(xué)建模，以及能用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)表達(dá)實(shí)現(xiàn)。這對(duì)我們的程序設(shè)計(jì)水平和對(duì)程序語(yǔ)言代碼的敏感度以及專業(yè)修養(yǎng)是一個(gè)很好的挑戰(zhàn)。</p><p>　　算法設(shè)計(jì)的要求也不僅僅是程序設(shè)計(jì)語(yǔ)言，前面講到了由實(shí)際具體問(wèn)題抽象建模，由于計(jì)算機(jī)內(nèi)部是由二進(jìn)制來(lái)表示和存儲(chǔ)數(shù)據(jù)，程序設(shè)

20、計(jì)語(yǔ)言實(shí)現(xiàn)了計(jì)算機(jī)內(nèi)部表示和程序員和計(jì)算機(jī)交流的語(yǔ)言斷層，而程序設(shè)計(jì)語(yǔ)言和自然語(yǔ)言之間又有一個(gè)斷層，這個(gè)斷層就需要靠程序員的集體或個(gè)人腦力勞動(dòng)來(lái)彌補(bǔ)。軟件總體質(zhì)量的好壞除了對(duì)軟件工程的設(shè)計(jì)者相關(guān)，程序設(shè)計(jì)者的水平至關(guān)重要。從自然語(yǔ)言到計(jì)算機(jī)能夠讀懂的程序設(shè)計(jì)語(yǔ)言，是對(duì)程序設(shè)計(jì)能力的考驗(yàn)。</p><p>　　經(jīng)過(guò)反復(fù)的測(cè)試比較，還能找出這個(gè)設(shè)計(jì)的很多不足甚至于錯(cuò)誤，也就是說(shuō)，我現(xiàn)在所做的設(shè)計(jì)并不是那么盡善盡美的。

21、最后，感謝指導(dǎo)老師悉心指導(dǎo)，感謝同學(xué)們無(wú)私的幫助。</p><p><b>　　5. 參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏 吳偉民 . 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）: 清華大學(xué)出版社 ,2007.</p><p>　　[2] 譚浩強(qiáng)等著. C語(yǔ)言程序設(shè)計(jì) : 清華大學(xué)出版社 2008</p><p>　　[3]