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

1、 设计题目 猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二、运行环境（软、硬件环境）VC+6.0 PC电脑一台3、 算法的需求分析 1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种方法者,适当加分/用户界面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(n5)printf(*输入错误 ! 请重新输入*n);scanf(%d,&n);return 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);s-top = s-base;return *s;/二叉树创建一个大小为DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右节点存放数字1，即为多吃的一个桃子。typedef struct TNodeint data;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; 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的地址/算法框架图打印共摘的桃子数量判断是否执行完毕 进入猴子吃桃子系统界面 开始 选择要使用的方法 进入该函数判断是否执行 完毕 继续执行 N Y N Y5、 算法详细设计#include #include #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);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();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);/用户界面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(n5)printf(*输入错误 ! 请重新输入*n);scanf(%d,&n);return n;/采用数组数据结构实现上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后一天的桃子数for(i=DAYS ; i0; -i , j=i-1)peachj = 2*(peachi + 1);printf(* * * * * * * * * * * * * * * * * * * * *n);printf(* 数 组 法 * n);printf(* 这群猴子共摘了 %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 = 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 data=1; /根节点内的数据为第DAYS天的桃子数for(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的地址/对二叉树进行赋值计算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;/二叉树遍历最左下角的孩子节点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);六、算法的测试 开始函数功能 ：1-数组法 2-链表法 3-递归法 4-二叉树法 5-退出 选择一个功能 执行该功能/主函数#include #include #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);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(); 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 peach50=0; int i=0,j=0; peachDAYS-1=1; /最后一天的桃子数 for(i=DAYS ; i0; -i , j=i-1) peachj = 2*(peachi + 1); printf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 数 组 法 * n); printf(* 这群猴子共摘了 %d 个桃子 *n,peach0); printf(* * * * * * * * * * * * * * * * * * * * *n);void peach_2(stack *s) int i=0; int num=0; Push(s,1); /先把最后一天的桃子数进栈i+; while(i lchild != NULL) T=T-lchild; printf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 二 叉 树 法 *n); printf(* 这群猴子共摘了 %d 个桃子 *n,T-data); printf(* * * * * * * * * * * * * * * * * * * * *n);7、 运行结果分析 1、数组法：创建一个大小为DAYS的一维数组aDAYS，a0,a1.aDAYS-1分别存放当天的桃子数，其中an = 2*(an-1 + 1)。2、 链表法：创建一个链栈，先把第DAYS天的桃子数进栈，然后出栈，把出战的数据num进行处理，即num = 2*(num + 1)，然后继续进栈，出栈如此反复循环DAYS次结束。3、递归法：首先确定递归的终止条件，即i = DAYS（假设i的初始值为1）,循环体为fac(n,i+1),在递归过程中对n进行如下处理，n=2*(n + 1)。4、 二叉树法：创建一个大小为DAYS的二叉树，其中根节点为第DAYS天的桃子数，其中根节点的左孩子为上一天的桃子数，右孩子只存一个固定数据，即数字1。对二叉树作如下处理，对于一个根节点，其左孩子 = 2 *（根节点 + 右孩子）。经过一系列的调试运行，该程序可以正确执行，并能够按要求完成任务。8、 收获及体会 通过设计猴子吃桃子这一程序，是我对C语言以及数据结构有了更深的了解，通过编写代码，是我学习和掌握了C的理论知识和实践程序设计的各种技能。 在编写代码时也遇到了很多麻烦，例如在用递归编写时，突然忘了递归在系统栈内是如何运行的，于是我向同