课程设计报告的模板

算法与数据结构

课程设计报告

题    目：  猴子吃桃子问题   

设  计  者：        陈铭湖                

专业班级：        本软件102        

学    号：            19                

指导教师：         龙君芳              

所属系部： 计算机科学与技术系

2012年06月24日

目 录

1 问题描述及要求    1

2 需求分析    1

3 算法思想描述    1

4 概要设计    1

5 详细设计    1

6 测试数据及分析    1

7课程设计总结    1

8 参考资料    1

设计题目猴子吃桃问题

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 算法思想描述

     根据需求分析，设计合理的数据结构，并对其数据结构的操作算法思想进行描述。

4 概要设计

 理出在设计中要用到的函数定义，及函数的功能，并用图描述函数的调用过程。

5 详细设计（小四号，加粗）

  介绍各功能模块（函数）的功能并给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。

6 测试数据及分析

测试数据: 

#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)

 { Node *p; p=(LinkStack)malloc(sizeof(Node)); 

p->datax=a;p->datay=b;

p->next=s; s=p;

 return s; } 

LinkStack Pop(LinkStack s) 

{ 

LinkStack p;

 if(s==NULL) 

{printf("stack is empty\\n");

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) {f=1; while(s) 

{ f=s->datax*f+s->datay; s=Pop(s);

 } 

printf("%d\\n",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\\n",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\\n",sum); 

printf("栈链实现:"); 

Zhanlian(1); 

}

结果如图:

7课程设计总结

   通过这次课程设计使我充分的理解了栈的利用并初步学习到了用栈去模拟递归 调用，而且对递归调用的细节更加清淅。虽然此次的程序不是很完备，但是总体还是 一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。 在刚开始编程的时候，我感到无从下手，但通过学习和查找资料，了解了算法，以这 个为基础才开始 慢慢写程序，不断改进才最后完成。 在此我非常要感谢的是我的指导老师许又泉老师，感谢老师的细心认真的辅导， 让我对数据结构这门课程有了更深一步了解，使我了解到数据结构的重要性，并能运 用数据结构去想问题和解决问题。

8 参考资料

[1] 李云清，杨.数据结构（C语言版）.北京：人民邮电出版社，2004.

[2] 严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版.1997.