猴子吃桃问题数据结构课程设计

1、1、 设计题目  猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二、运行环境（软、硬件环境）VC+6.0 PC电脑一台3、 算法的需求分析 1) 采用数组数据结构实现上述求解2) 采用链数据结构实现上述求解3) 采用递归实现上述求解4) 如果采用4种方法者,适当加分/用户界面int Desk(int n) printf("*n");printf("| 欢迎进入猴子吃桃子系统 |n");print

2、f("| 1-数组法 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;四、算法概要设计/采用链数据结构 (栈) 实现上述求解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;/二叉树创建一个大小为DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右节点存放数字1，即为多吃的一个桃子。typedef struct TNodeint d

4、ata;struct TNode *lchild;struct TNode *rchild;tree;/创建一个二叉树tree CreatTree(tree *T) /T 为指针类型 int n=0,i=0;tree *p,*pr,*T1;T=(tree *)malloc(sizeof(TNode);T1=T;T->data=1; /根节点内的数据为第DAYS天的桃子数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的地址/算法框架图打印共摘的桃子数量判断是否执行完毕 进入猴子吃桃子系统界面 开始 选择要使用的方法 进入该函数判断是否执行 完毕 继续执行 N Y N Y5、 算法详细设计#include <stdio.h>#include <stdlib.h>#include "peach.h"/函数声明

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 /定义给定的天数#define STACK_SIZE 5 /栈的容量,实际只用了一个#define TRUE 1#define ERROR 0void peach_3(int n,int i);/用户

8、界面int Desk(int n)printf("*n");printf("| 欢迎进入猴子吃桃子系统 |n");printf("| 1-数组法 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;/采用数组数据结构实现上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后一天的桃子数for(i=DAYS ; i>0; -i , j=i-1)peachj = 2*(peachi + 1);printf("* * * * * * * * * * * * * * * * * * * * *n");printf("* 数 组 法 * n");printf("*

10、 这群猴子共摘了 %d 个桃子 *n",peach0);printf("* * * * * * * * * * * * * * * * * * * * *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;/把当天的桃子数进栈void Push(stack *s,int num)*s->top+ = 2*(num + 1);/把前一天的桃子数出栈void Pop(stack *s,int &num) /&num位地址传递，可以直接对参数进行修改num = *-s->top;void peach_2(stack *s)int i=0;int num=0;Push(s,1); /先把最后一天的桃子数进栈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; /根节点内的数据为第DAYS天的桃子数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的地址/对二叉树进行赋值计算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;/二叉树遍历最左下角的孩子节点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");六、算法的测试 开始函数功能 ：1-数组法 2-链表法 3-递归法 4-二叉树法 5-退出 选择一个功能 执行该功能/主函数#include <stdio.

17、h>#include <stdlib.h>#include "peach.h"/函数声明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;/采用数组数据结构实现上述求解void peach_1(void) int

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

20、* * * *n");void peach_2(stack *s) int i=0; int num=0; Push(s,1); /先把最后一天的桃子数进栈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); /循环体 /二叉树遍历最左下角的孩子节点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、 运行结果分析 1、数组法：创建一个大小为DAYS的一维数组aDAYS，a0,