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

《数据结构课程设计---猴子吃桃子问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1、需求分析12、概要设计12.1.用数组数据结构实现上述求解12.2.用链数据结构实现上述求解12.3用栈数据结构实现求解12.4用递归实现上述求解23、运行环境23.1硬件环境23.2软件环境24、详细设计24.1系统流程图24.2用数组数据结构实现上述求解34.3用链数据结构实现上述求解44.4用栈数据结构实现求解54.5用递归实现上述求解65、调试分析76、运行结果7课程设计总结8参考文献9附录：9151、需求分析1、猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群

2、猴子共摘了多少个桃子。 要求：1) 采用数组数据结构实现上述求解2) 采用链数据结构实现上述求解3) 采用栈实现上述求解4) 采用递归实现上述求解2、概要设计2.1.用数组数据结构实现上述求解在taozi函数中定义一个一维数组，分别存储每天的桃子个数，根据题目的内容找出各个数之间的关系，用数组元素表示出来，根据用户输入要计算哪一天的桃子，用for循环控制结束。在main函数中让用户输入要计算的哪一天，调用taozi函数，以便用户可查出任意一天的桃子个数，用switch语句判断用户要执行的功能，然后用while循环控制，直到用户输入0为止。2.2.用链数据结构实现

3、上述求解先写出预定义常量和类型，写出结点的类型定义，创建结点，初始化链表，定义变量并初始化，找出结点与其后继结点之间的联系，然后在主函数中控制。2.3用栈数据结构实现求解本部分包括预定义常量和类型，顺序栈的定义，InitStack函数，Push函数，和main函数，在InitStack函数构造一个空栈，在Push函数中调用该函数，并在其中编写控制栈顶指针和栈底指针移动的语句，找出指针所指向的数据之间的关系，在main函数中编写控制循环结束的语句，最后再用main函数去调用Push函数。152.4用递归实现上述求解这种方法跟上述几种不同，在函数的执行函数的过程中，

4、需多次进行自我调用，递归函数的运行过程类似与多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，从主函数开始调用，一次更深一层，退出时一步一步返回到上一层，所以不需写控制循环语句，不需要写控制循环语句，比上几种方法简单点。3、运行环境3.1硬件环境PC3.2软件环境（1）WindowsXP（2）MicrosoftVisualC++6.04、详细设计4.1系统流程图猴子吃桃问题的实现用数组结构实现用链数据结构实现用栈数据结构实现用递归方法实现154.2用数组数据结构实现上述求解//计算桃子的个数voidtaozi(intn,intm){intday[10];

5、//初始化变量，用数组元素分别存储每天的桃子个数inti;//控制循环执行的次数day[0]=n;//最后一天的桃子个数for(i=0;i<10-m;i++)day[i+1]=2*(day[i]+1);//相邻元素之间的关系printf("第%d天的桃子为:%d",m,day[10-m]);}voidmain(){intm;//用户要计算的是第几天printf("请输入要求第几天剩下的桃子:");scanf("%d",&m);taozi(1,m);//调用while(1){intj;//循环控制条件printf("请输入j的值0:退出1:继续:");

6、scanf("%d",&j);switch(j){//当j=1时，用户可以输入多次想要的数值case1:printf("请输入要求第几天剩下的桃子:");scanf("%d",&m);taozi(1,m);15break;//跳出//当j=0时，跳出switch结构case0:return;break;//当用户输入除0和1以外的数值时，会让你重新输入，直到输入正确为止default:printf("输入有误请重新输入!");}}}4.3用链数据结构实现上述求解//预定义常量和类型#defineNULL0//单链表的存储结构typedefstructLNod

7、e{intdata;//数据域structLNode*next;//指针域}LNode;LNode*L;LNode*p,*s;//计算桃子的个数intCreateList_L(inte,intm)//e是第十天的桃子的个数，m是将要计算的是第几天{inti;L=(LNode*)malloc(sizeof(LNode));//生成新结点p=(LNode*)malloc(sizeof(LNode));L->next=NULL;//创建一个带头结点的单链表15L->next=p;//插入到表头L->next->data=e;//初始化第一个结点for(i=m-1;i>

8、0;i--){s=(LN