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

1、 文章编辑系统数学与计算机学院课程设计说明书课 程 名 称: 课 程 代 码: 6015059 题 目: 年级/专业/班: 学 生 姓 名: 学 号: 312011070102216 开 始 时 间: 2014 年 5 月 14 日完 成 时 间: 2014 年 5 月 28 日课程设计成绩：学习态度及平时成绩（20）技术水平与实际能力（20）完成情况(20)创新（5） 说明书（计算书、图纸、分析报告）撰写质量（35）总 分（100）指导教师签名： 年 月 日目 录 1 需求分析32 概要设计33详细设计44调试分析115用户使用说明126测试结果127结论14致谢15参考文献15摘 要 本课

2、程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C+，数据库采用MS SQL 2000，程序运行平台为Windows 98/2000/XP。在整个程序中分别采用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。程序通过调试运行，初步实现了设计目标。关键词：程序设计；C+；数组；链；递归；猴子吃桃 引 言 在日常生活中经常遇到一些与数据计算有关的问题，许多与猴子吃桃问题类似的问题

3、要求用计算机程序语言来解决，用这个程序算法可以解决一些类似问题，以便利于生活实际。1 需求分析 1.1任务与分析 任务功能：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子要求：采用数组数据结构实现上述求解采用链数据结构实现上述求解采用递归实现上述求解如果采用4种方法者,适当加分分析： 这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。 用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的项来实现。 用链结构实现的算法，则是建立链表，将每天的桃子数目

4、存入链表，然后输出第一天的桃子数。 用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解。1.2测试数据 输入任意一篇文章，按要求输入功能序号与字符串。测试是否能按要求输出正确结果。2 概要设计 C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子

5、的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为ai=3*2e(i-1)-2 (i=2)。如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递归算法。3详细设计3.1数组结构把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的

6、通项公式为ai=3*pow（2，(i-1)）-2 (i=2)。数组结构算法的流程图如图3-1：开 始建立一个以天数为下标以剩下桃子数为元素的数组规定此数组的通向公式求第一天的桃子数结 束图3-1int day,tao11; /定义数组和下标tao0=0; /tao0赋值为0tao1=1; /倒数第一天的桃子数为1for(day=2;daynext=NULL;这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部分构成。在插入数据时，将插入的位置的前一项的原有后去指针赋给此结点的后去指针，然后把插入结点的data地址赋给前一结点的后驱指针，插入就完成了。插入结点的程序代码如下：S

7、tatus ListInsert(LinkList L,int i,ElemType e)/在第i个位置之前插入元素e int j=0;/计数器初值为0LinkList s,p=L;/p指向头结点while(p&jnext;3.3递归设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。递归算法的流程图如图3-3开 始定义参数i和ni0NY调用本身，且-i输出sum开 始主要程序代码如下：int sum_fan(int n,int i) /子函数sum_fun，参数n和i接受主函数的参数 x和day if (i0) n = sum_fan(n+1)

8、*2,-i); /每一次都用(n+1)*2)的值去调用子函数本身 return n; /返回结果）程序完整代码/ zhanghang123.cpp: 主项目文件。#include stdafx.h# include# include#include#includeiostream#includestdlib.husing namespace System;/ ConsoleApplication1.cpp: 主项目文件。void method1() /数组实现int day, tao11; /定义数组和下标tao0 = 0; /tao0赋值为0tao1 = 1; /倒数第一天的桃子数为1for

9、 (day = 2; day 0)n = sum_fan(n + 1) * 2, -i); /每一次都用(n+1)*2)的值去调用子函数本身 return n; /返回结果void method3()/递归int sum;int day = 9; /实现函数调用的次数int x = 1; /最后一天还剩得一个桃子sum = sum_fan(x, day); /调用子函数sum_fan,并把返回得结果赋给sumprintf(%d, sum);getchar();#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW 0#defin

10、e OK 1#define NULL 0typedef int Status;typedef int ElemType;struct LNodeElemType data;LNode *next;typedef LNode *LinkList;void InitList(LinkList &L)/构造一个空链链表L = (LinkList)malloc(sizeof(LNode);/申请内存，产生头结点,并使L指向此头结点if (!L) exit(OVERFLOW);/判断是否申请成功L-next = NULL;/ next指针置空Status GetElem(LinkList L, int

11、i, ElemType &e)/当第i个元素存在的时，将其值赋给eint j = 1;/计数器初值为0LinkList p = L-next;/p指向第一个结点while (p&jnext;if (!p | ji)return ERROR;e = p-data;return OK;Status ListInsert(LinkList L, int i, ElemType e)/在第i个位置之前插入元素eint j = 0;/计数器初值为0LinkList s, p = L;/p指向头结点while (p&jnext;if (!p | ji - 1) return 0;/当第i节点不存在时s =

12、 (LinkList)malloc(sizeof(LNode);/生成新的结点s-data = e;s-next = p-next;/新结点指向原第i个结点p-next = s;/原第i-1个结点指向新结点return 1;void method2()LinkList L;int i, e, n;InitList(L);/初始化链表for (i = 1, n = 1; i 10; i+)n = 2 * n + 2;/将每一天的桃子数赋值给nListInsert(L, 1, n);/将n的值输入链表 GetElem(L,1, e);printf(%d, e);/输出桃子的数目getchar();

13、int main(array args)L:system(cls);puts(选择需要的方法来求解：请输入数字选项：);puts(*);puts(1.数组求解法；);puts(2.链表求解法；); puts(3.递归求解法；);puts(*);char a= getchar();if(a=1)method1();puts(n请按任意键返回：);getchar();goto L;else if (a=2)method2();puts(n请按任意键返回：);getchar();goto L;else if (a=3)method3();puts(n请按任意键返回：);getchar();goto

14、L;else puts(请输入合法的选项；);goto L; return 0;4 调试分析运行环境 在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual

15、 C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Window

16、s 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Deb

17、ugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。5使用说明界面弹出后，输入相应的数字代号进行运算，得出结果后按enter键返回6测试结果1.主界面展示2. 输入1用数组求解3. 按任意键返回，输入2用链表求解4. 按任意键返回，输入3用递归求解。结 论 这次的课程设计的内容是用C语言实现猴子吃桃子问题，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的学生学籍管理模块，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强

18、上机实践。同时再次深刻理解了C+中类的思想和实现，文件的概念和相关操作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计，在此，我忠心感谢我的指导老师湛新霞。湛老师对工作认真负责，耐心辅导，知识丰富而且相当和蔼。在这次课程设计中给了我很大的帮助。他严谨的治学精神和深厚的理论水平都使我获益非浅。同时还要感谢我的同学，他们为我提出了很多有用的建议，帮助我完成了这次的课程设计。最后也要感谢我们学校为我们提供良好的编程环境，使我们能够按时完成任务。 致 谢程序经过3周的时间终于编写完成，在此感谢老师对我们传授知识的恩情，让我们有了编写程序的基础，其次