唐 山 学 院 数据结构 课 程 设 计
题 目 猴子吃桃问题 系 (部) 计算机科学与技术系 班 级 08信管本（1）班 姓 名 李金龙 学 号 ********** 指导教师 刘印平
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引言 .............................................................. 1 1.1编写目的 ..................................................... 1
1.2背景 ......................................................... 1 1.3开发概述 ..................................................... 1 1.4采用方法特点 ................................................. 1 2问题分析 ........................................................... 3
2.1问题描述 ..................................................... 3 2.2问题要求 ..................................................... 3 2.3任务定义 ..................................................... 3 3算法思想及分析 ..................................................... 4
3.1设计思想 ..................................................... 4 3.2功能模块 ..................................................... 4 4源程序及说明 ....................................................... 5
4.1声明类型，定义函数 ........................................... 5 4.2源程序代码 ................................................... 5
4.3数据结构说明 ................................................ 11
4.3.1基本抽象数据类型 ...................................... 11 4.3.2基本运算 .............................................. 11 4.3.3具体问题的数据类型 .................................... 11 4.4程序流程图 .................................................. 12 5测试数据及运行情况 ................................................ 13 6总结 .............................................................. 18 参考文献 ........................................................... 20
唐 山 学 院 课 程 设 计
1引言
1.1编写目的
全面系统地学习C语言面向对象程序设计的语法和编程方法。
更加透彻地理解和掌握课本上的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，掌握它们在程序中的使用方法。
利用所学知识解决复杂数学问题，复杂问题用简单程序进行求解，得到答案。同时，在编写的过程中巩固所学知识，在查看课外资料的过程中开拓眼界，增长知识。
在程序编辑的过程中，不但可以弥补自身知识的缺陷，还能对C++的性能和操作技巧有进一步的掌握。
以猴子吃桃问题为起点，掌握程序编辑的技巧
学习软件设计的基本内容和设计方法，以培养规范化软件设计的能力。 掌握计算机的各种功能的使用方法、技巧，学会参考有关资料，提高进行程序设计的基本能力和增强日后的学习能力。
1.3开发环境
主要采用的开发工具是Visual C++ 6.0；在开发过程中利用数组数据结构，链式数据结构和递归进行分析和设计。主要的开发环境是奔腾四以上CPU，Windows XP系统，利用Visual C++ 6.0及相关软件
1.4采用方法特点
数组数据结构，链数据结构是数据结构中两种重要的数据算法。数组是有序数据的集合,在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。链式结构每个存储单元实际上包含两个内容：数据本身与指向存储下一个数据的存储单元地址的指针，可以使程序简单化。
递归做为一种算法在程序设计语言中广泛应用. 指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。
线性表按链式存储时，每个数据元素 (结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据，指针区存放其后继元素的地址 (没有后继元素时设置为空字符(Null).。只要知道该线性表的起始地址 (记录在头指针中)，表中的各
1
唐 山 学 院 课 程 设 计
个元素就可通过其间的链接关系逐步找到。
2
唐 山 学 院 课 程 设 计
2问题分析
2.1问题描述
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解
2.2问题要求
功能要求：分别用数组数据结构、链数据结构、递归的方法求出第一天摘到桃子的数量。
输出形式：有中文提示，桃子数量是整形 界面要求：有合理的说明，及结果。 存储结构：链式存储，数组存储。 测试数据：要求使用： (1)全部合法数据； (2)整体非法数据； (3)局部非法数据。
进行程序测试，以保证程序的稳定。测试数据及测试结果在上交的资料中写明。
2.3任务定义
利用数组数据结构、链式数据结构和递归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源程序及说明
4.1声明类型，定义函数：进行函数声明，定义所有用到的函数。
#include #include #define NULL 0 void main() void print() void creat()4.2源程序代码
#include#include#define NULL 0
typedef struct linknode {
int data;
struct linknode *next;
//链表指针 }node;
node *head;
//头结点 int day;
void creat()
5
唐 山 学 院 课 程 设 计
//创建链表
{ node *p,*s;
int peaches=1;
//第十天时只剩下一个桃子
int day=10;
head=(node*)malloc(sizeof(node));
p=head;
while(day>0) {
s=(node*)malloc(sizeof(node));
//分配存属空间
s->data=peaches;
//用来存放结点数据
p->next=s;
//把结点插入链表中 p=s;
peaches=(peaches+1)*2;
6
唐 山 学 院 课 程 设 计
//第一天的桃子数是第二天桃子数加后的2倍； day--; }
p->next=NULL;
p=head;
head=head->next;
//使头指针指向头结点
free(p);
//释放指针P } int print()
//输出从这十天每天的桃子数
{ node *p;
p=head;
int day=10;
while(p&&day>0) {
printf(\"第%d天的桃子数:%d个\\n\
7
唐 山 学 院 课 程 设 计
p=p->next; day--; } return 0 ; }
int array() {
static unsigned short arr[11]={0,0,0,0,0,0,0,0,0,0,1};
for(int i=11;i>=2;i--) {
arr[i-2]=2*(arr[i-1]+1);
printf(\"第%d天还剩桃子%d\\n\ } return 0; }
int digui() { int n ;
int fun(int);
8
唐 山 学 院 课 程 设 计
n = fun (1);
printf(\"%d\\n\ return 0; }
int fun(int day) {
if(day==10) return 1; else
return (fun(day+1)+1)*2; }
void main() { int n; pp: do {
9
唐 山 学 院 课 程 设 计
printf(\"\ ************************************************\\n\");
printf(\"\ *********猴子吃桃问题的实现方法***************\\n\");
printf(\"\ ************************************************\\n\");
printf(\"\ 1 数组实现 \\n\");
printf(\"\ 2 递归实现 \\n\");
printf(\"\ 3 链表实现 \\n\");
printf(\"\ 4 退出程序 \\n\");
printf(\"\ ************************************************\\n\");
printf(\"\请选择(1-4):[ ]\\b\\b\");
scanf(\"%d\
if(n<1||n>4) {
printf(\"重新输入1或2或3\\n\"); goto pp; } else
switch(n)
10
唐 山 学 院 课 程 设 计
{
case 1: printf(\"使用数组的方法\\n\");
array(); break;
case 2: printf(\"使用递归的方法\");
digui(); break;
case 3: printf(\"使用链表的方法\");
creat();
print();
break;
case 4: exit(0); } }
while(n>=1&&n<=4); }
11
唐 山 学 院 课 程 设 计
4.4数据结构说明
4.4.1基本抽象数据类型
ADT linknode {
数据对象：
D={ data[i]|1≤i≤10, data[i]属ElemType类型} 数据关系：
R={| data[i],data[i+1],i=1,2…10} }4.4.2基本运算：
A[i-1]=(A[i]+1)*2
4.4.3具体问题的数据类型：
int [day] 定义数组的类型为整型
12
唐 山 学 院 课 程 设 计
4.5 程序流程图
开始 n>0 n<=4 输入n执行相应操作n=n+1 结束
13
唐 山 学 院 课 程 设 计
5测试数据及情况分析
本系统共三种操作实现猴子吃桃问题，分拨而对应1，2，3，操作时键入任意一个即可得到由改算法算出的结果。
程序正常运行后出现的第一个页面如图1所示，可根据需求选择1、2、3、4四个数字进行操做，得到结果。
图1
输入“1”，则程序正常运行，显示如图2所示界面，得到由数组数据结构求得的结果，此时可继续输入2、3两个数字中的任意一个，进行求解
14
唐 山 学 院 课 程 设 计
此时可输入数字3继续进行操作。
图2
输入“2”，程序正常运行，显示如图3所示界面，得到由递归算法求得的结果，
图3
15
唐 山 学 院 课 程 设 计
输入“3”程序正常运行，显示如图4所示。
图4
计算完毕，输入“4”退出程序，显示效果如图5
16
唐 山 学 院 课 程 设 计
图5
对系统进行测试，输入非1、2、3、4的数字，查看系统的运行结果，在此输入“5”，进行测试，得到结果如图6所示。
图6
17
唐 山 学 院 课 程 设 计
6总结
经过这一个学期对《数据结构》的学习，我学到了不少东西，可能有一些学的不够理想，但这些知识为我的下一步学习打下了坚实的基础。做这样一个课程设计，一方面是为了检查我一个学期来学习的成果，另一方面也是为了让我进一步的掌握和运用它，同时也让我认清自己的不足之处和薄弱环节，加以弥补和加强。
在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。 通过这次课程设计，对我们大家的逻辑思维能力是一个很大的锻炼，加强了我们的系统思考问题的能力。
此次课程设计也对我们的团对合作精神有了极大的提高，以前没有做过什么稍大的程序，就都是一个人做，做了后，甚至还洋洋得意，可这一次，一开始是对我们的一个打击，没有一个人能单独完成，最后还是大家一齐出力，共同商讨，才得出了最后的结果，并且在这个过程中，我们相互之间还掌握了其他人掌握了但自己还没有掌握的知识，是一次知识的大汇总，并且在这个讨论的过程中，还更正了不少我们各自自身对于某个知识点的误区。
设计一个“猴子吃桃”的程序，我通过查询资料和上网搜，对程序有了初步的设想。通过各个功能的算法进行分析后，进一步设计出了程序。
这学期的课程设计，加深了我对数据结构基本知识的理解，提高了综合运用课程知识的能力；培养了参考书籍，查阅手册、图表和文献资料的能力；初步掌握了简单软件的分析方法和设计方法；并且了解了与课程有关的工程技术规范，能够正确的解释和分析出实验结果。
在本次课程设计的过程中，我们遇到了很多困难，比如对猴子吃桃问题课程设计的理解，在开始阶段，我们都未能正确地理解该问题，把用三种方法进行课程设计理解为用三种不同的方法对猴子吃桃问题进行求解，而不是将三种方法联系起来通过一个主函数来调用，这使得我们浪费了很多时间，但对我们影响最大的是精神上的打击，自己好多天的辛勤劳动就这样付诸流水，这让我们感觉很不爽，但错了就是错了，我们能做的就是重新进行程序编辑，在短时间内将程序编出来，这给了我们很大的压力，看着别人都已经快收尾了，而我们却要重新开始，而摆在我们面前的难题还不仅这些。
本次课程设计对格式的要求很严，我们必须很认真的做每一步，丝毫不能马虎，而且转换了一个新的编译环境，这个变化让我们有点儿难以适应，以至于在开始的时候无从下手，后来经过团队的努力，我们将问题的核心找了出来，讨论出了基本思路，在团队的努力下我们才能将程序编译出来，然后在做课程设计报告的过程中才轻松了一些，最后在我们的努力之下大家都顺利的完成了任务。
通过本次课程设计我掌握了C语言和数据结构的基础知识以及一些实践经验，
18
唐 山 学 院 课 程 设 计
为更好地在以后的学习中能够更好地运用打下了基础。总之，这次课程设计收获颇多，使我各方面的能力得到了提升，积累了丰富的经验。
19
