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

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

2、f("| 1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |n");printf("*n"); printf("請輸入要選擇的方法: ");scanf("%d",&n);getchar();system("cls"); /刷新屏幕while(n<1 | n>5)printf("*輸入錯誤 ! 請重新輸入*n");scanf("%d",&n);return n;四、算法概要設(shè)計/采用鏈數(shù)據(jù)結(jié)構(gòu) (棧) 實(shí)現(xiàn)上述求解ty

3、pedef 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);s->top = s->base;return *s;/二叉樹創(chuàng)建一個大小為DAYS(由用給出)的二叉樹,二叉樹的左孩子節(jié)點(diǎn)存放當(dāng)天的桃子數(shù)，右節(jié)點(diǎn)存放數(shù)字1，即為多吃的一個桃子。typedef struct TNodeint d

4、ata;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é)點(diǎn)內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)for(i=1; i<DAYS; i+)p=(tree *)malloc(sizeof(TNode);pr=(tree *)malloc(sizeof(TNode);pr->lchild=NULL;pr->

5、;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í)行完畢 進(jìn)入猴子吃桃子系統(tǒng)界面 開始 選擇要使用的方法 進(jìn)入該函數(shù)判斷是否執(zhí)行 完畢 繼續(xù)執(zhí)行 N Y N Y5、 算法詳細(xì)設(shè)計#include <stdio.h>#include <stdlib.h>#include "peach.h"/函數(shù)聲明

6、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(&s);T=

7、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;/頭文件代碼#define DAYS 10 /定義給定的天數(shù)#define STACK_SIZE 5 /棧的容量,實(shí)際只用了一個#define TRUE 1#define ERROR 0void peach_3(int n,int i);/用戶

8、界面int Desk(int n)printf("*n");printf("| 歡迎進(jìn)入猴子吃桃子系統(tǒng) |n");printf("| 1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |n");printf("*n");printf("請選擇要使用的方法: ");scanf("%d",&n);getchar();system("cls"); /刷新屏幕while(n<1 | n>5)printf("*輸入錯誤 ! 請

9、重新輸入*n");scanf("%d",&n);return n;/采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后一天的桃子數(shù)for(i=DAYS ; i>0; -i , j=i-1)peachj = 2*(peachi + 1);printf("* * * * * * * * * * * * * * * * * * * * *n");printf("* 數(shù) 組 法 * n");printf("*

10、 這群猴子共摘了 %d 個桃子 *n",peach0);printf("* * * * * * * * * * * * * * * * * * * * *n");/采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(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("Init failed !n");exit(-1);s->top =

11、 s->base;return *s;/把當(dāng)天的桃子數(shù)進(jìn)棧void Push(stack *s,int num)*s->top+ = 2*(num + 1);/把前一天的桃子數(shù)出棧void Pop(stack *s,int &num) /&num位地址傳遞，可以直接對參數(shù)進(jìn)行修改num = *-s->top;void peach_2(stack *s)int i=0;int num=0;Push(s,1); /先把最后一天的桃子數(shù)進(jìn)棧i+;while(i < DAYS)Pop(s,num);Push(s,num);i+;printf("* *

12、* * * * * * * * * * * * * * * * * * *n");printf("* 鏈 表 法 * n");printf("* 這群猴子共摘了 %d 個桃子 *n",num);printf("* * * * * * * * * * * * * * * * * * * * *n");void peach_3(int n,int i)if(i =DAYS) /DAYS 為遞歸終止條件 由用戶給出printf("* * * * * * * * * * * * * * * * * * * * *n&quo

13、t;);printf("* 遞 歸 法 *n");printf("* 這群猴子共摘了 %d 個桃子 *n",n);printf("* * * * * * * * * * * * * * * * * * * * *n");elsen = 2*(n + 1); peach_3(n,i+1);/二叉樹typedef struct TNodeint data;struct TNode *lchild;struct TNode *rchild;tree;tree CreatTree(tree *T) /T 為指針類型 int n=0,i=0;t

14、ree *p,*pr,*T1;T=(tree *)malloc(sizeof(TNode);T1=T;T->data=1; /根節(jié)點(diǎn)內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)for(i=1; i<DAYS; i+)p=(tree *)malloc(sizeof(TNode);pr=(tree *)malloc(sizeof(TNode);pr->lchild=NULL;pr->rchild=NULL;p->data=0;pr->data=1;T1->lchild=p;T1->rchild=pr;T1=p;T1->lchild=NULL;T1->r

15、child=NULL;return *T; /返回T的地址/對二叉樹進(jìn)行賦值計算void calculate(tree *T)int i=0; tree *T1,*T2,*T3; /T1,T3分別為T2的左右孩子T2=T;for(i=0; i<DAYS-1; i+)T1=T2->lchild;T3=T2->rchild;T1->data=2*(T2->data + T3->data);T2=T1;/二叉樹遍歷最左下角的孩子節(jié)點(diǎn)void peach_4(tree *T)calculate(T);while(T->lchild != NULL)T=T-&g

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

17、h>#include <stdlib.h>#include "peach.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);in

18、t 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(); 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)實(shí)現(xiàn)上述求解void peach_1(void) int

19、 peach50=0; int i=0,j=0; peachDAYS-1=1; /最后一天的桃子數(shù) for(i=DAYS ; i>0; -i , j=i-1) peachj = 2*(peachi + 1); printf("* * * * * * * * * * * * * * * * * * * * *n"); printf("* 數(shù) 組 法 * n"); printf("* 這群猴子共摘了 %d 個桃子 *n",peach0); printf("* * * * * * * * * * * * * * * * *

20、* * * *n");void peach_2(stack *s) int i=0; int num=0; Push(s,1); /先把最后一天的桃子數(shù)進(jìn)棧i+; while(i < DAYS) Pop(s,num); Push(s,num); i+; printf("* * * * * * * * * * * * * * * * * * * * *n"); printf("* 鏈 表 法 * n"); printf("* 這群猴子共摘了 %d 個桃子 *n",num); printf("* * * * *

21、* * * * * * * * * * * * * * * *n");void peach_3(int n,int i) if(i =DAYS) /DAYS 為遞歸終止條件 由用戶給出 printf("* * * * * * * * * * * * * * * * * * * * *n"); printf("* 遞 歸 法 * n"); printf("* 這群猴子共摘了 %d 個桃子 *n",n); printf("* * * * * * * * * * * * * * * * * * * * *n")

22、; else n = 2*(n + 1); peach_3(n,i+1); /循環(huán)體 /二叉樹遍歷最左下角的孩子節(jié)點(diǎn)void peach_4(tree *T) calculate(T); while(T->lchild != NULL) T=T->lchild; printf("* * * * * * * * * * * * * * * * * * * * *n"); printf("* 二 叉 樹 法 *n"); printf("* 這群猴子共摘了 %d 個桃子 *n",T->data); printf("* * * * * * * * * * * * * * * * * * * * *n");7、 運(yùn)行結(jié)果分析 1、數(shù)組法：創(chuàng)建一個大小為DAYS的一維數(shù)組aDAYS，a0,