《猴子吃桃子問題 大數(shù)據(jù)結構課程設計》由會員分享，可在線閱讀，更多相關《猴子吃桃子問題 大數(shù)據(jù)結構課程設計（15頁珍藏版）》請在裝配圖網上搜索。

1、word 目錄 1、需求分析1 2、概要設計1 2.1.用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解1 2.2.用鏈數(shù)據(jù)結構實現(xiàn)上述求解1 2.3 用棧數(shù)據(jù)結構實現(xiàn)求解1 2.4 用遞歸實現(xiàn)上述求解2 3、 運行環(huán)境2 3.1 硬件環(huán)境2 軟件環(huán)境2 4、 詳細設計2 系統(tǒng)流程圖2 用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解3 用鏈數(shù)據(jù)結構實現(xiàn)上述求解4 用棧數(shù)據(jù)結構實現(xiàn)求解5 用遞歸實現(xiàn)上述求解6 5、 調試分析7 6、運行結果7 課程設計總結8 參考文獻9 附錄：9 1、需求分析 1、 猴子吃桃子問題 有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10

2、天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。 ?要求： 1)?采用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解 2)?采用鏈數(shù)據(jù)結構實現(xiàn)上述求解 3)?采用棧實現(xiàn)上述求解 4)?采用遞歸實現(xiàn)上述求解 2、概要設計 在taozi函數(shù)中定義一個一維數(shù)組，分別存儲每天的桃子個數(shù)，根據(jù)題目的內容找出各個數(shù)之間的關系，用數(shù)組元素表示出來，根據(jù)用戶輸入要計算哪一天的桃子，用for循環(huán)控制完畢。在main函數(shù)中讓用戶輸入要計算的哪一天，調用taozi函數(shù)，以便用戶可查出任意一天的桃子個數(shù)，用switch語句判斷用戶要執(zhí)行的功能，然后用while循環(huán)控制，直到用戶輸入0為止。

3、 先寫出預定義常量和類型，寫出結點的類型定義，創(chuàng)建結點，初始化鏈表，定義變量并初始化，找出結點與其后繼結點之間的聯(lián)系，然后在主函數(shù)中控制。 2.3 用棧數(shù)據(jù)結構實現(xiàn)求解 本局部包括預定義常量和類型，順序棧的定義，InitStack函數(shù)，Push函數(shù)，和main函數(shù)，在InitStack函數(shù)構造一個空棧，在Push函數(shù)中調用該函數(shù)，并在其中編寫控制棧頂指針和棧底指針移動的語句，找出指針所指向的數(shù)據(jù)之間的關系，在main函數(shù)中編寫控制循環(huán)完畢的語句，最后再用main函數(shù)去調用Push函數(shù)。 2.4 用遞歸實現(xiàn)上述求解 這種方法跟上述幾種不同，在函數(shù)的執(zhí)行函數(shù)的過程中

4、，需屢次進展自我調用，遞歸函數(shù)的運行過程類似與多個函數(shù)的嵌套調用，只是調用函數(shù)和被調用函數(shù)是同一個函數(shù)，從主函數(shù)開始調用，一次更深一層，退出時一步一步返回到上一層，所以不需寫控制循環(huán)語句，不需要寫控制循環(huán)語句，比上幾種方法簡單點。 3、 運行環(huán)境 3.1 硬件環(huán)境 PC 〔1〕Windows XP 〔2〕Microsoft Visual 4、 詳細設計 猴子吃桃問題的實現(xiàn) 用數(shù)組結構實現(xiàn) 用鏈數(shù)據(jù)結構實現(xiàn) 用棧數(shù)據(jù)結構實現(xiàn) 用遞歸方法實現(xiàn) 用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解 //計算桃子的個數(shù) void taozi(int

5、 n,int m) { int day[10];//初始化變量，用數(shù)組元素分別存儲每天的桃子個數(shù) int i;//控制循環(huán)執(zhí)行的次數(shù) day[0]=n;//最后一天的桃子個數(shù) for(i=0;i<10-m;i++) day[i+1]=2*(day[i]+1);//相鄰元素之間的關系 printf("第%d天的桃子為:%d\n",m,day[10-m]); } void main() { int m;//用戶要計算的是第幾天 printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m)

6、;//調用 while(1){ int j;//循環(huán)控制條件 printf("請輸入j的值 0:退出 1:繼續(xù):\n"); scanf("%d",&j); switch(j){ //當j=1時，用戶可以輸入屢次想要的數(shù)值 case 1: printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m); break;//跳出 //當j=0時，跳出switch結構 case 0: return; break; /

7、/當用戶輸入除0和1以外的數(shù)值時，會讓你重新輸入，直到輸入正確為止 default: printf("輸入有誤請重新輸入!"); } } } 用鏈數(shù)據(jù)結構實現(xiàn)上述求解 //預定義常量和類型 #define NULL 0 //單鏈表的存儲結構 typedef struct LNode{ int data;//數(shù)據(jù)域 struct LNode *next;//指針域 }LNode; LNode *L; LNode *p,*s; //計算桃子的個數(shù) int CreateList_L(int e,int m)//e是第十天的桃子的個數(shù)，m是將要

