we桃子

路漫漫其修远兮，吾将上下而求索-百度文库

11

数据结构课程设计报告

题目：猴子吃桃问题

院（系）：数理学院

专业：信息计算科学

班级：计科1101

学生：史城逸

学号：1104101127

指导老师：周海岩

2012年6月

路漫漫其修远兮，吾将上下而求索-百度文库

22

摘要

当下C++语言是一门重要的课程学习，学会运用并结合其他的知识一起解题

是一件值得我们重视的，数据结构是一门结合C++知识的重要课程，因此我们要

学会将平时课本的知识运用到我们现实生活当中，这样才能让我们所学的知识更

加深刻。猴子吃桃的问题就是一个例子，我们可以运用简单的三种解法进行解题，

即数组求值解法，链表求值解法和递归求值解法，通过分析三种解法，根据各种

解法的功能从而我们得到最合适的求法。

关键词：猴子吃桃，数组法，链表法，递归法，分析

Abstract

Thec++languageisanimportantcourstudy,learntouand

incombinationwithotherknowledgeproblemsolvingisaworthy

togetherwevalue,thedatastructuretobeacombinationC++

knowledgeimportantcour,sowehavetolearnhowtouthe

knowledgewillusuallytextbookstoourrealitylife,sothatwecan

keyatthepeach

problemisoneexample,wecanusimplethreesolutiontoproblem

solving,namelyarrayevaluatedmethod,thelistoftheevaluated

hydrolysisandrecursionevaluatedmethod,throughtheanalysisof

threekindsofsolution,accordingtovariousmethodstogetthemost

appropriatefunctionswethemethod.

Keywords:themonkeyatthepeach,thearraymethod,chain

tablemethod,arecursivemethod,analysis

路漫漫其修远兮，吾将上下而求索-百度文库

33

目录

1、需求分析.........................4

2、概要设计.........................4

2.1.用数组数据结构实现上述求解......4

2.2.用链数据结构实现上述求解........4

2.3用递归实现上述求解..............4

2.4用栈数据结构实现求解............5

3、运行环境........................5

3.1硬件环境........................5

3.2软件环境........................5

4、详细设计........................5

4.1系统流程图......................5

4.2用数组数据结构实现上述求解......6

4.3用链数据结构实现上述求解........6

4.4用递归实现上述求解..............8

4.5用栈数据结构实现求解............8

5、调试分析........................9

6、运行结果.........................9

课程设计总结.......................13

致谢..............................14

参考文献...........................15

路漫漫其修远兮，吾将上下而求索-百度文库

44

1、需求分析

1、猴子吃桃子问题

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只

余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。

要求：

1)采用数组数据结构实现上述求解

2)采用链数据结构实现上述求解

3)采用递归实现上述求解

4)如果采用第4种做法，适当加分

2、概要设计

2.1.用数组数据结构实现上述求解

在taozi函数中定义一个一维数组，分别存储每天的桃子个数，根据题目的内容找出各

个数之间的关系，用数组元素表示出来，根据用户输入要计算哪一天的桃子，用for循环控

制结束。在main函数中让用户输入要计算的哪一天，调用taozi函数，以便用户可查出任

意一天的桃子个数，用switch语句判断用户要执行的功能，然后用while循环控制，直到

用户输入0为止。

2.2.用链数据结构实现上述求解

先写出预定义常量和类型，写出结点的类型定义，创建结点，初始化链表，定义变量并

初始化，找出结点与其后继结点之间的联系，然后在主函数中控制。

2.3用递归实现上述求解

这种方法跟上述几种不同，在函数的执行函数的过程中，需多次进行自我调用，递归函数的

运行过程类似与多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，从主函数

开始调用，一次更深一层，退出时一步一步返回到上一层，所以不需写控制循环语句，不需

要写控制循环语句，比上几种方法简单点。

路漫漫其修远兮，吾将上下而求索-百度文库

55

2.4用栈数据结构实现求解

本部分包括预定义常量和类型，顺序栈的定义，InitStack函数，Push函数，和main函数，

在InitStack函数构造一个空栈，在Push函数中调用该函数，并在其中编写控制栈顶指针

和栈底指针移动的语句，找出指针所指向的数据之间的关系，在main函数中编写控制循环

结束的语句，最后再用main函数去调用Push函数。

3、运行环境

3.1硬件环境

PC

3.2软件环境

（1）WindowsXP

（2）MicrosoftVisualC++6.0

4、详细设计

4.1系统流程图

猴子吃桃问题的实现

用

数

组

结

构

实

现

用

链

数

据

结

构

实

现

用

递

归

方

法

实

现

用

栈

数

据

结

构

实

现

路漫漫其修远兮，吾将上下而求索-百度文库

66

4.2用数组数据结构实现上述求解

#include

voidmain()

{

inti,tao[10];

tao[9]=1;//tao[9]代表第10天剩的桃子数

for(i=8;i>=0;i--){

tao[i]=2*(tao[i+1]+1);

}

printf("共摘了%d个桃子！n",tao[0]);

}

