數據結構課程設計報告-- 漢諾威塔

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

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

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

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

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

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

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

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

9、gt;　　5）程序一定要經得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。</p><p><b>　　2.設計分析</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>　　設A上有n個盤子。 </p><p>　　當n=1時，則將圓盤從A直接移動到C。 </p><p>　　當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個盤子的工作就可以按照以下過程進行：</p><p><b>　　第一次調用遞歸 </b></p><p>　　②將一個盤子從A移動到B上；</p><p><b>　　③第二次調用遞歸</b></p><p>　　重復以上過程，直到將全部的盤子移動到位時為止。&l

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

15、;<b>　　2.3流程圖</b></p><p>　　實現遞歸的部分如下：</p><p>　　2.4模塊及其功能介紹</p><p>　　首先定義隊列的結構體和的函數，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，用來存放移動時開始和終止的盤子，并且記下相應的步驟，；調用遞歸函數，當遞歸函數運行結束之后，就輸出隊列中所有的步驟。</p><p><b>　　3. 設計實現</b></p><p>　　3.1系

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

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

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

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

21、最后，感謝指導老師悉心指導，感謝同學們無私的幫助。</p><p><b>　　5. 參考文獻</b></p><p>　　[1] 嚴蔚敏 吳偉民 . 數據結構（C語言版）: 清華大學出版社 ,2007.</p><p>　　[2] 譚浩強等著. C語言程序設計 : 清華大學出版社 2008</p><p>　　[3]