资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
唐 山 学 院 数据结构 课 程 设 计 题 目 猴子吃桃问题 系 (部) 计算机科学与技术系 班 级 08信管本(1)班 姓 名 李金龙 学 号 4082014114 指导教师 刘印平 2010 年 1 月 4 日至 1 月 8 日 共 1 周 2010年 1 月 8 日数据结构 课程设计任务书一、设计题目、内容及要求本课题题目是猴子吃桃子问题。有一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求:1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种方法者,适当加分功能要求:分别用数组数据结构、链数据结构、递归的方法求出第一天摘到桃子的数量。输出形式:有中文提示,桃子数量是整形界面要求:有合理的说明,及结果。存储结构:链式存储,数组存储。测试数据:要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明;要独立完成主要功能模块的编程并通过调试,能用合理的模拟数据运行。写出不少于5000字的设计报告,并另程序代码。二、要求的设计成果(课程设计说明书、设计实物、图纸等)1.软件(实现了规定功能的软件系统)2.课程设计报告(按学校规定要求)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设计思想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语言面向对象程序设计的语法和编程方法。更加透彻地理解和掌握课本上的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,掌握它们在程序中的使用方法。利用所学知识解决复杂数学问题,复杂问题用简单程序进行求解,得到答案。同时,在编写的过程中巩固所学知识,在查看课外资料的过程中开拓眼界,增长知识。在程序编辑的过程中,不但可以弥补自身知识的缺陷,还能对C+的性能和操作技巧有进一步的掌握。以猴子吃桃问题为起点,掌握程序编辑的技巧学习软件设计的基本内容和设计方法,以培养规范化软件设计的能力。掌握计算机的各种功能的使用方法、技巧,学会参考有关资料,提高进行程序设计的基本能力和增强日后的学习能力。1.3开发环境主要采用的开发工具是Visual C+ 6.0;在开发过程中利用数组数据结构,链式数据结构和递归进行分析和设计。主要的开发环境是奔腾四以上CPU,Windows XP系统,利用Visual C+ 6.0及相关软件1.4采用方法特点数组数据结构,链数据结构是数据结构中两种重要的数据算法。数组是有序数据的集合,在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。链式结构每个存储单元实际上包含两个内容:数据本身与指向存储下一个数据的存储单元地址的指针,可以使程序简单化。递归做为一种算法在程序设计语言中广泛应用. 指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。线性表按链式存储时,每个数据元素 (结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据,指针区存放其后继元素的地址 (没有后继元素时设置为空字符(Null).。只要知道该线性表的起始地址 (记录在头指针中),表中的各个元素就可通过其间的链接关系逐步找到。2问题分析2.1问题描述有一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解2.2问题要求功能要求:分别用数组数据结构、链数据结构、递归的方法求出第一天摘到桃子的数量。输出形式:有中文提示,桃子数量是整形界面要求:有合理的说明,及结果。存储结构:链式存储,数组存储。测试数据:要求使用:(1)全部合法数据;(2)整体非法数据;(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源程序及说明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=(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;while(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 *
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号