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

word目錄1、需求分析12、概要設(shè)計(jì)12.1.用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解12.2.用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解12.3 用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)求解12.4 用遞歸實(shí)現(xiàn)上述求解23、 運(yùn)行環(huán)境23.1 硬件環(huán)境2軟件環(huán)境24、 詳細(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)上述求解65、 調(diào)試分析76、運(yùn)行結(jié)果7課程設(shè)計(jì)總結(jié)8參考文獻(xiàn)9附錄：91、需求分析1、 猴子吃桃子問(wèn)題有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(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ù)組元素表示出來(lái)，根據(jù)用戶輸入要計(jì)算哪一天的桃子，用for循環(huán)控制完畢。在main函數(shù)中讓用戶輸入要計(jì)算的哪一天，調(diào)用taozi函數(shù)，以便用戶可查出任意一天的桃子個(gè)數(shù)，用switch語(yǔ)句判斷用戶要執(zhí)行的功能，然后用while循環(huán)控制，直到用戶輸入0為止。 先寫出預(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)的語(yǔ)句，找出指針?biāo)赶虻臄?shù)據(jù)之間的關(guān)系，在main函數(shù)中編寫控制循環(huán)完畢的語(yǔ)句，最后再用main函數(shù)去調(diào)用Push函數(shù)。2.4 用遞歸實(shí)現(xiàn)上述求解 這種方法跟上述幾種不同，在函數(shù)的執(zhí)行函數(shù)的過(guò)程中，需屢次進(jìn)展自我調(diào)用，遞歸函數(shù)的運(yùn)行過(guò)程類似與多個(gè)函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，從主函數(shù)開(kāi)始調(diào)用，一次更深一層，退出時(shí)一步一步返回到上一層，所以不需寫控制循環(huán)語(yǔ)句，不需要寫控制循環(huán)語(yǔ)句，比上幾種方法簡(jiǎn)單點(diǎn)。3、 運(yùn)行環(huán)境3.1 硬件環(huán)境PC1Windows XP2Microsoft Visual 4、 詳細(xì)設(shè)計(jì)猴子吃桃問(wèn)題的實(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 n,int m) int day10;/初始化變量，用數(shù)組元素分別存儲(chǔ)每天的桃子個(gè)數(shù)int i;/控制循環(huán)執(zhí)行的次數(shù)day0=n;/最后一天的桃子個(gè)數(shù) for(i=0;i<10-m;i+) dayi+1=2*(dayi+1);/相鄰元素之間的關(guān)系 printf("第%d天的桃子為:%dn",m,day10-m);void main() int m;/用戶要計(jì)算的是第幾天 printf("請(qǐng)輸入要求第幾天剩下的桃子:n"); scanf("%d",&m); taozi(1,m);/調(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; /當(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 LNodeint 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是將要計(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; 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天的桃子為:%dn",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;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;/剛開(kāi)始棧為空 s.stacksize=20; return OK;/計(jì)算桃子個(gè)數(shù)的函數(shù)void Push(int e,int m)/ m是要計(jì)算的是第幾天 int i; InitStack(); *s.top+=e;/給棧底元素初始化 for(i=0;i<10-m;i+) *s.top=2*(*(s.top-1)+1);/棧頂元素和剛插入的元素之間的關(guān)系 s.top+;/每插入一個(gè)棧頂元素，指針就要自加1 printf("第%d天的桃子為:%dn",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("%dn",y); 5、 調(diào)試分析 1 在用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)時(shí)，運(yùn)行時(shí)沒(méi)有顯示錯(cuò)誤，但輸出不是預(yù)測(cè)的結(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)制類型轉(zhuǎn)換，要不就要出錯(cuò)。不能把s=(LNode *) malloc(sizeof(LNode)寫成s=(LNode) malloc(sizeof(LNode);因?yàn)樗鼈儾粚儆谕活愋汀? 在用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的過(guò)程中，雖然只有一個(gè)錯(cuò)誤，但卻顯示了好多錯(cuò)誤。主要原因是由于一個(gè)參數(shù)是在main函數(shù)中定義的，但卻被其它函數(shù)調(diào)用，只要把該參數(shù)定義成全局變量就行了。4 在用while循環(huán)時(shí)，由于控制條件的不恰當(dāng)導(dǎo)致的錯(cuò)誤，不過(guò)只要再認(rèn)真分析一下，就正確了。5 還有些其它方面的錯(cuò)誤，不過(guò)只要看一眼，就能改正，是粗心造成的。6、運(yùn)行結(jié)果 鏈數(shù)組和棧實(shí)現(xiàn)結(jié)果：遞歸實(shí)現(xiàn)結(jié)果：課程設(shè)計(jì)總結(jié)通過(guò)這一周的實(shí)踐學(xué)習(xí)，我認(rèn)識(shí)到學(xué)好計(jì)算機(jī)要重視實(shí)踐操作，不僅僅是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，以與其它的計(jì)算機(jī)方面的知識(shí)都要重在實(shí)踐，很多以前學(xué)過(guò)的東西，在運(yùn)用時(shí)都不能很熟練，也說(shuō)明理論知識(shí)和實(shí)踐之間的差異。這就告訴了我們?cè)谝院蟮膶W(xué)習(xí)過(guò)程中要培養(yǎng)自己的動(dòng)手能力，要將學(xué)過(guò)的知識(shí)轉(zhuǎn)化為實(shí)踐。作為一個(gè)計(jì)科專業(yè)的學(xué)生，通過(guò)這周的學(xué)習(xí)，使我更加明白了動(dòng)手能力的重要性。在這次的課程設(shè)計(jì)中，我不斷地去找書本知識(shí)和查閱其它有關(guān)資料，不僅鞏固了對(duì)課本知識(shí)的掌握，還有利于以后更好的進(jìn)步，提高了對(duì)課外知識(shí)的了解，雖然花費(fèi)了不少時(shí)間，但只要學(xué)到有價(jià)值的東西，我認(rèn)為都是值得的。在完成該試驗(yàn)的過(guò)程中，我問(wèn)了同學(xué)和教師，還查閱了很多和鏈表有關(guān)系的書籍，通過(guò)學(xué)習(xí)，翻看以前學(xué)過(guò)的知識(shí)，使我明白了我在學(xué)習(xí)知識(shí)上的很多不足。不過(guò)在此同時(shí)又重新復(fù)習(xí)了課本，從中學(xué)到了許多以前未學(xué)到的知識(shí)，感覺(jué)非常有成就感，讓我對(duì)自己更加有信心，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程也更感興趣了，以前我一直感覺(jué)枯燥難學(xué)的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在我也愿意去認(rèn)真研究學(xué)習(xí)了。這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，多虧了我的指導(dǎo)教師黃磊教師的悉心教誨。在以后的學(xué)習(xí)過(guò)程中，我要認(rèn)真負(fù)責(zé)地對(duì)待課本中的每一個(gè)知識(shí)點(diǎn)，進(jìn)一步充實(shí)自己，提高自己。參考文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M：中國(guó)電力，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解M：中國(guó)電力，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版M. ：清華大學(xué)，20024 X振鵬，X曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M：中國(guó)鐵道，2003附錄：源代碼如下1 用數(shù)組數(shù)據(jù)結(jié)構(gòu)編寫#include<stdio.h>void taozi(int n,int m) int day10; int i; day0=n; for(i=0;i<10-m;i+) dayi+1=2*(dayi+1); printf("第%d天的桃子為:%dn",m,day10-m);void 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: return; break; default: printf("輸入有誤請(qǐng)重新輸入!"); 2 用鏈數(shù)據(jù)結(jié)構(gòu)編寫#include<stdio.h>#include<stdlib.h>#define NULL 0typedef 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(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; printf("第%d天的桃子為:%dn",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)輸入要求第幾天剩下的桃子: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<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100 #define OK 1#define OVERFLOW -2typedef 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; InitStack(); *s.top+=e; for(i=0;i<10-m;i+) *s.top=2*(*(s.top-1)+1); s.top+; printf("第%d天的桃子為:%dn",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("%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<stdio.h>int i=9;int taozi(int x)int y;while(i>0) y=2*(x+1); i-; taozi(y); printf("%dn",y); void main()int a=1;taozi(a);printf("1n");14 / 15