数据结构课程设计.doc

Data organization curriculm project 数据结构课程设计 设计题目： 猴子吃桃子问题专业班级： 通信工程0804班学生学号： 0909082421学生姓名： 王 璐指导老师： 彭 春 华完成时间： 2010-06-06 目 录1. 问题描述.1页2. 基本要求.1页3. 程序设计思想1-2页4. 软件模块结构图.2页5. 程序流程图.3页6. 源程序4-7页7. 调试分析8-9页8. 测试数据.9-10页9. 心得体会11-12页一问题描述这是一个很经典的简易的程序设计题，具体题目为:有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二基本要求1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解虽然题目很简单，但是要求用多种方法实现，要求知识比较全面，涉及到数组，链表，函数，指针，结构体，循环等方面的基础知识。三程序设计思想 1分析题目。每天吃当前桃子数目的一半再加一个，所以桃子数目肯定为偶数。用我们所熟悉的函数来表示，即：f(x+1)=f(x)/2-1;其中x代表第多少天。：猴子摘桃子的那天也就是第一天就吃了所摘桃子的一半加一个，所以桃子总数应该为第一天加1再乘以2，等效为f(0)。2. 实现方法。最容易想到的也是最简单的就是运用函数的递归。给出了边界条件与递归函数，直接调用就可以了。用数组实现，先定义一个一维数组，然后结合循环，也可以求解。如果用链表的话，相对来说要复杂点。先要构建一个动态链表，将头指针赋值给p,p赋值给q，使p, q同时指向链表头,将第十天的桃子数放在链表第一个数据域中，然后移动p,q使后一个数据域中存放的是前一个加1的2倍，即倒过来存放数据。四软件模块结构图猴子吃桃问题用数组实现用递归实现用链表实现五程序流程图开 始选择实现方法数组递归链表输入x=10输入nn=9输出y【10】=1TFm=2*(duigui(n+1)+1)i=0T输出m=1FY【x-1】=(y【x】+1)*2输出mx-输出y【x】六源程序#include#include#define NULL 0typedef int datatype;typedef struct linkdatatype tao;struct link *next;node;void shuzu()int day11,i;day10=1;for(i=10;i0;i-)dayi-1=2*(dayi+1);printf(%dt,i);printf(%dn,dayi);printf(the total :%dn,day0);int digui(int n)int m;if(n=9)m=1;elsem=2*(digui(n+1)+1);printf(%dt,n+1);printf(%dn,m);return(m);node *init_link(node *head)head=NULL;return(head);node m;void toutao(node *head)int i=10;node *p,*q;p=head;m.tao=1;p=&m;while(i0)q=p;q-tao=p-tao;p-next=(node*)malloc(sizeof(node);p=p-next;p-tao=2*(q-tao+1);printf(%dt,i);printf(%dn,q-tao);i-;printf(the total : %dn,p-tao);void main()int a,m,j;node *head;head=NULL;printf(please choose one method : 1: shuzu 2: digui 3: lianbiaon);for(j=0;j3;j+)scanf(%d,&m);switch(m)case 1:printf(the result of using shuzu:n);shuzu();break;case 2:printf(the result of using digui:n);a=digui(0);printf(the total : %dn,2*(a+1);break;case 3: printf(the result of using lianbiao:n);node *init_link(node *head);toutao(head);break;七调试分析分块测试1. 用数组实现没有出错，可以得到正确结果。2用递归实现运行出错：原因在于输入变量时忘了加&；if判断语句中用的应该是=却用成了赋值语句。改正后得到正确结果。3用链表实现运行出错，出错原因在于：第一个大括号后面忘了加“；”；没有在main()主函数中声明taoshu()函数的话，其定义就必须放在main()主函数前面，修改后，程序能正确运行。八测试数据程序运行界面1. 程序运行的初始界面2. 选择方法1运行界面3.选择方法2运行界面4.选择方法3运行界面 九心得体会终于挨到了写心得和体会的时候了，也就意味着这个课程设计接近了尾声，的确令人兴奋，看着自己的劳动成果，内心真的很激动。一开始从一大堆的题目中挑选适合自己和自己感兴趣的，发现自己对好多题都没感觉，关键就是当初基础没打好，即使有思想，也不一定能运行。所以当初就选了猴子吃桃这个简单一点的程序，因为它要用多种方法来实现，而且更接近于基础。翻书重新学习是我迈开的第一步，经过两三天的努力，我把相关的知识学了一遍，把框架弄出来了，然后分开编程，可是还有一些小问题存在，运行不了，但是一想到自己由完全不会到慢慢的开始懂了，就觉得自己不能放弃，一定会成功。我参照类似程序，改改和添添，终于大功告成，一块块小程序纷纷运行成功。顿时信心倍增，我又废寝忘食的把程序小块整合到一起，看到运行界面，我欢呼雀跃，看到正确结果，我觉得自己真行。这一个星期以来，我坐在电脑旁，又累又热，可是当程序做出来了之后，那点累那点苦又算得了什么呢。当现在敲打这些字的时候，满足感油然而生，如果有人问我物质和精神哪个更让人满足，那答案一定是精神，那种感觉只有自己体会了才能懂。这可不是大话，原来一直认为这样一个程序我是不能完成的，就等着在网上搜，可是现在我会很自信的说：没有什么可以难倒我。程序设计提升了我的自信心，真的是受益匪浅啊。这当然得感谢彭春华老师以及林立新老师还有同学的帮助。这就是年少轻狂的我什么都敢做，什么都不怕，就算跌倒了，再爬起来，没有什么大不了。最后小结：程序设计分为逻辑设计和详细设计两步。逻辑设计指的是，对问题描述中的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义软件模块结构图；详细设计则为定义相应的存储结构，并写出各函数模块的伪码算法。程序设计过程有如解决一实际