8、計算的是第幾天 { int i; L=(LNode *) malloc(sizeof(LNode));//生成新結點 p=(LNode *) malloc(sizeof(LNode)); L->next=NULL;//創(chuàng)建一個帶頭結點的單鏈表 L->next=p;//插入到表頭 L->next->data=e;//初始化第一個結點 for(i=m-1;i>0;i--) { s=(LNode *) malloc(sizeof(LNode)); p->next=s;

9、s->data=2*(p->data+1);//結點與下一結點之間的聯(lián)系 p=s;//指針P總是指向最后一個結點 s->next=NULL; } printf("第%d天的桃子為:%d\n",11-m,p->data); } 用棧數(shù)據(jù)結構實現(xiàn)求解 //儲存空間初始分配量 #define STACK_INIT_SIZE 100 //順序棧的定義 typedef struct { int *base;//棧底指針 int *top;//棧頂指針 int stacksize;//當前已分配的存儲空間 }SqStack;

10、SqStack s; //構造一個空棧 int InitStack() { s.base=(int *) malloc(STACK_INIT_SIZE * sizeof(int)); if(!s.base) exit (OVERFLOW);//存儲分配失敗 s.top=s.base;//剛開始棧為空 s.stacksize=20; return OK; } //計算桃子個數(shù)的函數(shù) void Push(int e,int m)// m是要計算的是第幾天 { int i; InitStack(); *s.top++=e;//給棧底元素初始化

11、for(i=0;i<10-m;i++) { *s.top=2*(*(s.top-1)+1);//棧頂元素和剛插入的元素之間的關系 s.top++;//每插入一個棧頂元素，指針就要自加1 } printf("第%d天的桃子為:%d\n",m,*(s.top-1)); } 用遞歸實現(xiàn)上述求解 int i=9;//初始化全局變量 //遞歸函數(shù) int taozi(int x) { int y; while(i>0) { y=2*(x+1); i--;//循環(huán)控制條件 taozi(y); printf("%d\n",y); } }

12、 5、 調試分析 1 在用鏈數(shù)據(jù)結構實現(xiàn)時，運行時沒有顯示錯誤，但輸出不是預測的結果，代碼如下： for(i=m-1;i>0;i--) { s=(LNode *) malloc(sizeof(LNode)); p->next=s; s->data=2*(p->data+1); s->next=NULL; } 在指針的移動時，由于p總是第一個結點，在for循環(huán)前已經被賦值，指針P 應該總是指向最后一個結點的，所以在這句s->next=NULL前加上一句p=s就行了， 就能輸出正確結果。 2 在生成新結點時，一定要用強制類型

13、轉換，要不就要出錯。不能把s=(LNode *) malloc(sizeof(LNode))寫成s=(LNode) malloc(sizeof(LNode));因為它們不屬于同一類型。 3 在用棧數(shù)據(jù)結構實現(xiàn)的過程中，雖然只有一個錯誤，但卻顯示了好多錯誤。主要原因是由于一個參數(shù)是在main函數(shù)中定義的，但卻被其它函數(shù)調用，只要把該參數(shù)定義成全局變量就行了。 4 在用while循環(huán)時，由于控制條件的不恰當導致的錯誤，不過只要再認真分析一下，就正確了。 5 還有些其它方面的錯誤，不過只要看一眼，就能改正，是粗心造成的。 6、運行結果 鏈數(shù)組和棧實現(xiàn)結果： 遞歸實現(xiàn)結果：

14、 課程設計總結 通過這一周的實踐學習，我認識到學好計算機要重視實踐操作，不僅僅是學習數(shù)據(jù)結構，以與其它的計算機方面的知識都要重在實踐，很多以前學過的東西，在運用時都不能很熟練，也說明理論知識和實踐之間的差異。這就告訴了我們在以后的學習過程中要培養(yǎng)自己的動手能力，要將學過的知識轉化為實踐。作為一個計科專業(yè)的學生，通過這周的學習，使我更加明白了動手能力的重要性。 在這次的課程設計中，我不斷地去找書本知識和查閱其它有關資料，不僅鞏固了對課本知識的掌握，還有利于以后更好的進步，提高了對課外知識的了解，雖然花費了不少時間，但只要學到有價值的東西，我認為都是值得的。在完成該試驗的過程中，我問了同學

15、和教師，還查閱了很多和鏈表有關系的書籍，通過學習，翻看以前學過的知識，使我明白了我在學習知識上的很多不足。不過在此同時又重新復習了課本，從中學到了許多以前未學到的知識，感覺非常有成就感，讓我對自己更加有信心，讓我對數(shù)據(jù)結構這門課程也更感興趣了，以前我一直感覺枯燥難學的數(shù)據(jù)結構，現(xiàn)在我也愿意去認真研究學習了。 這次數(shù)據(jù)結構課程設計中，多虧了我的指導教師黃磊教師的悉心教誨。在以后的學習過程中，我要認真負責地對待課本中的每一個知識點，進一步充實自己，提高自己。 參考文獻 [1] 黃同成，黃俊民，董建寅．數(shù)據(jù)結構[M]．：中國電力，2008 [2] 董建寅，黃俊民，黃同成．數(shù)據(jù)結構實驗指導與題

16、解[M]．：中國電力，2008 [3] 嚴蔚敏，吳偉民. 數(shù)據(jù)結構〔C語言版〕[M]. ：清華大學，2002 [4] X振鵬，X曉莉，郝杰．數(shù)據(jù)結構[M]．：中國鐵道，2003 附錄： 源代碼如下 1 用數(shù)組數(shù)據(jù)結構編寫 #include void taozi(int n,int m) { int day[10]; int i; day[0]=n; for(i=0;i<10-m;i++) day[i+1]=2*(day[i]+1); printf("第%d天的桃子為:%d\n",m,day[10-m]); } voi

17、d main() { int m; printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m); while(1){ int j; printf("請輸入j的值 0:退出 1:繼續(xù):\n"); scanf("%d",&j); switch(j){ case 1: printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m); break; case 0: retur

18、n; break; default: printf("輸入有誤請重新輸入!"); } } } 2 用鏈數(shù)據(jù)結構編寫 #include #include #define NULL 0 typedef struct LNode{ int data; struct LNode *next; }LNode; LNode *L; LNode *p,*s; int CreateList_L(int e,int m) { int i; L=(LNode *) malloc