4.3用链数据结构实现上述求解

#include

#include

#defineNULL0

typedefstructlinknode

{

intdata;

structlinknode*next;

}node;

node*head;

voidcreat()

{

node*p,*s;

intpeaches=1;

intday=10;

head=(node*)malloc(sizeof(node));

p=head;

while(day>0)

路漫漫其修远兮，吾将上下而求索-百度文库

77

{

s=(node*)malloc(sizeof(node));

s->data=peaches;

p->next=s;

p=s;

peaches=(peaches+1)*2;

day--;

}

p->next=NULL;

p=head;

head=head->next;

free(p);

}

voidprint()

{

node*p;

p=head;

intday=10;

while(p&&day>0)

{printf("%d:%dn",day,p->data);

p=p->next;

day--;

}

}

voidmain()

{

creat();

print();

}

路漫漫其修远兮，吾将上下而求索-百度文库

88

4.4用递归实现上述求解

#include

inttao(intn)

{

if(n==10)return1;

return2*(tao(n+1)+1);

}

voidmain()

{

intsum=0;

sum+=tao(1);

printf("共摘了%d个桃子！n",sum);

}

4.5用栈数据结构实现求解

#include

#include

//栈的结构定义

typedefstruct{

int*ba;

int*top;

}Stack;

//初始化栈

voidInitStack(Stack&s)

{

=(int*)malloc(sizeof(int));

if()=;

el{

printf("空间分配错误！n");

exit(0);

路漫漫其修远兮，吾将上下而求索-百度文库

99

}

}

//入栈

voidPushStack(Stack&s,intdata)

{

*++=data;

}

//出栈

intPopStack(Stack&s)

{

return*(--);

}

voidmain()

{

inti=10,data;

Stacks;

InitStack(s);

PushStack(s,1);//先将第10天的桃子数1入栈

while(i-->1){

data=PopStack(s);//出栈一个元素保存在data中

PushStack(s,2*(data+1));//再将2*(data+1)入栈

}

//最后栈中剩余的那个元素就是第1天摘的桃子数

printf("共摘了%d个桃子！n",PopStack(s));

}

5、调试分析

调试基本无错误，仅字体及符号的错误，很容易便改正过来。

6、运行结果

用数组数据结构实现：

路漫漫其修远兮，吾将上下而求索-百度文库

1010

用链数据结构实现：

路漫漫其修远兮，吾将上下而求索-百度文库

1111

用递归实现：

路漫漫其修远兮，吾将上下而求索-百度文库

1212

用栈数据结构实现：

路漫漫其修远兮，吾将上下而求索-百度文库

1313

课程设计总结

通过这一周的实践学习，我认识到学好计算机要重视实践操作，不仅仅是学

习数据结构，以及其它的计算机方面的知识都要重在实践，很多以前学过的东西，

在运用时都不能很熟练，也说明理论知识和实践之间的差别。这就告诉了我们在

以后的学习过程中要培养自己的动手能力，要将学过的知识转化为实践。作为一

个计科专业的学生，通过这周的学习，使我更加明白了动手能力的重要性。

在这次的课程设计中，我不断地去找书本知识和查阅其它有关资料，不仅

巩固了对课本知识的掌握，还有利于以后更好的进步，提高了对课外知识的了解，

虽然花费了不少时间，但只要学到有价值的东西，我认为都是值得的。在完成该

试验的过程中，我问了同学和老师，还查阅了很多和链表有关系的书籍，通过学

习，翻看以前学过的知识，使我明白了我在学习知识上的很多不足。不过在此同

时又重新复习了课本，从中学到了许多以前未学到的知识，感觉非常有成就感，

让我对自己更加有信心，让我对数据结构这门课程也更感兴趣了，以前我一直感

觉枯燥难学的数据结构，现在我也愿意去认真研究学习了。

这次数据结构课程设计中，多亏了我的指导老师周海岩老师的悉心教导。

在以后的学习过程中，我要认真负责地对待课本中的每一个知识点，进一步充实

自己，提高自己。

路漫漫其修远兮，吾将上下而求索-百度文库

1414

致谢

这次课程设计，首先要感谢淮阴工学院给了我们相当好的试验环

境，机房的设备很好，学习环境也很好，一点没有吵闹，也要感谢周

海岩老师，在这一周的教导，每天陪着我们，解答我们的疑难，也监

督我们的学习。当然，同学们的帮助也是很重要的，我们互相讨论，

虽然课题并不一样，可是解决方法却大同小异，各方面知识都要运用

到，合作就显得至关重要。

总之，完成这次课程设计，要搞些的太多，以后一定要更好的学

习数据结构，冰灵活地运用。

路漫漫其修远兮，吾将上下而求索-百度文库

1515

参考文献

[1]黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2008

[2]董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出

版社，2008

[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2002

[4]刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003