《数据结构课程设计猴子吃桃问题》由会员分享，可在线阅读，更多相关《数据结构课程设计猴子吃桃问题（24页珍藏版）》请在金锄头文库上搜索。
1、唐 山 学 院 数据结构 课 程 设 计 题 目 猴子吃桃问题 系 (部) 计算机科学与技术系 班 级 08信管本（1）班 姓 名 李金龙 学 号 4082014114 指导教师 刘印平 2010 年 1 月 4 日至 1 月 8 日 共 1 周 2010年 1 月 8 日数据结构 课程设计任务书一、设计题目、内容及要求本课题题目是猴子吃桃子问题。有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种
2、方法者,适当加分功能要求：分别用数组数据结构、链数据结构、递归的方法求出第一天摘到桃子的数量。输出形式：有中文提示，桃子数量是整形界面要求：有合理的说明，及结果。存储结构：链式存储，数组存储。测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；要独立完成主要功能模块的编程并通过调试，能用合理的模拟数据运行。写出不少于5000字的设计报告，并另程序代码。二、要求的设计成果（课程设计说明书、设计实物、图纸等）1.软件（实现了规定功能的软件系统）2.课程设计报告（按学校规定要求）3.软件使用简要说明。三、进程
3、安排周一 问题分析和任务定义周二 逻辑设计周三 详细设计周四 程序编码周五 程序调试与测试四、主要参考资料1谭浩强，c语言程序设计，清华大学出版社，2008年2.严蔚敏，数据结构，清华大学出版社，1997年指导教师（签名）：教研室主任（签名）：课程设计成绩评定表出勤情况出勤天数 缺勤天数成绩评定出勤情况及设计过程表现（20分）课设答辩（20分）设计成果（60分）总成绩（100分）提问（答辩）问题情况综合评定 指导教师签名： 年 月 日目录1引言11.1编写目的11.2背景11.3开发概述11.4采用方法特点12问题分析32.1问题描述32.2问题要求32.3任务定义33算法思想及分析43.1设
4、计思想43.2功能模块44源程序及说明54.1声明类型，定义函数54.2源程序代码54.3数据结构说明114.3.1基本抽象数据类型114.3.2基本运算114.3.3具体问题的数据类型114.4程序流程图125测试数据及运行情况136总结18参考文献20唐 山 学 院 课 程 设 计1引言1.1编写目的全面系统地学习C语言面向对象程序设计的语法和编程方法。更加透彻地理解和掌握课本上的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，掌握它们在程序中的使用方法。利用所学知识解决复杂数学问题，复杂问题用简单程序进行求解，得到答案。同时，在编写的过程中巩固所学知识，在查看课外资料的过程中开拓
5、眼界，增长知识。在程序编辑的过程中，不但可以弥补自身知识的缺陷，还能对C+的性能和操作技巧有进一步的掌握。以猴子吃桃问题为起点，掌握程序编辑的技巧学习软件设计的基本内容和设计方法，以培养规范化软件设计的能力。掌握计算机的各种功能的使用方法、技巧，学会参考有关资料，提高进行程序设计的基本能力和增强日后的学习能力。1.3开发环境主要采用的开发工具是Visual C+ 6.0；在开发过程中利用数组数据结构，链式数据结构和递归进行分析和设计。主要的开发环境是奔腾四以上CPU，Windows XP系统，利用Visual C+ 6.0及相关软件1.4采用方法特点数组数据结构，链数据结构是数据结构中两种重要
6、的数据算法。数组是有序数据的集合,在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。链式结构每个存储单元实际上包含两个内容：数据本身与指向存储下一个数据的存储单元地址的指针，可以使程序简单化。递归做为一种算法在程序设计语言中广泛应用. 指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。线性表按链式存储时，每个数据元素 (结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据，指针区存放其后继元素的地址 (没有后继元素时设置为空字符(Nu
7、ll).。只要知道该线性表的起始地址 (记录在头指针中)，表中的各个元素就可通过其间的链接关系逐步找到。2问题分析2.1问题描述有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解2.2问题要求功能要求：分别用数组数据结构、链数据结构、递归的方法求出第一天摘到桃子的数量。输出形式：有中文提示，桃子数量是整形界面要求：有合理的说明，及结果。存储结构：链式存储，数组存储。测试数据：要求使用：(1)全部合法数据；(2)整体非法
8、数据；(3)局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果在上交的资料中写明。 2.3任务定义利用数组数据结构、链式数据结构和递归3种方法求解出猴子原来所摘的桃子数。3算法思想及分析3.1设计思想猴子分10天吃完了桃子,要想求出第1天的桃子数,就先要求出第2天的桃子数,.因此,有: A1=(A2+1)*2; A2=(A3+1)*2; . A9=(A10+1)*2; A10=1; 根据该算法进行程序编辑，计算结果。 建立顺序表，通过定义子函数将内容读如顺序表，对顺序表进行操作，实现用不同方法求解得到结果的目的。链表方法数组方法结果菜单输入错误返回3.2功能模块 递归方法4源程序
9、及说明4.1声明类型，定义函数：进行函数声明，定义所有用到的函数。#include#include#define NULL 0void main()void print()void creat()4.2源程序代码#include#include#define NULL 0typedef struct linknode int data; struct linknode *next;/链表指针node;node *head; /头结点int day;void creat()/创建链表 node *p,*s; int peaches=1;/第十天时只剩下一个桃子 int day=10; head=
10、(node*)malloc(sizeof(node); p=head;while(day0) s=(node*)malloc(sizeof(node);/分配存属空间 s-data=peaches;/用来存放结点数据 p-next=s; /把结点插入链表中 p=s; peaches=(peaches+1)*2;/第一天的桃子数是第二天桃子数加后的2倍； day-; p-next=NULL; p=head; head=head-next;/使头指针指向头结点 free(p); /释放指针Pint print()/输出从这十天每天的桃子数 node *p; p=head; int day=10;w
11、hile(p&day0) printf(第%d天的桃子数:%d个n,day,p-data); p=p-next; day-;return 0 ;int array()static unsigned short arr11=0,0,0,0,0,0,0,0,0,0,1;for(int i=11;i=2;i-)arri-2=2*(arri-1+1);printf(第%d天还剩桃子%dn,i-1,arri-1);return 0;int digui() int n ; int fun(int); n = fun (1); printf(%dn,n); return 0; int fun(int day)if(day=10)return 1;elsereturn (fun(day+1)+1)*2;void main() int n;pp:do printf(t *n); printf(t *猴子吃桃问题的实现方法*n); printf(t *n);printf(t 1 数组实现 n); printf(t 2 递归实现 n); printf(t 3 链表实现 n); printf(t 4 退出程序 n); printf(t *
