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

目 錄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)境23.2軟件環(huán)境24、 詳細(xì)設(shè)計(jì)24.1系統(tǒng)流程圖24.2用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解34.3用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解44.4用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)求解54.5用遞歸實(shí)現(xiàn)上述求解65、 調(diào)試分析76、運(yùn)行結(jié)果7課程設(shè)計(jì)總結(jié)8參考文獻(xiàn)9附錄：91、需求分析1、 猴子吃桃子問題有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(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ì)2.1.用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解 在taozi函數(shù)中定義一個(gè)一維數(shù)組，分別存儲(chǔ)每天的桃子個(gè)數(shù)，根據(jù)題目的內(nèi)容找出各個(gè)數(shù)之間的關(guān)系，用數(shù)組元素表示出來，根據(jù)用戶輸入要計(jì)算哪一天的桃子，用for循環(huán)控制結(jié)束。在main函數(shù)中讓用戶輸入要計(jì)算的哪一天，調(diào)用taozi函數(shù)，以便用戶可查出任意一天的桃子個(gè)數(shù)，用switch語句判斷用戶要執(zhí)行的功能，然后用while循環(huán)控制，直到用戶輸入0為止。2.2.用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解 先寫出預(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)結(jié)束的語句，最后再用main函數(shù)去調(diào)用Push函數(shù)。2.4 用遞歸實(shí)現(xiàn)上述求解 這種方法跟上述幾種不同，在函數(shù)的執(zhí)行函數(shù)的過程中，需多次進(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)語句，比上幾種方法簡(jiǎn)單點(diǎn)。3、 運(yùn)行環(huán)境3.1 硬件環(huán)境PC3.2軟件環(huán)境（1）Windows XP（2）Microsoft Visual C+6.04、 詳細(xì)設(shè)計(jì)4.1系統(tǒng)流程圖猴子吃桃問題的實(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)4.2用數(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;inext=NULL;/創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表 L-next=p;/插入到表頭 L-next-data=e;/初始化第一個(gè)結(jié)點(diǎn) for(i=m-1;i0;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);4.4用棧數(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;/剛開始棧為空 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;i0) 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í)沒有顯示錯(cuò)誤，但輸出不是預(yù)測(cè)的結(jié)果，代碼如下： for(i=m-1;i0;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)的過程中，雖然只有一個(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é)果：課程設(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í)踐之間的差別。這就告訴了我們?cè)谝院蟮膶W(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é)和老師，還查閱了很多和鏈表有關(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)老師黃磊老師的悉心教導(dǎo)。在以后的學(xué)習(xí)過程中，我要認(rèn)真負(fù)責(zé)地對(duì)待課本中的每一個(gè)知識(shí)點(diǎn)，進(jìn)一步充實(shí)自己，提高自己。參考文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解M北京：中國電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國鐵道出版社，2003附錄： 源代碼如下1 用數(shù)組數(shù)據(jù)結(jié)構(gòu)編寫#includevoid taozi(int n,int m) int day10; int i; day0=n; for(i=0;i10-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#include#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;i0;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#include#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;i10-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) ca