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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、;<b>　　2.3流程圖</b></p><p>　　實現(xiàn)遞歸的部分如下：</p><p>　　2.4模塊及其功能介紹</p><p>　　首先定義隊列的結(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)；然后定義隊列變量que，用來存放移動時開始和終止的盤子，并且記下相應(yīng)的步驟，；調(diào)用遞歸函數(shù)，當(dāng)遞歸函數(shù)運行結(jié)束之后，就輸出隊列中所有的步驟。</p><p><b>　　3. 設(shè)計實現(xiàn)</b></p><p>　　3.1系

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

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

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

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

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