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

数据结构课程设计报告

题目：猴子吃桃问题

院 （系）： 数 理 学 院
专 业： 信息计算科学
班 级： 计科 1101
学 生： 史 城 逸
学 号： 1104101127
指导老师： 周 海 岩

2012年6月

摘要
当下C++语言是一门重要的课程学习，学会运用并结合其他的知识一起解题是一件值得我们重视的，数据结构是一门结合C++知识的重要课程，因此我们要学会将平时课本的知识运用到我们现实生活当中，这样才能让我们所学的知识更加深刻。猴子吃桃的问题就是一个例子，我们可以运用简单的三种解法进行解题，即数组求值解法，链表求值解法和递归求值解法，通过分析三种解法，根据各种解法的功能从而我们得到最合适的求法。
关键词：猴子吃桃，数组法，链表法，递归法，分析

Abstract
The c + + language is an important course study, learn to use and in combination with other knowledge problem solving is a worthy together we value, the data structure to be a combination C++ knowledge important course, so we have to learn how to use the knowledge will usually textbooks to our reality life, so that we can apply the knowledge more deeply. The monkeys eat the peach problem is one example, we can use simple three solution to problem solving, namely array evaluated method, the list of the evaluated hydrolysis and recursion evaluated method, through the analysis of three kinds of solution, according to various methods to get the most appropriate functions we the method.
Key words: the monkeys eat the peach, the array method, chain table method, a recursive method, analysis

目录
1、需求分析 3
2、概要设计 3
2.1.用数组数据结构实现上述求解 3
2.2.用链数据结构实现上述求解 4
2.3用递归实现上述求解 4
2.4用栈数据结构实现求解 4
3、 运行环境 4
3.1 硬件环境 4
3.2软件环境 4
4、 详细设计 5
4.1系统流程图 5
4.2用数组数据结构实现上述求解 5
4.3用链数据结构实现上述求解 5
4.4用递归实现上述求解 7
4.5用栈数据结构实现求解 7
5、 调试分析 9
6、运行结果 9
课程设计总结 13
致谢 14
参考文献 15

1、需求分析
1、 猴子吃桃子问题
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
 要求：
1) 采用数组数据结构实现上述求解
2) 采用链数据结构实现上述求解
3) 采用递归实现上述求解
4)如果采用第4种做法，适当加分
2、概要设计
2.1.用数组数据结构实现上述求解
在taozi函数中定义一个一维数组，分别存储每天的桃子个数，根据题目的内容找出各个数之间的关系，用数组元素表示出来，根据用户输入要计算哪一天的桃子，用for循环控制结束。在main函数中让用户输入要计算的哪一天，调用taozi函数，以便用户可查出任意一天的桃子个数，用switch语句判断用户要执行的功能，然后用while循环控制，直到用户输入0为止。
2.2.用链数据结构实现上述求解
先写出预定义常量和类型，写出结点的类型定义，创建结点，初始化链表，定义变量并初始化，找出结点与其后继结点之间的联系，然后在主函数中控制。
2.3用递归实现上述求解
这种方法跟上述几种不同，在函数的执行函数的过程中，需多次进行自我调用，递归函数的运行过程类似与多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，从主函数开始调用，一次更深一层，退出时一步一步返回到上一层，所以不需写控制循环语句，不需要写控制循环语句，比上几种方法简单点。
2.4用栈数据结构实现求解
本部分包括预定义常量和类型，顺序栈的定义，InitStack函数，Push函数，和main函数，在InitStack函数构造一个空栈，在Push函数中调用该函数，并在其中编写控制栈顶指针和栈底指针移动的语句，找出指针所指向的数据之间的关系，在main函数中编写控制循环结束的语句，最后再用main函数去调用Push函数。
3、 运行环境
3.1 硬件环境
PC
3.2软件环境
（1）Windows XP
（2）Microsoft Visual C++6.0
4、 详细设计
猴子吃桃问题的实现
用数组结构实现
用链数据结构实现
用递归方法实现
用栈数据结构实现
4.1系统流程图

