课程设计-猴子吃桃.doc

湖 南 工 学 院 数据结构课程设计题 目： 数据结构实现猴子吃桃系 别： 专 业： 年 级： 班 级： 学 生： 学 号： 目 录l 论 文 提 要 3l 需 求 分 析 4l 详 细 设 计 5n 数组结构 5n 递归 7n 链表 9l 调 试 结 果 11l 调试分析 12论文提要初步分析说明数据结构和抽象数类型等基本概念；从抽象数据类型的角度，通过数学应用的分析，把问题进行分析，整理，面后通过观察选择适当的逻辑结构、存储结构入及其相应的算法来解决问题,数据结构课程主要是为了培养我们对数据的抽象能力和对算法在时间和空间和复杂度上进行优化，猴子吃桃这一数学方面的例题是很典型的一道程序例题，在这里主要以C语言作为数据结构和描述语言，分析并采用数组数据结构，递归，链数据结构实现上述问题。需 求 分 析实现课题猴子吃桃摘 要：猴子吃桃这一典型的数学课题,其主要实现的过程是将其数学课题公式化，用一些简单的数据定义、初使化、通过一系列的条件判断和循环用来实现学数公式的计算机化。通过C语言基础分析和数据结构初步了解,我们使用C语言,利用C和数据结构的结合使用,让我们在短时间内建立起对数据结构的进一步认识。然后,形成正确的对算法和优有个的理解观念。关键词：C语言的基本了解，数据结构的基本了解, 数据中数组的使用，递归调用，用C语言实现数据链表题目：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了，求第一天共摘了多少？ 要求： 采用数组，递归，链数据结构实现上述求解 详 细 设 计1 数组结构把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。数组结构算法的流程图如图3-1：开 始建立一个以天数为下标以剩下桃子数为元素的数组规定此数组的通向公式求第一天的桃子数结 束程序如下：#includevoid main() int i,tao10; tao9=1;/tao9代表第10天剩的桃子数 for(i=8;i=0;i-) taoi=2*(taoi+1+1); printf(共摘了%d个桃子！n,tao0);2.链结构 建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给L。然后把每天的桃子数从链表的第一个结点插入链表。最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e，最后只要输出e即得到第一天的桃子数。程序如下：#includestdio.h#includestdlib.h#define TRUE 1#define FALSE 0#define NULL 0typedef int ElementType;typedef struct nodeElementType data;struct node *next;StackNode,*LinkStack;void InitStack(LinkStack top)top-next=NULL;int IsEmpty(LinkStack top) if(top-next=NULL) return TRUE;else return FALSE;int Push(LinkStack top,ElementType element)StackNode *temp;temp=(StackNode *)malloc(sizeof(StackNode);if(!temp) return FALSE;else temp-data=element;temp-next=top-next;top-next=temp; return TRUE;int Pop(LinkStack top,ElementType *element)if(IsEmpty(top) return FALSE;else StackNode *temp=top-next;*element=temp-data;top-next=temp-next;free(temp);return TRUE;void main() int i=10,data; Stack s; InitStack(s); PushStack(s,1); while(i-1) data=PopStack(s); PushStack(s,2*(data+1); printf(共摘了%d个桃子！n,PopStack(s);3.递归结构设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。递归算法的流程图如图3-3开 始定义参数i和ni0NY调用本身，且-i输出sum开 始程序如下：#includeint 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.2运行结果数组结构，链结构，递归结构的运行结果如图：数组结构结果 调 试 分 析 运行环境在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。 程序编辑体会 这次的课程设计的内容是用C语言实现猴子吃桃子问题，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的学生学籍管理模块，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻理解了C+中类的思想和实现，文件的概念和相关操作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计，在此，我忠心感谢我的指导老师戴成秋。