猴子吃桃子问题 课程设计

1、课 程 设 计课程设计名称： 算法分析与综合课程设计 专 业 班 级 ： 计 科0604 学 生 姓 名 ： 高 丽 学 号 ： 20064140427 指 导 教 师 ： 白 浩 课程设计时间： 2008年6月27日 1）需求分析 该程序已知第十天的桃子个数，第一天桃子个数与下一天的之间的关系，要求刚开始桃子的个数。要求用数组，链和递归等其它方法实现。2）概要设计2.1.用数组数据结构实现上述求解 在taozi函数中定义一个一维数组，分别存储每天的桃子个数，根据题目的内容找出各个数之间的关系，用数组元素表示出来，根据用户输入要计算哪一天的桃子，用for循环控制结束。在main函数中让用户输入

2、要计算的哪一天，调用taozi函数，以便用户可查出任意一天的桃子个数，用switch语句判断用户要执行的功能，然后用while循环控制，直到用户输入0为止。2.2.用链数据结构实现上述求解 先写出预定义常量和类型，写出结点的类型定义，创建结点，初始化链表，定义变量并初始化，找出结点与其后继结点之间的联系，然后在主函数中控制。2.3 用栈数据结构实现求解 本部分包括预定义常量和类型，顺序栈的定义，initstack函数，push函数，和main函数，在initstack函数构造一个空栈，在push函数中调用该函数，并在其中编写控制栈顶指针和栈底指针移动的语句，找出指针所指向的数据之间的关系，在m

3、ain函数中编写控制循环结束的语句，最后再用main函数去调用push函数。2.4 用递归实现上述求解 这种方法给上述几种不同，在函数的执行函数的过程中，需多次进行自我调用，递归函数的运行过程类似与多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，从主函数开始调用，一次更深一层，退出时一步一步返回到上一层，所以不需要写控制循环语句，不需要写控制循环语句，比上几种方法简单点。3） 运行环境3.1 硬件环境pc3.2软件环境（1）windows xp（2）microsoft visual c+6.04） 开发工具和编程语言4.1 开发工具microsoft visual c+6.0 4.2

