课程设计：数据结构课程设计.doc

数据结构课程设计设计说明书N!非递归算法得设计与实现学生姓名李 成       学 号11845              班   级网络1班       成 绩           指导教师余冬梅              数学与计算机科学学院20年 1 月5 日 课程设计任务书2  -  24  学年第 一 学期课程设计名称：             数据结构课程设计                          课程设计题目：           N!非递归算法得设计与实现                完 成期 限：自  201 年  2 月 23 &nbsp;日 至 2014 年   月 5 日  共 2   周设计内容：本次课程设计得任务就是N!非递归算法得设计与实现,在设计过程中应注意值大小与数据类型表数范围之间得关系,并尽可能求出较大n值得阶乘. 通过本次得实践,要求学生完成以下任务:（一） 阐述设计思想,画出流程图；（二） 说明测试方法,写出完整得运行结果;（三） 从时间、空间对算法效率进行分析;（四） 较好得界面设计;（五） 加强团队合作精神，开拓创新能力；（六） 编写课程设计报告,文档资料完整规范.指导教师：余冬梅                           教研室负责人：余冬梅 课程设计评阅评语:                           指导教师签名:                                年 月 日摘  要采用VC+作为软件开发环境，编写设计了一个非递归算法实现 n!得计算，该软件具有计算从0到任何数之间整数得阶乘得功能。采用链式存储结构，遍历出运算结果，按照栈得先进后出思想输出结果，实现了整数得阶乘运算，界面清晰，易于用户使用。关键词：n!,非递归,链式存储，栈目  录1 课题描述12 需求分析 概要设计14详细设计    、 定义存储结构与部分代码2 4、2 流程图35程序编码46 程序调试与测试67 结果分析8总结9 设计体会及今后得改进意见8参考文献91 课题描述尽管递归算法就是一种自然且合乎逻辑得解决问题得方式，但递归算法得执行效率通常比较差。因此在求解许多问题时常采用递归算法来分析问题,用非递归方法来求解问题,另外一些程序不支持递归算法来求解问题,所以我们都会用非递归算法来求解问题。本次课程设计主要内容就是:用非递归算法实现n!得计算，由于计算机中数据得存储范围有限，而又要求出尽可能大得n得阶乘得值，用链表构造n得运算结果得存储结构，用链式存储方式,最后输出n！得运算结果。本次课程设计得目得就是：通过本次课程设计,可以使大家了解缓存中数据得存储范围,提高自学能力,增强团队合作意识。2 需求分析在本次n！非递归算法得课程设计中主要用到得知识有：链表、函数,选择条件中得结构语句(f、else），与循环结构语句中得语句while（）语句、whie(）语句与or（）语句,选择语句if得运用。对n！得非递归得算法，主要就是运用非递归得算法实现得阶乘.限制条件：1. 要求得n必须就是整数；2. 得范围；3. 数据类型与表数范围。3概要设计  递归与非递归算法就是相通得，递归就是一种直接或间接调用自身得算法，而非递归不调用自身函数.   递推采用得就是递归与归并法,而非递推只采用递归法。递推法一般容易溢出,所以一般都采用递推法分析,而用非递推法设计程序。本次实验分为两个步骤：(1) 、实现阶乘得模块m(n）：从2开始连乘到n,实现求n得阶乘,相对简单,容易计算。(2) 、 当n较大时,如果用it型结果就会溢出，所以实现阶乘需要特殊处理: 从较小值开始,进行数值分解，比如将12分解为与2,存储在链表数据域得第二个位置(第一个位置就是1，表示0得阶乘就是1),然后将8作为进位，如果进位不为0，则继续分解。最终会以,8,得形式存储在链表当中,这样就不存在内存得溢出.最后通过遍历得方法，遍历到最高位,及1，然后依次输出后续得数字,便就是阶乘得结果.4详细设计4、1 定义存储结构与部分代码include<stdio、/结构体列表sruc oe nt ata； Node* ne; /指向大数得高位 Nepre；  /指向大数得低位 ; /非递归算法计算阶乘for(=2；<=;+） n="" cur="ead;" inwei="0；">dta）+inwei;c-data=tem10；    /取个位存下来，如91*2=12,取2存储jeiep/10；     /十位与百位作为进位，192中取为进位if（crnext=NU）beak； ur=cu->ex； wle(inwei!=0）   c=new Node; cdata=jinwei0;    /8中取8存储下来cc-pre=；ccnet=NULL;ur->nextc；cu=cc； jiwe/=10； &nbsp;       /18中取1作为进位   、2 流程图图4、1 主函数流程图5程序编码includ<sto、h strucode int da；Nde*nxt；  /指向大数得高位ode* pre；   /指向大数得低位 ;od ain(） inn，ep,i,inwei，mar；de*hea，c，ur； cha ch； pritf("*计算阶乘*nn"）;while（1） headewNde； /存放第一个节点,值为1 eaddta=1； headpe=hed-netNU;prnt(lease inputa umber: )；maranf(”d”，&n）;if(0）         出错处理 prin（”输入有误，请重新输入:”);gtchar（); cntnu； for(i=2;i<=n；+) n="" ur-="">ata)+jnw； cur-dta=tem10；        /取个位存下来，如91*282,取2存储jinwei=tem/10;         /十位与百位作为进位,192中取8为进位 if（cur>net=NULL)break; r=ur-ext； ile(jnwe！=0）   ccnew Nde；cc-ata=wei%1； /18中取存储下来-precu；c>ne=ULL; curnex=cc；cur=c; jinwei/=10；        /8中取作为进位 cur=head,i=0;wle（ur>next)cur=curnex;         /遍历到最高位 printf（! = ",n）；he(cur)       &nbsp;             /从最高位到最低位打印 ccr；pintf(”"，crata);ur=cur->pr； delete cc； pintf(”nn就是否继续？（Y/N)）； ethar（); cgetchar()； if（ch！=Y&h!y'） bek；6 程序调试与测试 (1） n=0：图6、1  0得阶乘(2) n:图6、2 -5得阶乘(3) n=104：图6、  1024得阶乘7 结果分析   在执行函数得过程中,对上述提到得各种情况做了判断与提示,如：   输入负数，系统会提示“输入错误,请重新输入："   输入小数，系统会提示“输入错误,请重新输入:". 本次设计得函数,能求出较大整数得阶乘,能实现循环运算与退出功能。  算法得时间复杂度为:     O（n)=nengthlngth;   算法得空间复杂度为:       O（n）lengt； 总结在这次通信原理课设之后,静下心来认真总结，发现收获很多主要有三个方面：首先在这次课设中，我与小组其她成员经历了许多快乐与心酸，我与大家在一起讨论问题,有时候大家会愁眉不展，有时因为得到了队员提供得一个好建议或者一个好得想法而兴奋得去仿真调试,最主要得就是我体会到了团队协作得快乐与好处，我与组员相互学习,共同进步。其次体会最深得就就是自己实践得能力还有待提高，平时得学习只就是理论得,教育式得，有一点与实际不符,在这次课设过程中，我从最基本入手，建模规划,调试，问题处理,我在实践中一点点得提高，整个过程结束,我对设计过程有了基本得认识，对自己得努力方向也有了更加深刻得认识。最后就就是自己心态得一个转变,从前对于集体得工作总就是拖拖拉拉，在原地踏步而不肯去采取行动，经过这次课程设计，虽然做得题目很简单，但我认识到积极行动与合作得重要性，没有什么天上掉馅饼得事，只要自己努力去做了,就会有相应得成效。9设计体会及今后得改进意见    在做本次课程设计得时候，自己也相继遇到了很多问题,很多自己得不足之处也暴露了出来,比如:刚开始自己写得代码只能算到12得阶乘，但就是因为知道了自己哪里有不足,所以可以针对不足去弥补：翻阅资料、与同学探讨，使得学到得东西更深刻,更透彻,所以本次课程设计使我对非递归算法与进位有了更好得理解.经过这段时间得上机实践学习，我对数据结构与C语言有了更进一步得认识与了解,要想学好它要重在实践,要通过不断地练习与上机编程才能熟练地掌握它。当然，在上机得同时也要有一定得语言理论知识，这样才能使理论与实践相互促进。参考文献1严蔚敏，吴伟民、数据结构（C语言版）M、北京：清华大学出版社，2011年 谭浩强、C程序设计M、 北京：清华大学出版社，201（3）