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

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

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

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

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

5、 n,int m) { int day[10];//初始化變量，用數(shù)組元素分別存儲(chǔ)每天的桃子個(gè)數(shù) int i;//控制循環(huán)執(zhí)行的次數(shù) day[0]=n;//最后一天的桃子個(gè)數(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;//用戶要計(jì)算的是第幾天 printf("請(qǐng)輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m)

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

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

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

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

10、SqStack s; //構(gòu)造一個(gè)空棧 int InitStack() { s.base=(int *) malloc(STACK_INIT_SIZE * sizeof(int)); if(!s.base) exit (OVERFLOW);//存儲(chǔ)分配失敗 s.top=s.base;//剛開始棧為空 s.stacksize=20; return OK; } //計(jì)算桃子個(gè)數(shù)的函數(shù) void Push(int e,int m)// m是要計(jì)算的是第幾天 { 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++;//每插入一個(gè)棧頂元素，指針就要自加1 } printf("第%d天的桃子為:%d\n",m,*(s.top-1)); } 用遞歸實(shí)現(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)實(shí)現(xiàn)時(shí)，運(yùn)行時(shí)沒有顯示錯(cuò)誤，但輸出不是預(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; } 在指針的移動(dòng)時(shí)，由于p總是第一個(gè)結(jié)點(diǎn)，在for循環(huán)前已經(jīng)被賦值，指針P 應(yīng)該總是指向最后一個(gè)結(jié)點(diǎn)的，所以在這句s->next=NULL前加上一句p=s就行了， 就能輸出正確結(jié)果。 2 在生成新結(jié)點(diǎn)時(shí)，一定要用強(qiáng)制類型

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

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

15、和教師，還查閱了很多和鏈表有關(guān)系的書籍，通過學(xué)習(xí)，翻看以前學(xué)過的知識(shí)，使我明白了我在學(xué)習(xí)知識(shí)上的很多不足。不過在此同時(shí)又重新復(fù)習(xí)了課本，從中學(xué)到了許多以前未學(xué)到的知識(shí)，感覺非常有成就感，讓我對(duì)自己更加有信心，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程也更感興趣了，以前我一直感覺枯燥難學(xué)的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在我也愿意去認(rèn)真研究學(xué)習(xí)了。 這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，多虧了我的指導(dǎo)教師黃磊教師的悉心教誨。在以后的學(xué)習(xí)過程中，我要認(rèn)真負(fù)責(zé)地對(duì)待課本中的每一個(gè)知識(shí)點(diǎn)，進(jìn)一步充實(shí)自己，提高自己。 參考文獻(xiàn) [1] 黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．：中國電力，2008 [2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(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("請(qǐng)輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m); while(1){ int j; printf("請(qǐng)輸入j的值 0:退出 1:繼續(xù):\n"); scanf("%d",&j); switch(j){ case 1: printf("請(qǐng)輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); taozi(1,m); break; case 0: retur

18、n; break; default: printf("輸入有誤請(qǐng)重新輸入!"); } } } 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é)點(diǎn) 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總是指向最后一個(gè)結(jié)點(diǎn) s->next=NULL; }

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

21、要求第幾天剩下的桃子:\n"); scanf("%d",&n); k=11-n; CreateList_L(1,k); break; case 0: return; break; default: printf("輸入有誤請(qǐng)重新輸入!"); } } } 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("請(qǐng)輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); Push(1,m); while(1){ int j; printf("請(qǐng)輸入j的值 0:退出 1:繼續(xù):\n"); scanf

24、("%d",&j); switch(j){ case 1: printf("請(qǐng)輸入要求第幾天剩下的桃子:\n"); scanf("%d",&m); Push(1,m); break; case 0: return; break; default: printf("輸入有誤請(qǐng)重新輸入!"); } } } 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