1 问题描述。
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子，求原来这群猴子共摘了多少个桃子。一种采用数组数据结构实现；一种采用栈链数据结构实现； 一种采用递归实现上述求解。
2 需求分析。
1)由问题可知，题目中知道第十天所剩的桃子数，所以可以及往前算，算出前一天所剩余的桃子数，到第一天时即为总的桃子数，所以可用数组来存每天所剩的桃子数， 容易实现求解。 (2) 根据问题设第 n 天的桃子数为 f(n), 则前一天的桃子数为。
f(n+1)=f(n)-(f(n)/2+1)，化解可得 f(n)=2f(n+1)+2,以此为依据实现递归。
3) 由栈与递归的实现可知调用函数各被调用函数之间的链接及信息交换是通过栈来实现的，因此可以用栈模拟函数递归。即可通过用栈的链表储存结构模拟函数的递归调用过程来实现问题的求解。
3 概要设计。
3．1 抽象数据类型定义。
栈的抽象数据类型定义。
ast stack 数据关系：r1= 约定 an 端为栈顶，a1 端为栈底。 基本操作：
initstack(&s)
操作结果：构造一个空栈 s。
destroystack(&s)
初始条件：栈 s 已存在。 操作结果：栈 s 被销毁。
clearstack(&s)
初始条件：栈 s 已存在。 操作结果：将栈 s 清为空栈。
stackempty(s)
初始条件：栈 s 已存在。 操作结果：若栈 s 为空栈，则返回 true，否则 false。
push(&s,&e)
初始条件：栈 s 已存在。 操作结果：插入元素 e 为新的栈顶元素。
pop(&s,&e)
初始条件：栈 s 已存在且非空。 操作结果：删除 s 的栈顶元素，并用 e 返回其值。
stacktr**erse(s,visit())
初始条件：栈 s 已存在且非空。 操作结果： 从栈底到栈顶依次对 s 的每个数据元素调用函数 visit(),一旦 visit() 失败，则操作失败。
adt stack
3．2 模块划分。
本程序包括四个模块：
1 ) 主程序模块 void main() node,*linkstack;
4．2 主要模块的算法描述 ( 1 )主函数 void main() 2 )利用数组实现求解 int a[n] 用以存每天所下的桃子数，从第 10 天 a[10]=1 向前循环，到第一天，即为总的个数。
for(i=9;i>=1;i--)a[i]=2*a[i+1]+2; (3 )利用递归实现求解。
根据题可得出 f(n)=2f(n+1)+2,由此可用递归调有函数。
int fun(int n) 4 )用链栈实现求解。
由栈与递归的实现可知调用函数各被调用函数之间的链接及信息交换是通过栈来实现的，因此可以用栈模拟函数递归。 递归调用中每层递归要把参数用栈来保存，每进入一层递归，就压入栈顶，每退出一层，则出栈。 因为 f(n)=2f(n+1)+2,即应把参数 2，2 存入模拟栈中，当出栈时进行运算，并用中间变量 f 存结果。
for(n=1;n<=10;n++)printf("%d",f); else /*当 n 不等于 10 时，进行入栈操作*/ s=push(s,2,2);
链栈的操作。
linkstack push(linkstack s,int a, int b)/*入栈操作*/ linkstack pop(linkstack s)/*出栈操作*/ p=s; s=s->next; free(p); return s; }
5 测试分析。
测试数据及结果如图 5．1：图 5．1
6 课程设计总结。
通过这次课程设计使我充分的理解了栈的利用并初步学习到了用栈去模拟递归调用，而且对递归调用的细节更加清淅。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。 在刚开始编程的时候，我感到无从下手，但通过学习和查找资料，了解了算法，以这个为基础才开始慢慢写程序，不断改进才最后完成。
在此我非常要感谢的是我的指导老师许又泉老师，感谢老师的细心认真的辅导， 让我对数据结构这门课程有了更深一步了解，使我了解到数据结构的重要性，并能运用数据结构去想问题和解决问题。
参考文献。1] 李云清，杨**。数据结构（c语言版）.北京：人民邮电出版社，2004.
2] 严蔚敏，吴伟民。数据结构（c语言版）.北京：清华大学出版。1997.
3] 苏光奎，李春葆。数据结构导学。北京：清华大学出版。2002.
4] 周海英，马巧梅，靳雁霞。数据结构与算法设计。北京：国防工业出版社，2007.
5] 张海藩。 软件工程导论。 北京：清华大学出版社。2003.
附录（源程序清单）
#include""
#include""
#define n 20
typedef struct node
int datax;
int datay;
struct node *next; }node,*linkstack;
linkstack push(linkstack s,int a, int b)
linkstack pop(linkstack s)
linkstack p;
if(s==null)
printf("stack is empty");
return null;}
p=s; s=s->next; free(p); return s; }栈链实现*/
void zhanlian(int n)
int f; linkstack s=null; for(n=1;n<=10;n++)
if(n==10)
printf("%d",f); else s=push(s,2,2); 数组实现*/
void suzhu()
int i,a[n]; a[10]=1; for(i=9;i>=1;i--)a[i]=2*a[i+1]+2; printf("%d",a[1]);递归实现*/
int fun(int n)
if(n==10) return 1; else return(2*fun(n+1)+2); 主函数*/
void main() int sum; printf("数组实现：")
suzhu();
printf("递归实现：")
sum=fun(1);
printf("%d",sum);
printf("栈链实现：")
zhanlian(1);
getch();
课程设计报告格式 课程设计
洛阳理工学院。课程设计说明书。课程名称。设计课题。专业。班级。学号。姓名。完成日期2014年12月26日。问题描述 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的内容要求。基本要求 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的基本要求。测试数据 小四宋体，行间距单倍行距，每...
课程设计总结,课程设计报告
课程设计总结，课程设计报告。3.尝试应用项目管理软件进行项目进程的规划管理 绘制甘特图，不作硬性要求 二 选题说明。人事管理是企业信息管理的重要部分，面对大量的人事工资信息，财务部门采用人力处理将浪费大量的时间 人力和物力，且数据的准确性低。因此，开发一个界面友好，易于操作的人事工资管理软件进行自动...
课程设计 课程设计报告格式
学校名。课程设计报告。课程名称 c语言程序设计 系别 专业班级 学号。姓名。课程题目 企业人事管理系统 完成日期 指导老师 年月日。附件。课程设计的内容。企业人事管理系统 本项目的目标是开发一个功能实用，操作简便，简单明了的人事管理系统。能够录入人事的基本资料，在操作上能够完成诸如添加 修改 删除 ...