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

一、设计题目猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二、运行环境（软、硬件环境）VC++6.0PC电脑一台三、算法的需求分析1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种方法者,适当加分//用户界面intDesk(intn){printf(**************************************************\n);printf(|欢迎进入猴子吃桃子系统|\n);printf(|1-数组法2-链表法3-递归法4-二叉树法5-退出|\n);printf(***************************************************\n);printf(请输入要选择的方法:);scanf(%d,&n);getchar();system(cls);//刷新屏幕while(n1||n5){printf(***输入错误!请重新输入***\n);scanf(%d,&n);}returnn;}四、算法概要设计//采用链数据结构(栈)实现上述求解typedefstruct{int*top;int*base;}stack;//初始化一个栈stackInit(stack*s){s-base=(int*)malloc(STACK_SIZE*sizeof(int));if(s-base==NULL){printf(Initfailed!\n);exit(-1);}s-top=s-base;return*s;}//二叉树创建一个大小为DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右节点存放数字1，即为多吃的一个桃子。typedefstructTNode{intdata;structTNode*lchild;structTNode*rchild;}tree;//创建一个二叉树treeCreatTree(tree*T)//T为指针类型{intn=0,i=0;tree*p,*pr,*T1;T=(tree*)malloc(sizeof(TNode));T1=T;T-data=1;//根节点内的数据为第DAYS天的桃子数for(i=1;iDAYS;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-rchild=NULL;return*T;//返回T的地址}//算法框架图NYNY打印共摘的桃子数量判断是否执行完毕进入猴子吃桃子系统界面开始选择要使用的方法进入该函数判断是否执行完毕继续执行五、算法详细设计#includestdio.h#includestdlib.h#includepeach.h//函数声明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){intdata=0;intn=1,i=1;stacks;treeT;s=Init(&s);T=CreatTree(&T);while(1){switch(Desk(n)){case1:peach_1();break;case2:peach_2(&s);break;case3:peach_3(n,i);break;case4:peach_4(&T);break;case5:exit(0);break;}}return0;}//头文件代码#defineDAYS10//定义给定的天数#defineSTACK_SIZE5//栈的容量,实际只用了一个#defineTRUE1#defineERROR0voidpeach_3(intn,inti);//用户界面intDesk(intn){printf(**************************************************\n);printf(|欢迎进入猴子吃桃子系统|\n);printf(|1-数组法2-链表法3-递归法4-二叉树法5-退出|\n);printf(***************************************************\n);printf(请选择要使用的方法:);scanf(%d,&n);getchar();system(cls);//刷新屏幕while(n1||n5){printf(***输入错误!请重新输入***\n);scanf(%d,&n);}returnn;}//采用数组数据结构实现上述求解voidpeach_1(void){intpeach[50]={0};inti=0,j=0;peach[DAYS-1]=1;//最后一天的桃子数for(i=DAYS;i0;--i,j=i-1){peach[j]=2*(peach[i]+1);}printf(*********************\n);printf(*数组法*\n);printf(*这群猴子共摘了%d个桃子*\n,peach[0]);printf(*********************\n);}//采用链数据结构实现上述求解typedefstruct{int*top;int*base;}stack;//初始化一个栈stackInit(stack*s){s-base=(int*)malloc(STACK_SIZE*sizeof(int));if(s-base==NULL){printf(Initfailed!\n);exit(-1);}s-top=s-base;return*s;}//把当天的桃子数进栈voidPush(stack*s,intnum){*s-top++=2*(num+1);}//把前一天的桃子数出栈voidPop(stack*s,int&num)//&num位地址传递，可以直接对参数进行修改{num=*--s-top;}voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子数进栈i++;while(iDAYS){Pop(s,num);Push(s,num);i++;}printf(*********************\n);printf(*链表法*\n);printf(*这群猴子共摘了%d个桃子*\n,num);printf(*********************\n);}voidpeach_3(intn,inti){if(i==DAYS)//DAYS为递归终止条件由用户给出{printf(*********************\n);printf(*递归法*\n);printf(*这群猴子共摘了%d个桃子*\n,n);printf(*********************\n);}else{n=2*(n+1);peach_3(n,i+1);}}//二叉树typedefstructTNode{intdata;structTNode*lchild;structTNode*rchild;}tree;treeCreatTree(tree*T)//T为指针类型{intn=0,i=0;tree*p,*pr,*T1;T=(tree*)malloc(sizeof(TNode));T1=T;T-data=1;//根节点内的数据为第DAYS天的桃子数for(i=1;iDAYS;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-rchild=NULL;return*T;//返回T的地址}//对二叉树进行赋值计算voidcalculate(tree*T){inti=0;tree*T1,*T2,*T3;//T1,T3分别为T2的左右孩子T2=T;for(i=0;iDAYS-1;i++){T1=T2-lchild;T3=T2-rchild;T1-data=2*(T2-data+T3-data);T2=T1;}}//二叉树遍历最左下角的孩子节点voidpeach_4(tree*T){calculate(T);while(T-lchild!=NULL){T=T-lchild;}printf(*********************\n);printf(*二叉树法*\n);printf(*这群猴子共摘了%d个桃子*\n,T-data);printf(*********************\n);}六、算法的测试//主函数#includestdio.h#includestdlib.h#includepeach.h//函数声明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){intdata=0;intn=1,i=1;stacks;treeT;s=Init(&s);T=CreatTree(&T);while(1){switch(Desk(n)){case1:peach_1();开始函数功能：1-数组法2-链表法3-递归法4-二叉树法5-退出选择一个功能执行该功能break;case2:peach_2(&s);break;case3:peach_3(n,i);break;case4:peach_4(&T);break;case5:exit(0);break;}}return0;}//采用数组数据结构实现上述求解voidpeach_1(void){intpeach[50]={0};inti=0,j=0;peach[DAYS-1]=1;//最后一天的桃子数for(i=DAYS;i0;--i,j=i-1){peach[j]=2*(peach[i]+1);}printf(*********************\n);printf(*数组法*\n);printf(*这群猴子共摘了%d个桃子*\n,peach[0]);printf(*********************\n);}voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子数进栈i++;while(iDAYS){Pop(s,num);Push(s,num);i++;}printf(*********************\n);printf(*链表法*\n);printf(*这群猴子共摘了%d个桃子*\n,num);printf(*********************\n);