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

1、1、 設(shè)計題目 猴子吃桃子問題 有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。二、運行環(huán)境（軟、硬件環(huán)境）VC+6.0 PC電腦一臺3、 算法的需求分析 1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解2)采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解3)采用遞歸實現(xiàn)上述求解4)如果采用4種方法者,適當加分/用戶界面int Desk(int n) printf(*n);printf(| 歡迎進入猴子吃桃子系統(tǒng) |n);printf(| 1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |n);printf(*n); prin

2、tf(請輸入要選擇的方法: );scanf(%d,&n);getchar();system(cls); /刷新屏幕while(n5)printf(*輸入錯誤 ! 請重新輸入*n);scanf(%d,&n);return n;四、算法概要設(shè)計/采用鏈數(shù)據(jù)結(jié)構(gòu) (棧) 實現(xiàn)上述求解typedef struct int *top; int *base;stack;/初始化一個棧stack Init(stack *s)s-base=(int *)malloc(STACK_SIZE*sizeof(int);if(s-base = NULL)printf(Init failed !n);exit(-1);

3、s-top = s-base;return *s;/二叉樹創(chuàng)建一個大小為DAYS(由用給出)的二叉樹,二叉樹的左孩子節(jié)點存放當天的桃子數(shù)，右節(jié)點存放數(shù)字1，即為多吃的一個桃子。typedef struct TNodeint data;struct TNode *lchild;struct TNode *rchild;tree;/創(chuàng)建一個二叉樹tree CreatTree(tree *T) /T 為指針類型 int n=0,i=0;tree *p,*pr,*T1;T=(tree *)malloc(sizeof(TNode);T1=T;T-data=1; /根節(jié)點內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)fo

4、r(i=1; ilchild=NULL;pr-rchild=NULL;p-data=0;pr-data=1;T1-lchild=p;T1-rchild=pr;T1=p;T1-lchild=NULL;T1-rchild=NULL;return *T; /返回T的地址/算法框架圖打印共摘的桃子數(shù)量判斷是否執(zhí)行完畢 進入猴子吃桃子系統(tǒng)界面 開始 選擇要使用的方法 進入該函數(shù)判斷是否執(zhí)行 完畢 繼續(xù)執(zhí)行 N Y N Y5、 算法詳細設(shè)計#include #include #include peach.h/函數(shù)聲明int Desk(int n);void peach_1(void);stack Init

5、(stack *s);void Push(stack *s,int num);void Pop(stack *s,int &num);void peach_2(stack *s);void peach_3(int n,int i);tree CreatTree(tree *T);void calculate(tree *T);void peach_4(tree *T);int main()int data=0;int n=1,i=1;stack s;tree T;s=Init(&s);T=CreatTree(&T);while(1)switch(Desk(n)case 1:peach_1();

6、break;case 2: peach_2(&s);break;case 3:peach_3(n,i);break;case 4:peach_4(&T);break;case 5:exit(0);break;return 0;/頭文件代碼#define DAYS 10 /定義給定的天數(shù)#define STACK_SIZE 5 /棧的容量,實際只用了一個#define TRUE 1#define ERROR 0void peach_3(int n,int i);/用戶界面int Desk(int n)printf(*n);printf(| 歡迎進入猴子吃桃子系統(tǒng) |n);printf(| 1-數(shù)

7、組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |n);printf(*n);printf(請選擇要使用的方法: );scanf(%d,&n);getchar();system(cls); /刷新屏幕while(n5)printf(*輸入錯誤 ! 請重新輸入*n);scanf(%d,&n);return n;/采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后一天的桃子數(shù)for(i=DAYS ; i0; -i , j=i-1)peachj = 2*(peachi + 1);printf(

8、* * * * * * * * * * * * * * * * * * * * *n);printf(* 數(shù) 組 法 * n);printf(* 這群猴子共摘了 %d 個桃子 *n,peach0);printf(* * * * * * * * * * * * * * * * * * * * *n);/采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解typedef structint *top;int *base;stack;/初始化一個棧stack Init(stack *s)s-base=(int *)malloc(STACK_SIZE*sizeof(int);if(s-base = NULL)printf(In

9、it failed !n);exit(-1);s-top = s-base;return *s;/把當天的桃子數(shù)進棧void Push(stack *s,int num)*s-top+ = 2*(num + 1);/把前一天的桃子數(shù)出棧void Pop(stack *s,int &num) /&num位地址傳遞，可以直接對參數(shù)進行修改num = *-s-top;void peach_2(stack *s)int i=0;int num=0;Push(s,1); /先把最后一天的桃子數(shù)進棧i+;while(i data=1; /根節(jié)點內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)for(i=1; ilchild

10、=NULL;pr-rchild=NULL;p-data=0;pr-data=1;T1-lchild=p;T1-rchild=pr;T1=p;T1-lchild=NULL;T1-rchild=NULL;return *T; /返回T的地址/對二叉樹進行賦值計算void calculate(tree *T)int i=0; tree *T1,*T2,*T3; /T1,T3分別為T2的左右孩子T2=T;for(i=0; ilchild;T3=T2-rchild;T1-data=2*(T2-data + T3-data);T2=T1;/二叉樹遍歷最左下角的孩子節(jié)點void peach_4(tree *

11、T)calculate(T);while(T-lchild != NULL)T=T-lchild;printf(* * * * * * * * * * * * * * * * * * * * *n);printf(* 二 叉 樹 法 *n);printf(* 這群猴子共摘了 %d 個桃子 *n,T-data);printf(* * * * * * * * * * * * * * * * * * * * *n);六、算法的測試 開始函數(shù)功能 ：1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 選擇一個功能 執(zhí)行該功能/主函數(shù)#include #include #include peac

12、h.h/函數(shù)聲明int Desk(int n);void peach_1(void);stack Init(stack *s);void Push(stack *s,int num);void Pop(stack *s,int &num);void peach_2(stack *s);void peach_3(int n,int i);tree CreatTree(tree *T);void calculate(tree *T);void peach_4(tree *T);int main() int data=0; int n=1,i=1; stack s; tree T; s=Init(&

13、s);T=CreatTree(&T); while(1) switch(Desk(n) case 1: peach_1(); break; case 2: peach_2(&s); break; case 3: peach_3(n,i); break; case 4: peach_4(&T); break; case 5: exit(0); break; return 0;/采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解void peach_1(void) int peach50=0; int i=0,j=0; peachDAYS-1=1; /最后一天的桃子數(shù) for(i=DAYS ; i0; -i , j=i

14、-1) peachj = 2*(peachi + 1); printf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 數(shù) 組 法 * n); printf(* 這群猴子共摘了 %d 個桃子 *n,peach0); printf(* * * * * * * * * * * * * * * * * * * * *n);void peach_2(stack *s) int i=0; int num=0; Push(s,1); /先把最后一天的桃子數(shù)進棧i+; while(i lchild != NULL) T=T-lchild; prin

15、tf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 二 叉 樹 法 *n); printf(* 這群猴子共摘了 %d 個桃子 *n,T-data); printf(* * * * * * * * * * * * * * * * * * * * *n);7、 運行結(jié)果分析 1、數(shù)組法：創(chuàng)建一個大小為DAYS的一維數(shù)組aDAYS，a0,a1.aDAYS-1分別存放當天的桃子數(shù)，其中an = 2*(an-1 + 1)。2、 鏈表法：創(chuàng)建一個鏈棧，先把第DAYS天的桃子數(shù)進棧，然后出棧，把出戰(zhàn)的數(shù)據(jù)num進行處理，即num = 2*(num

16、 + 1)，然后繼續(xù)進棧，出棧如此反復(fù)循環(huán)DAYS次結(jié)束。3、遞歸法：首先確定遞歸的終止條件，即i = DAYS（假設(shè)i的初始值為1）,循環(huán)體為fac(n,i+1),在遞歸過程中對n進行如下處理，n=2*(n + 1)。4、 二叉樹法：創(chuàng)建一個大小為DAYS的二叉樹，其中根節(jié)點為第DAYS天的桃子數(shù)，其中根節(jié)點的左孩子為上一天的桃子數(shù)，右孩子只存一個固定數(shù)據(jù)，即數(shù)字1。對二叉樹作如下處理，對于一個根節(jié)點，其左孩子 = 2 *（根節(jié)點 + 右孩子）。經(jīng)過一系列的調(diào)試運行，該程序可以正確執(zhí)行，并能夠按要求完成任務(wù)。8、 收獲及體會 通過設(shè)計猴子吃桃子這一程序，是我對C語言以及數(shù)據(jù)結(jié)構(gòu)有了更深的了解，通過編寫代碼，是我學(xué)習(xí)和掌握了C的理論知識和實踐程序設(shè)計的各種技能。 在編寫代碼時也遇到了很多麻煩，例如在用遞歸編寫時，突然忘了遞歸在系統(tǒng)棧內(nèi)是如何運行的，于是我向同