1、猴子吃桃问题数据结构课程设计一、设计题目 猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二、运行环境（软、硬件环境）VC+6.0 PC电脑一台三、算法的需求分析 1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种方法者,适当加分/用户界面int Desk(int n) printf(*n); printf(| 欢迎进入猴子吃桃子系统 |n); printf(| 1-数组法 2-链表法 3-递归法 4-二叉树法 5-退出 |n); p
2、rintf(*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(
3、Init failed !n); exit(-1); s-top = s-base; return *s;/二叉树创建一个大小为DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右节点存放数字1，即为多吃的一个桃子。typedef struct TNode int 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
4、=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 Y五、算法详细设计#include #include #include peach.h/函数声明int Desk(int n);void peach_1(void);stack Init(stack *s);void P
5、ush(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;
6、 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); pri
7、ntf(| 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 =
8、 2*(peachi + 1); printf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 数 组 法 * n); printf(* 这群猴子共摘了 %d 个桃子 *n,peach0); printf(* * * * * * * * * * * * * * * * * * * * *n);/采用链数据结构实现上述求解typedef struct int *top; int *base;stack;/初始化一个栈stack Init(stack *s) s-base=(int *)malloc(STACK_SIZE*sizeof(i
9、nt); 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 d
10、ata=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
11、-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);六、算法的测试/主函数#include #includ
12、e #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; t
13、ree 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
14、 ; 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
15、=T-lchild; printf(* * * * * * * * * * * * * * * * * * * * *n); printf(* 二 叉 树 法 *n); printf(* 这群猴子共摘了 %d 个桃子 *n,T-data); printf(* * * * * * * * * * * * * * * * * * * * *n);七、运行结果分析 1、数组法：创建一个大小为DAYS的一维数组aDAYS，a0,a1.aDAYS-1分别存放当天的桃子数，其中an = 2*(an-1 + 1)。2、链表法：创建一个链栈，先把第DAYS天的桃子数进栈，然后出栈，把出战的数据num进行处理，
16、即num = 2*(num + 1)，然后继续进栈，出栈如此反复循环DAYS次结束。3、递归法：首先确定递归的终止条件，即i = DAYS（假设i的初始值为1）,循环体为fac(n,i+1),在递归过程中对n进行如下处理，n=2*(n + 1)。4、二叉树法：创建一个大小为DAYS的二叉树，其中根节点为第DAYS天的桃子数，其中根节点的左孩子为上一天的桃子数，右孩子只存一个固定数据，即数字1。对二叉树作如下处理，对于一个根节点，其左孩子 = 2 *（根节点 + 右孩子）。经过一系列的调试运行，该程序可以正确执行，并能够按要求完成任务。八、收获及体会 通过设计猴子吃桃子这一程序，是我对C语言以及
17、数据结构有了更深的了解，通过编写代码，是我学习和掌握了C的理论知识和实践程序设计的各种技能。 在编写代码时也遇到了很多麻烦，例如在用递归编写时，突然忘了递归在系统栈内是如何运行的，于是我向同学和老师虚心请教。另外在用二叉树时，根节点T总是没有正确定位，使其成为了野指针。 总而言之，通过这一课程设计的学习，我对C程序有了更深的认识。我深信，一个良好的程序员需要不断去敲写代码，在实践中总结经验，从而提高自己的综合实践能力，去为社会最初更大的奉献。 最后我要感谢我的同学以及汪文彬老师对我的帮助，我所取得的进步与他们的热心帮助是离不开的。九、主要参考文献：1苏小红 C语言 大学实用教程 (第二版) 电子工业出版社2数据结构 C语言版 严蔚敏 清华大学出版社3 C 程序设计 谭浩强 第三版 清华大学出版社