19、(sizeof(LNode)); p=(LNode *) malloc(sizeof(LNode)); L->next=NULL;//創(chuàng)建頭結點 L->next=p; L->next->data=e; for(i=m-1;i>0;i--) { s=(LNode *) malloc(sizeof(LNode)); p->next=s; s->data=2*(p->data+1); p=s;//指針P總是指向最后一個結點 s->next=NULL; }

20、 printf("第%d天的桃子為:%d\n",11-m,p->data); } void main() { int n; int k; printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&n); k=11-n; CreateList_L(1,k); while(1){ int j; printf("請輸入j的值 0:退出 1:繼續(xù):\n"); scanf("%d",&j); switch(j){ case 1: printf("請輸入

21、要求第幾天剩下的桃子:\n"); scanf("%d",&n); k=11-n; CreateList_L(1,k); break; case 0: return; break; default: printf("輸入有誤請重新輸入!"); } } } 3 用棧數(shù)據(jù)結構編寫 #include #include #define STACK_INIT_SIZE 100 #define OK 1

22、 #define OVERFLOW -2 typedef struct { int *base; int *top; int stacksize; }SqStack; SqStack s; int InitStack() { s.base=(int *) malloc(STACK_INIT_SIZE * sizeof(int)); if(!s.base) exit (OVERFLOW); s.top=s.base; s.stacksize=20; return OK; } void Push(int e,int m) { int i

23、; InitStack(); *s.top++=e; for(i=0;i<10-m;i++) { *s.top=2*(*(s.top-1)+1); s.top++; } printf("第%d天的桃子為:%d\n",m,*(s.top-1)); } void main() { int m; printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); Push(1,m); while(1){ int j; printf("請輸入j的值 0:退出 1:繼續(xù):\n"); scanf

24、("%d",&j); switch(j){ case 1: printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); Push(1,m); break; case 0: return; break; default: printf("輸入有誤請重新輸入!"); } } } 4 用遞歸編寫 #include int i=9; int taozi(int x) { int y; while(i>0) { y=2*(x+1); i--; taozi(y); printf("%d\n",y); } } void main() { int a=1; taozi(a); printf("1\n"); } 14 / 15