猴子吃桃子問題 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

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

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

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

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

4、，需屢次進(jìn)展自我調(diào)用，遞歸函數(shù)的運(yùn)行過程類似與多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，從主函數(shù)開始調(diào)用，一次更深一層，退出時一步一步返回到上一層，所以不需寫控制循環(huán)語句，不需要寫控制循環(huán)語句，比上幾種方法簡單點。 3、 運(yùn)行環(huán)境 3.1 硬件環(huán)境 PC 〔1〕Windows XP 〔2〕Microsoft Visual 4、 詳細(xì)設(shè)計 猴子吃桃問題的實現(xiàn) 用數(shù)組結(jié)構(gòu)實現(xiàn) 用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 用棧數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 用遞歸方法實現(xiàn) 用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(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);//相鄰元素之間的關(guān)系 printf("第%d天的桃子為:%d\n",m,day[10-m]); } void main() { int m;//用戶要計算的是第幾天 printf("請輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m)

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

7、/當(dāng)用戶輸入除0和1以外的數(shù)值時，會讓你重新輸入，直到輸入正確為止 default: printf("輸入有誤請重新輸入!"); } } } 用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 //預(yù)定義常量和類型 #define NULL 0 //單鏈表的存儲結(jié)構(gòu) 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));//生成新結(jié)點 p=(LNode *) malloc(sizeof(LNode)); L->next=NULL;//創(chuàng)建一個帶頭結(jié)點的單鏈表 L->next=p;//插入到表頭 L->next->data=e;//初始化第一個結(jié)點 for(i=m-1;i>0;i--) { s=(LNode *) malloc(sizeof(LNode)); p->next=s;

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

10、SqStack s; //構(gòu)造一個空棧 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);//棧頂元素和剛插入的元素之間的關(guān)系 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、 調(diào)試分析 1 在用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)時，運(yùn)行時沒有顯示錯誤，但輸出不是預(yù)測的結(jié)果，代碼如下： 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總是第一個結(jié)點，在for循環(huán)前已經(jīng)被賦值，指針P 應(yīng)該總是指向最后一個結(jié)點的，所以在這句s->next=NULL前加上一句p=s就行了， 就能輸出正確結(jié)果。 2 在生成新結(jié)點時，一定要用強(qiáng)制類型

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

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

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

16、解[M]．：中國電力，2008 [3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)〔C語言版〕[M]. ：清華大學(xué)，2002 [4] X振鵬，X曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．：中國鐵道，2003 附錄： 源代碼如下 1 用數(shù)組數(shù)據(jù)結(jié)構(gòu)編寫 #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ù)結(jié)構(gòu)編寫 #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)建頭結(jié)點 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總是指向最后一個結(jié)點 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ù)結(jié)構(gòu)編寫 #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