4、 编程语言c语言5） 详细设计5.1用数组数据结构实现上述求解/计算桃子的个数void taozi(int n,int m) int day10;/初始化变量，用数组元素分别存储每天的桃子个数 int i;/控制循环执行的次数day0=n;/最后一天的桃子个数 for(i=0;inext=null;/创建一个带头结点的单链表 l-next=p;/插入到表头 l-next-data=e;/初始化第一个结点 for(i=m-1;i0;i-) s=(lnode *) malloc(sizeof(lnode); p-next=s; s-data=2*(p-data+1);/结点与下一结点之间的联系 p

5、=s;/指针p总是指向最后一个结点 s-next=null; printf(第%d天的桃子为:%dn,11-m,p-data);5.3用栈数据结构实现求解/储存空间初始分配量#define stack_init_size 100 /顺序栈的定义typedef struct int *base;/栈底指针 int *top;/栈顶指针 int stacksize;/当前已分配的存储空间sqstack;sqstack s;/构造一个空栈int initstack() s.base=(int *) malloc(stack_init_size * sizeof(int); if(!s.base) e

6、xit (overflow);/存储分配失败 s.top=s.base;/刚开始栈为空 s.stacksize=20; return ok;/计算桃子个数的函数void push(int e,int m)/ m是要计算的是第几天 int i; initstack(); *s.top+=e;/给栈底元素初始化 for(i=0;i0) y=2*(x+1); i-;/循环控制条件 taozi(y); printf(%dn,y); 5.5 源代码如下1 用数组数据结构编写#includevoid taozi(int n,int m) int day10; int i; day0=n; for(i=0;

7、i10-m;i+) dayi+1=2*(dayi+1); printf(第%d天的桃子为:%dn,m,day10-m);void main() int m; printf(请输入要求第几天剩下的桃子:n); scanf(%d,&m); taozi(1,m); while(1) int j; printf(请输入j的值 0:退出 1:继续:n); scanf(%d,&j); switch(j) case 1: printf(请输入要求第几天剩下的桃子:n); scanf(%d,&m); taozi(1,m); break; case 0: return; break; default: prin

8、tf(输入有误请重新输入!); 2 用链数据结构编写 #include#include#define null 0typedef struct lnode int data; struct lnode *next;lnode;lnode *l;lnode *p,*s;int createlist_l(int e,int m) int i; l=(lnode *) malloc(sizeof(lnode); p=(lnode *) malloc(sizeof(lnode); l-next=null;/创建头结点 l-next=p; l-next-data=e; for(i=m-1;i0;i-)

9、s=(lnode *) malloc(sizeof(lnode); p-next=s; s-data=2*(p-data+1); p=s;/指针p总是指向最后一个结点 s-next=null; printf(第%d天的桃子为:%dn,11-m,p-data);void main() int n; int k;printf(请输入要求第几天剩下的桃子:n); scanf(%d,&n); k=11-n; createlist_l(1,k); while(1)int j; printf(请输入j的值 0:退出 1:继续:n); scanf(%d,&j); switch(j)case 1:printf

10、(请输入要求第几天剩下的桃子:n); scanf(%d,&n); k=11-n; createlist_l(1,k); break; case 0: return; break; default: printf(输入有误请重新输入!); 3 用栈数据结构编写#include#include#define stack_init_size 100 #define ok 1#define overflow -2typedef struct int *base; int *top; int stacksize;sqstack;sqstack s;int initstack() s.base=(int

11、*) malloc(stack_init_size * sizeof(int); if(!s.base) exit (overflow); s.top=s.base; s.stacksize=20; return ok;void push(int e,int m) int i; initstack(); *s.top+=e; for(i=0;i10-m;i+) *s.top=2*(*(s.top-1)+1); s.top+; printf(第%d天的桃子为:%dn,m,*(s.top-1);void main() int m; printf(请输入要求第几天剩下的桃子:n); scanf(%d

12、,&m); push(1,m); while(1) int j; printf(请输入j的值 0:退出 1:继续:n); scanf(%d,&j); switch(j) case 1: printf(请输入要求第几天剩下的桃子:n); scanf(%d,&m); push(1,m); break; case 0: return; break; default: printf(输入有误请重新输入!); 4 用递归编写 #includeint i=9;int taozi(int x)int y;while(i0) y=2*(x+1); i-; taozi(y); printf(%dn,y); vo

13、id main()int a=1;taozi(a);printf(1n);6) 调试分析 1 在用链数据结构实现时，运行时没有显示错误，但输出不是预测的结果，代码如下： for(i=m-1;i0;i-) s=(lnode *) malloc(sizeof(lnode); p-next=s; s-data=2*(p-data+1); s-next=null;在指针的移动时，由于p总是第一个结点，在for循环前已经被赋值，指针p 应该总是指向最后一个结点的，所以在这句s-next=null前加上一句p=s就行了， 就能输出正确结果。2 在生成新结点时，一定要用强制类型转换，要不就要出错。不能把s=

14、(lnode *) malloc(sizeof(lnode)写成s=(lnode) malloc(sizeof(lnode);因为它们不属于同一类型。3 在用栈数据结构实现的过程中，虽然只有一个错误，但却显示了好多错误。主要原因是由于一个参数是在main函数中定义的，但却被其它函数调用，只要把该参数定义成全局变量就行了。4 在用while循环时，由于控制条件的不恰当导致的错误，不过只要再认真分析一下，就正确了。5 还有些其它方面的错误，不过只要看一眼，就能改正，是粗心造成的。7）运行结果 链数组和栈实现结果：递归实现结果：参考文献 数据结构（c语言版） 严蔚敏 吴伟民 编著 清华大学出版社数据

15、结构（c语言版） 秦玉平 马靖善 主编 冯佳昕 周连秋 副主编 清华大学出版社 总结我的实验的主要目的是当用户输入第几天时，可以给出当天的桃子的个数，而且当用户输入1时，可以继续输入所要的，感觉挺简单的，在高中的时候就可以用公式把它给推出来，唯一不同的是，它要求用多种方法实现，分别是数组，链，和递归等其它的方法，而我又用了个栈来实现。在数组编写时，问题还不算太大，因为大一时就开始接触数组，用的次数也比较多，只需写出循环语句，以达到运行一次，可以输出多种结果。在用递归时，虽然也是大一时学的，但还是有点困难，不过经过请教同学和课本，还是把它给搞定了。到用链编程时，难度就更大了，本来编程就少，动手能

16、力不太强，在这次编程里，还要类型定义，建立结点和对结点的操作，并且还要定义多个指针，在结点建立的同时，还要时刻注意指针的移动，最后还要用循环控制。在用栈编写时，栈是本学期刚学的知识要点，是先进后出的，跟链表一样，要求类型定义，即对顺序栈的定义，再构造一个空栈，对栈进行一些操作，虽然大一时也好好听课了，可能是时间长的缘故，感觉对栈顶指针和栈底指针的控制比链表简单点。总的来说，我写的程序应该不是最好的，有些地方不够简练，就这样，我把这学期课程设计的程序代码搞定了，虽然跟其他人的程序比起来，简单些，又短了一些，但从中我学到了好多以前没学到的东西，那些被我认为没有用的知识和感觉自己已经会了的东西。心得

17、体会通过这一周的实践学习，我认识到学好计算机要重视实践操作，不仅仅是学习数据结构，以及其它的计算机方面的知识都要重在实践，很多以前学过的东西，在运用时都不能很熟练，也说明理论知识和实践之间的差别。这就告诉了我们在以后的学习过程中要培养自己的动手能力，要将学过的知识转化为实践。作为一个计科专业的学生，通过这周的学习，使我更加明白了动手能力的重要性。在这次的课程设计中，我不断地去找书本知识和查阅其它有关资料，不仅巩固了对课本知识的掌握，还有利于以后更好的进步，提高了对课外知识的了解，虽然花费了不少时间，但只要学到有价值的东西，我认为都是值得的。在完成该试验的过程中，我问了同学和老师，还查阅了很多和

18、链表有关系的书籍，通过学习，翻看以前学过的知识，使我明白了我在学习知识上的很多不足。不过在此同时又重新复习了课本，从中学到了许多以前未学到的知识，感觉非常有成就感，让我对自己更加有信心，让我对数据结构这门课程也更感兴趣了，以前我一直感觉枯燥难学的数据结构，现在我也愿意去认真研究学习了。在以后的学习过程中，我要认真负责地对待课本中的每一个知识点，进一步充实自己，提高自己。要想学好这门课，最主要的在于实践，要通过不断的上机操作才能更好地学习它，平时我们总是自我感觉良好，感觉自己什么都会，但通过实践，我发现我的好多不足之处，一些基本的知识都没有掌握，比如说函数的调用，全局变量的用法等，好多基本的错误，有时连我们自己都无法原谅。有时经过半天的时间写出来一个调用函数，但一上机运行就有大量的错误，更糟的是没有错误，但是不能运行或者是运行不出想要的结果，怎么找也找不到原因所在。在写程序的每一步时，我