湖 南 工 學 院 數據結構課程設計題 目： 數據結構實現猴子吃桃系 別： 專 業： 年 級： 班 級： 學 生： 學 號： 目 錄l 論 文 提 要 3l 需 求 分 析 4l 詳 細 設 計 5n 數組結構 5n 遞歸 7n 鏈表 9l 調 試 結 果 11l 調試分析 12論文提要初步分析說明數據結構和抽象數類型等基本概念；從抽象數據類型的角度，通過數學應用的分析，把問題進行分析，整理，面后通過觀察選擇適當的邏輯結構、存儲結構入及其相應的算法來解決問題,數據結構課程主要是為了培養我們對數據的抽象能力和對算法在時間和空間和復雜度上進行優化，猴子吃桃這一數學方面的例題是很典型的一道程序例題，在這里主要以C語言作為數據結構和描述語言，分析并采用數組數據結構，遞歸，鏈數據結構實現上述問題。需 求 分 析實現課題猴子吃桃摘 要：猴子吃桃這一典型的數學課題,其主要實現的過程是將其數學課題公式化，用一些簡單的數據定義、初使化、通過一系列的條件判斷和循環用來實現學數公式的計算機化。通過C語言基礎分析和數據結構初步了解,我們使用C語言,利用C和數據結構的結合使用,讓我們在短時間內建立起對數據結構的進一步認識。然后,形成正確的對算法和優有個的理解觀念。關鍵詞：C語言的基本了解，數據結構的基本了解, 數據中數組的使用，遞歸調用，用C語言實現數據鏈表題目：猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個，第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了，求第一天共摘了多少？ 要求： 采用數組，遞歸，鏈數據結構實現上述求解 詳 細 設 計1 數組結構把猴子吃桃的天數倒過來看的話，以天數作為數組的下標i，剩下桃子的個數ai的遞推公式為ai=(ai-1+1)*2。ai實際代表了倒數第i天剩下的桃子數。數組結構算法的流程圖如圖3-1：開 始建立一個以天數為下標以剩下桃子數為元素的數組規定此數組的通向公式求第一天的桃子數結 束程序如下：#includevoid main() int i,tao10; tao9=1;/tao9代表第10天剩的桃子數 for(i=8;i=0;i-) taoi=2*(taoi+1+1); printf(共摘了%d個桃子！n,tao0);2.鏈結構 建立一個鏈表，根據每天桃子數與后一天桃子數的關系n=2*n+2,依次將每天的桃子數存進鏈表中，最后輸出第一天的桃子數。首先是建立一個空鏈表，產生一個頭結點，且將頭結點的地址賦給L。然后把每天的桃子數從鏈表的第一個結點插入鏈表。最后第一天的桃子數被最后一個插入鏈表，成為鏈表中第一個值，將其賦給e，最后只要輸出e即得到第一天的桃子數。程序如下：#includestdio.h#includestdlib.h#define TRUE 1#define FALSE 0#define NULL 0typedef int ElementType;typedef struct nodeElementType data;struct node *next;StackNode,*LinkStack;void InitStack(LinkStack top)top-next=NULL;int IsEmpty(LinkStack top) if(top-next=NULL) return TRUE;else return FALSE;int Push(LinkStack top,ElementType element)StackNode *temp;temp=(StackNode *)malloc(sizeof(StackNode);if(!temp) return FALSE;else temp-data=element;temp-next=top-next;top-next=temp; return TRUE;int Pop(LinkStack top,ElementType *element)if(IsEmpty(top) return FALSE;else StackNode *temp=top-next;*element=temp-data;top-next=temp-next;free(temp);return TRUE;void main() int i=10,data; Stack s; InitStack(s); PushStack(s,1); while(i-1) data=PopStack(s); PushStack(s,2*(data+1); printf(共摘了%d個桃子！n,PopStack(s);3.遞歸結構設計遞歸算法，利用x=2*x+2，定義一個函數sum_fan，然后不斷調用自身，求得第一天的桃子數。遞歸算法的流程圖如圖3-3開 始定義參數i和ni0NY調用本身，且-i輸出sum開 始程序如下：#includeint tao(int n) if(n=10) return 1; return 2*(tao(n+1)+1);void main() int sum=0; sum+=tao(1); printf(共摘了%d個桃子！n,sum);調 試 結 果4.2運行結果數組結構，鏈結構，遞歸結構的運行結果如圖：數組結構結果 調 試 分 析 運行環境在本課程設計中，系統開發平臺為Windows2000,程序設計語言為Visual C+6.0，程序的運行環境為Visual C+ 6.0。Visual C+一般分為三個版本:學習版、專業版和企業版，不同的版本適合于不同類型的應用開發。實驗中可以使用這三個版本的任意一種，在本課程設計中，以Visual C+ 6.0為編程環境。 程序編輯體會 這次的課程設計的內容是用C語言實現猴子吃桃子問題，這對我來說是個很具有挑戰性的任務，雖然只做了一個很簡單的學生學籍管理模塊，但通過兩個星期的設計也從中學到了不少東西，更深刻的理解了課本中的內容。數據結構是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。同時再次深刻理解了C+中類的思想和實現，文件的概念和相關操作，以及有關數據結構的很多知識。根據實際問題的需要，對個方面的優缺點加以綜合平衡，從中選擇比較適宜的實現方法。在本次課程設計中，我明白了理論與實際相結合的重要性，并提高了自己組織數據及編寫程序的能力，培養了基本的，良好的程序設計技能。提高綜合運用所學知識的能力。在這次課程設計中曾遇到了不少問題，就單憑我一個人的能力很難準時有效的完成這次的課程設計，在此，我忠心感謝我的指導老師戴成秋。