4.2用数组数据结构实现上述求解
#include
void main()
{
int i,tao[10];
tao[9]=1;//tao[9]代表第10天剩的桃子数
for(i=8;i>=0;i--){
tao[i]=2*(tao[i+1]+1);
}
printf("共摘了%d个桃子！\n",tao[0]);
}
4.3用链数据结构实现上述求解
#include
#include
#define NULL 0
typedef struct linknode
{
   int data;
   struct linknode *next;
}node;
node *head;
void creat()
{
  node *p,*s;
  int peaches=1;
  int day=10;
  head=(node*)malloc(sizeof(node));
  p=head;
  while(day>0)
{
   s=(node*)malloc(sizeof(node));
  s->data=peaches;
  p->next=s;
  p=s;
  peaches=(peaches+1)*2;
  day--;
}
   p->next=NULL;
    p=head;
   head=head->next;
   free(p);
}
  void print()
{
   node *p;
    p=head;
  int day=10;
  while(p&&day>0)
{printf("%d:%d\n",day,p->data);
   p=p->next;
  day--;
}
}
  void main()
{
    creat();
   print();
}
4.4用递归实现上述求解
#include
int tao(int n)
{
if(n==10) return 1;
return 2*(tao(n+1)+1);
}
void main()
{
int sum=0;
sum+=tao(1);
printf("共摘了%d个桃子！\n",sum);
}
4.5用栈数据结构实现求解
#include
#include
//栈的结构定义
typedef struct{
int *base;
int *top;
}Stack;
//初始化栈
void InitStack(Stack &s)
{
s.base=(int *)malloc(sizeof(int));
if(s.base) s.top=s.base;
else{
printf("空间分配错误！\n");
exit(0);
}
}
//入栈
void PushStack(Stack &s,int data)
{
*s.top++=data;
}
//出栈
int PopStack(Stack &s)
{
return *(--s.top);
}
void main()
{
int i=10,data;
Stack s;
InitStack(s);
PushStack(s,1);//先将第10天的桃子数1入栈
while(i-->1){
data=PopStack(s);//出栈一个元素保存在data中
PushStack(s,2*(data+1));//再将2*(data+1)入栈
}
//最后栈中剩余的那个元素就是第1天摘的桃子数
printf("共摘了%d个桃子！\n",PopStack(s));
}
5、 调试分析
调试基本无错误，仅字体及符号的错误，很容易便改正过来。
6、运行结果
用数组数据结构实现：

用链数据结构实现：

用递归实现：

用栈数据结构实现：

课程设计总结
通过这一周的实践学习，我认识到学好计算机要重视实践操作，不仅仅是学习数据结构，以及其它的计算机方面的知识都要重在实践，很多以前学过的东西，在运用时都不能很熟练，也说明理论知识和实践之间的差别。这就告诉了我们在以后的学习过程中要培养自己的动手能力，要将学过的知识转化为实践。作为一个计科专业的学生，通过这周的学习，使我更加明白了动手能力的重要性。
在这次的课程设计中，我不断地去找书本知识和查阅其它有关资料，不仅巩固了对课本知识的掌握，还有利于以后更好的进步，提高了对课外知识的了解，虽然花费了不少时间，但只要学到有价值的东西，我认为都是值得的。在完成该试验的过程中，我问了同学和老师，还查阅了很多和链表有关系的书籍，通过学习，翻看以前学过的知识，使我明白了我在学习知识上的很多不足。不过在此同时又重新复习了课本，从中学到了许多以前未学到的知识，感觉非常有成就感，让我对自己更加有信心，让我对数据结构这门课程也更感兴趣了，以前我一直感觉枯燥难学的数据结构，现在我也愿意去认真研究学习了。
这次数据结构课程设计中，多亏了我的指导老师周海岩老师的悉心教导。在以后的学习过程中，我要认真负责地对待课本中的每一个知识点，进一步充实自己，提高自己。

致谢
这次课程设计，首先要感谢淮阴工学院给了我们相当好的试验环境，机房的设备很好，学习环境也很好，一点没有吵闹，也要感谢周海岩老师，在这一周的教导，每天陪着我们，解答我们的疑难，也监督我们的学习。当然，同学们的帮助也是很重要的，我们互相讨论，虽然课题并不一样，可是解决方法却大同小异，各方面知识都要运用到，合作就显得至关重要。
总之，完成这次课程设计，要搞些的太多，以后一定要更好的学习数据结构，冰灵活地运用。

参考文献
[1] 黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2008
[2] 董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，2008
[3] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2002
[4] 刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003