《猴子吃桃问题大数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《猴子吃桃问题大数据结构课程设计.doc（16页珍藏版）》请在三一文库上搜索。
1、一、 设计题目猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一 个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共 摘了多少个桃子。二、运行环境（软、硬件环境）VC+6.0 PC 电脑一台三、算法的需求分析1）采用数组数据结构实现上述求解2）采用链数据结构实现上述求解3）采用递归实现上述求解4）如果采用4种方法者,适当加分 用户界面int Desk(i nt n)printf(”* n");printf("|欢迎进入猴子吃桃子系统|n");printf（"|1-数组法2-链表法3-递归法4-二叉树法5-退出|n&
2、quot;）;* n");printf(printf（"请输入要选择的方法："）;scan f("%d", &n);getchar();system("cls");/ 刷新屏幕while( n<1| n >5)printf("*输入错误！请重新输入*n");sca nf("%d",&n); return n;四、算法概要设计/采用链数据结构（栈）实现上述求解typedef structint *top;int *base;stack;/初始化一个栈stack
3、 In it(stack *s) s->base=(i nt *)malloc(STACK_SIZE*sizeof(i nt); 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
4、;tree;/创建一个二叉树tree CreatTree(tree *T) /T为指针类型int n=0,i=0;tree *p,*pr,*T1;T=(tree *)malloc(sizeof(TNode);T仁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->l
5、child=p;T1->rchild=pr;T1=p;T1->lchild=NULL;T1->rchild=NULL;return *T; / 返回T的地址/算法框架图N> 继续执行五、算法详细设计#i nclude <stdio.h>#in elude <stdlib.h>#in elude "peach.h"/函数声明int Desk(i nt n);void peach_1(void);stack In it(stack *s);void Push(stack *s,i nt n um);void Pop(stack *
6、s,i nt &n um);void peach_2(stack *s);void peach_3(i nt n ,i nt i); tree CreatTree(tree *T);void calculate(tree *T);void peach_4(tree *T);int mai n()int data=0;int n=1,i=1;stack s;tree T;s=I nit (&s);T=CreatTree(&T); while(1)switch(Desk (n)case 1:peach_1();break;case 2:peach_2(&s);bre
7、ak;case 3:peach_3( n,i);break;case 4:peach_4(&T);break;case 5:exit(0);break; return 0;/头文件代码#defi ne DAYS 10 /定义给定的天数#define STACK_SIZE 5 /栈的容量,实际只用了一个#defi ne TRUE 1#defi ne ERROR 0 void peach_3(i nt n ,i nt i);/用户界面 int Desk(i nt n)I*prin tf（"|欢迎进入猴子吃桃子系统|n"）;printf（"| 1- 数组法2-链
8、表法3-递归法4-二叉树法5-退岀|n"）;I *printf（”请选择要使用的方法："）;sca nf("%d",&n); getchar();刷新屏幕system("cls"); /while( n<1 | n>5)printf("*输入错误！请重新输入*n");sca nf("%d",&n);return n;/采用数组数据结构实现上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后
9、一天的桃子数for(i=DAYS ; i>0; -i , j=i-1)peachj = 2*(peachi + 1);printf('I* * *n");* n");prin tf("*printf("*这群猴子共摘了%d个桃子*n",peach0);printf('I*n");/采用链数据结构实现上述求解 typedef structint *top;int *base;stack;/初始化一个栈stack In it(stack *s)*n");链表法这群猴子共摘了 %d个桃子printf('
10、;I*n");* n");*n",n um);void peach_3(i nt n ,i nt i)if(i =DAYS) /DAYS为递归终止条件由用户给出prin tf("* * * * * * * * * * * * * * * * * * * * *n");prin tf("*n");prin tf("*这群猴子共摘了 %d个桃子*n",n);s->base=(i nt *)malloc(STACK_SIZE*sizeof(i nt); if(s->base = NULL)print
11、f("Init failed !n");exit(-1);s->top = s->base;return *s;/把当天的桃子数进栈void Push(stack *s,i nt n um)*s->top+ = 2*( num + 1);/把前一天的桃子数岀栈void Pop(stack *s,i nt &n um) &n um位地址传递，可以直接对参数进行修改num = *-s->top; void peach_2(stack *s) int i=0;int n um=0;Push(s,1); /先把最后一天的桃子数进栈i+;whi
12、le(i < DAYS)Pop(s ,n um);Push(s ,n um);i+;prin tf("* * *prin tf("*prin tf("*prin tf("* * * * * * * * * * * * * * * * * * * * *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为
13、指针类型int n=0,i=0;tree *p,*pr,*T1;T=(tree *)malloc(sizeof(TNode);T仁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->lchi
14、ld=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; ivDAYS-1; i+)T仁 T2->lchild;T3=T2->rchild;T1->data=2*(T2->data + T3->data);T2=T1;/二叉树遍历最左下角的孩子节点 void peach_4(tree *T) calculate(T); while(T->lch
15、ild != NULL) T=T->lchild;printf("* * * * * * * * * * * * * * * * * * * * *n “);prin tf("*二 叉树 法 *n");printf("*这群猴子共摘了%d个桃子*n",T->data);printf("* * * * * * * * * * * * * * * * * * * * *n");六、算法的测试开始/主函数#i nclude <stdio.h>#in clude <stdlib.h>#in clu
16、de "peach.h"/函数声明int Desk(i nt n);void peach_1(void); stack In it(stack *s);void Push(stack *s,i nt n um); void Pop(stack *s,i nt &n um);void peach_2(stack *s); void peach_3(i nt n ,i nt i); tree CreatTree(tree *T); void calculate(tree *T);void peach_4(tree *T);int mai n()int data=0;in
17、t n=1,i=1;函数功能：1-数组法2-链表法3-递归法4-二叉树法5-退出1T选择一个功能1执行该功能stack s;tree T;s=I ni t(&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(O); break;return 0;rC:UMrsXAdm i nist rat orDes
18、ktop5S-F 吃忌 Fl习 Debu g 憔子吃桃子问融曲甘2 U U' Tsf kJ寸 Rj UJ u ui w W U! W U &J! W U! U kl" U U U U U U IT U wj“ j R-F!、，囂世址兄軒吃桃子糸统，、! ' i-数组送2-議表法3-翁归法4-_文树法5退出!青选择要使用的方春/采用数组数据结构实现上述求解void peach_1(void)int peach50=0;int i=0,j=0;peachDAYS-1=1; /最后一天的桃子数for(i=DAYS ; i>0; -i , j=i-1) peac
19、hj = 2*(peachi + 1);pri ntf("* pri ntf("* pri ntf("* pri ntf("* * * * * * * * * * * * * * * * * * * *n");数 组 法* n");这群猴子共摘了d个桃子*n",peach0);* * * * * * * * * * * * * * * * * * * *n");品0U5ef3Admini5trdtorD«lrtop撫刊瑚子问斑Mbug便子瞅子问肛时14牖赢囂个桃子 :void peach_2(stack
20、*s) -int i=0;int num=0;Push(s,1); /先把最后一天的桃子数进栈i+；while(i < DAYS)Pop(s ,nu m);Push(s ,nu m); i+;printf(* * *n “);printf("*链printf("*这群猴子共摘了%d个桃子* n");*n", nu m);printf("* * *n");T:U那Wmini丸妣RDMo卩普刊?好寸悬Debu漕弼桃壬氐歆ht递離茯摘了 1«4个解 ”姜碁甚養旻鼻萎豪*長餐畀萎*豊*吳 « « «
21、;void peach_3(i nt n ,i nt i) if(i =DAYS) /DAYS为递归终止条件由用户给岀printf(“* * *n");pri ntf("*pri ntf("*这群猴子共摘了法%d个桃子* n");*n", n);*n");pri ntf("* * * * * * * * * elsen = 2*( n + 1);peach_3( n,i+1); /循环体/二叉树遍历最左下角的孩子节点 void peach_4(tree *T)calculate(T);while (T->lchild
22、!= NULL)T=T->lchild;printf(“ printf(“ printf(“ printf(“ * * *n");叉树 法 *n");这群猴子共摘了%d个桃子 *n",T->data);* * * * * * * * *n");1 C:U se rsAdm inistr ato rD eskto p堞fO t子闫驗De bu g 谯申fe 馳召軀,exe1*诵猴子棘了豪»#* «* * Kf J Kn* Ar * » r- X I; diHifip 3 Mr3 « lx七、运行结果分析1
23、、数组法：创建一个大小为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天的桃子数， 其中根节点的左孩子为上一
24、天的桃子数，右孩子只存一个固定数据，即数字1。对二叉树作如下处理，对于一个根节点，其左孩子=2 * (根节点+右孩子)。经过一系列的调试运行，该程序可以正确执行，并能够按要求完成任务八、收获及体会通过设计猴子吃桃子这一程序，是我对 C语言以及数据结构有了更深的了解，通 过编写代码，是我学习和掌握了 C的理论知识和实践程序设计的各种技能。在编写代码时也遇到了很多麻烦，例如在用递归编写时，突然忘了递归在系统栈内是如何运行的，于是我向同学和老师虚心请教。另外在用二叉树时，根节点T总是没有正确定位，使其成为了野指针。总而言之，通过这一课程设计的学习，我对 C程序有了更深的认识。我深信，一个 良好的程序员需要不断去敲写代码，在实践中总结经验，从而提高自己的综合实践能力， 去为社会最初更大的奉献。最后我要感谢我的同学以及汪文彬老师对我的帮助，我所取得的进步与他们的热心 帮助是离不开的。九、主要参考文献:1 苏小红C语言大学实用教程(第二版)电子工业出版社2 数据结构C语言版 严蔚敏清华大学出版社3 C 程序设计 谭浩强 第三版 清华大学出版社