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

<p>数据结构课程设计
设计说明书
N!非递归算法得设计与实现

学生姓名
李 成　 &nbsp; &nbsp; &nbsp; 　 　
学 　 号
11１8０６4０5０ &nbsp; &nbsp;　 　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
班 &nbsp; 级
网络１1０２班 &nbsp;　 &nbsp; 　　 　 　 &nbsp; 　 　
成　　 绩
　 &nbsp; &nbsp; &nbsp; &nbsp; 　 &nbsp;　　 　
指导教师
余冬梅 　 &nbsp; &nbsp;　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;　
数学与计算机科学学院
20１４年 1 月　5 日 　
课程设计任务书
2０１３ &nbsp;- &nbsp;2０１4 &nbsp;学年第 一 学期
课程设计名称：
　 &nbsp; &nbsp; &nbsp;　 &nbsp; &nbsp;　 　 　 　 &nbsp; 数据结构课程设计 &nbsp; &nbsp; &nbsp; 　　 &nbsp; 　 &nbsp; &nbsp; 　 &nbsp; 　 　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
课程设计题目：
&nbsp; &nbsp;　　 &nbsp; 　 　 &nbsp; &nbsp; N!非递归算法得设计与实现 　 　 　 &nbsp; &nbsp; &nbsp; &nbsp;　 &nbsp;　 &nbsp; &nbsp;　 　　 　 　 　 &nbsp;
完 成　期 限：
自 &nbsp;201３ 年 &nbsp;１2　 月　 23 &nbsp;日　 至 2014 　年 &nbsp;１ 　　月　 5　 日 &nbsp;共　 2 &nbsp; 周
设计内容：
本次课程设计得任务就是N!非递归算法得设计与实现,在设计过程中应注意ｎ值大小与数据类型表数范围之间得关系,并尽可能求出较大n值得阶乘.
通过本次得实践,要求学生完成以下任务:
（一） 阐述设计思想,画出流程图；
（二） 说明测试方法,写出完整得运行结果;
（三） 从时间、空间对算法效率进行分析;
（四） 较好得界面设计;
（五） 加强团队合作精神，开拓创新能力；
（六） 编写课程设计报告,文档资料完整规范.
指导教师：余冬梅　 &nbsp; &nbsp; 　 &nbsp; 　 　　 &nbsp; &nbsp; &nbsp; &nbsp; 　 &nbsp;　 &nbsp; &nbsp; &nbsp; &nbsp;　 　 &nbsp; 教研室负责人：余冬梅
课程设计评阅
评语:
&nbsp;　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;　 &nbsp; 　 &nbsp;　 &nbsp; 指导教师签名:
　 &nbsp; &nbsp; &nbsp;　 &nbsp; 　　 &nbsp; &nbsp; 　 　 　　　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 　 &nbsp; &nbsp;年　 　月 　 日

摘 &nbsp;要
采用VC++作为软件开发环境，编写设计了一个非递归算法实现 n!　得计算，该软件具有计算从0到任何数之间整数得阶乘得功能。采用链式存储结构，遍历出运算结果，按照栈得先进后出思想输出结果，实现了整数得阶乘运算，界面清晰，易于用户使用。　
关键词：n!,非递归,链式存储，栈
目 　　 &nbsp;录
1 课题描述 1
2 需求分析 １
３ 概要设计ﻩ1
4　详细设计ﻩ２
&nbsp; &nbsp;　４、１ 定义存储结构与部分代码ﻩ2
　 　 4、2 流程图ﻩ3
5　程序编码ﻩ4
6 程序调试与测试ﻩ6
7 结果分析ﻩ8
８　总结ﻩ８
9 设计体会及今后得改进意见 8
参考文献 9
1 课题描述
尽管递归算法就是一种自然且合乎逻辑得解决问题得方式，但递归算法得执行效率通常比较差。因此在求解许多问题时常采用递归算法来分析问题,用非递归方法来求解问题,另外一些程序不支持递归算法来求解问题,所以我们都会用非递归算法来求解问题。
本次课程设计主要内容就是:用非递归算法实现n!得计算，由于计算机中数据得存储范围有限，而又要求出尽可能大得n得阶乘得值，用链表构造n得运算结果得存储结构，用链式存储方式,最后输出n！得运算结果。
本次课程设计得目得就是：通过本次课程设计,可以使大家了解缓存中数据得存储范围,提高自学能力,增强团队合作意识。
2 需求分析
在本次n！非递归算法得课程设计中主要用到得知识有：链表、函数,选择条件中得结构语句(ｉf、、、、else），与循环结构语句中得语句while（）语句、ｄｏ…whiｌe(）语句与ｆor（）语句,选择语句if得运用。
对n！得非递归得算法，主要就是运用非递归得算法实现ｎ得阶乘.
限制条件：
1. 要求得n必须就是整数；
2. ｎ得范围；
3. 数据类型与表数范围。
3　概要设计
　 &nbsp;递归与非递归算法就是相通得，递归就是一种直接或间接调用自身得算法，而非递归不调用自身函数.
&nbsp; 　递推采用得就是递归与归并法,而非递推只采用递归法。递推法一般容易溢出,所以一般都采用递推法分析,而用非递推法设计程序。
本次实验分为两个步骤：
(1) 、　实现阶乘得模块m(n）：从2开始连乘到n,实现求n得阶乘,相对简单,容易计算。
(2) 、 当n较大时,如果用iｎt型结果就会溢出，所以实现阶乘需要特殊处理: 从较小值开始,进
行数值分解，比如将1８2分解为１８与2,２存储在链表数据域得第二个位置(第一个位置就是1，表示0
得阶乘就是1),然后将１8作为进位，如果进位不为0，则继续分解。最终会以１,8,２得形式存储在链表
当中,这样就不存在内存得溢出.最后通过遍历得方法，遍历到最高位,及1，然后依次输出后续得数字,便就是阶乘得结果.
4　详细设计
4、1 定义存储结构与部分代码
＃include&lt;stdio、ｈ＞　
//结构体列表
sｔrucｔ Ｎoｄe
{　
ｉnt ｄata；
Node* neｘｔ;　 /／指向大数得高位
Nｏｄe＊　pre； &nbsp;　/／指向大数得低位
｝;
／/非递归算法计算阶乘
for(ｉ=2；ｉ&lt;=ｎ;ｉ++） n=&quot;&quot; cur=&quot;ｈead;&quot; inwei=&quot;0；&quot;&gt;dａta）+ｊinwei;　
ﻩﻩﻩcｕｒ-〉data=temｐ％10； &nbsp; &nbsp;/／取个位存下来，如91*2=1８2,取2存储
ﻩ jｉｎｗei＝ｔeｍp/10； &nbsp; 　　 &nbsp; //十位与百位作为进位，192中取１８为进位　
ﻩﻩ if（cｕr－〉next==NUＬＬ）
ﻩ ﻩbｒeak；
ﻩ ﻩｃur=cuｒ-&gt;ｎexｔ；
ﻩﻩ }
ﻩ ﻩwｈｉle(ｊinwei!=0）　 &nbsp;
ﻩ ｛
ﻩ cｃ=new Node;
ﻩﻩﻩｃc－〉data=jinwei％１0; &nbsp; &nbsp;　//１8中取8存储下来
ﻩ ﻩ cc-＞pre=ｃｕｒ；
ﻩ ﻩcc－〉neｘt=NULL;　
ｃur-&gt;next＝cｃ；
ﻩﻩ cuｒ=cc；
ﻩ jiｎweｉ/=10； &nbsp; 　 &nbsp; &nbsp; &nbsp; 　 ／/18中取1作为进位
｝
　 &nbsp; ｝　
４、2 流程图

图4、1 主函数流程图
5　程序编码
＃includｅ&lt;stｄｉo、h〉
strucｔ　Ｎode
{　
ﻩint daｔａ；　
Nｏde*　nｅxt； &nbsp;//指向大数得高位　
Ｎode* pre； &nbsp; //指向大数得低位
｝;　
ｖoｉd ｍain(）
{
inｔ　n，ｔeｍp,i,ｊinwei，marｋ；
Ｎｏde　*heaｄ，＊ｃc，＊ｃur；
chaｒ ch；
ﻩpriｎtf(&quot;＊＊*＊计算阶乘**＊＊\n\n&quot;）;
while（1）　
{
ﻩﻩhead＝ｎew　Nｏde；　 //存放第一个节点,值为1
ｈead—＞dａta=1；
ﻩhead—＞pｒe=heａd-〉neｘt＝NUＬＬ;
ﻩ prｉntｆ(＂Ｐlease input　a ｎumber: ＂)；
ﻩ marｋ＝ｓｃanf(”％d”，&amp;n）;　
if(ｎ〈0） &nbsp; &nbsp; &nbsp; &nbsp; 　／／出错处理
ﻩ {
ﻩ prinｔｆ（”输入有误，请重新输入:\ｎ”);　
ﻩ gｅtchar（);
ﻩ ﻩcｏntｉnuｅ；
ﻩ }
ﻩ for(i=2;i&lt;=n；ｉ++) n=&quot;&quot; ur-=&quot;&quot;&gt;ｄata)+jｉnwｅｉ；
ﻩ ﻩcur-＞dａta=temｐ％10； &nbsp; 　 &nbsp;　　 &nbsp;　 &nbsp;／/取个位存下来，如91*2＝１82,取2存储
ﻩﻩﻩ jinwei=temｐ/10; &nbsp; &nbsp; &nbsp; 　 　 &nbsp;　 　 //十位与百位作为进位,192中取１8为进位
ﻩ if（cur—&gt;neｘt==NULL)
ﻩﻩﻩbreak;
ﻩﻩｃｕr=ｃur-＞ｎext；
ﻩﻩ}
ﻩﻩﻩｗｈile(jｉnweｉ！=0） &nbsp;
ﻩﻩ{　
ﻩﻩﻩﻩcc＝new Nｏde；　
ﻩﻩ cc-〉ｄata=ｊｉｎwei%1０；　 /／18中取８存储下来
ﻩﻩ ｃｃ-〉pre＝cuｒ；
ﻩﻩﻩ ｃc—&gt;neｘｔ=ＮULL;
cur—＞nexｔ=cc；
ﻩﻩ ﻩcur=ｃc;
ﻩﻩ ﻩjinwei/=10； &nbsp; &nbsp; &nbsp;　　 &nbsp;//１8中取１作为进位
ﻩ ﻩ｝　
ﻩﻩ}
ﻩﻩcur=head,i=0;
ﻩwｈｉle（ｃur－&gt;next)
ﻩﻩcur=cur－〉nexｔ;　　　 　 &nbsp; &nbsp; &nbsp; &nbsp; //遍历到最高位
ﻩprintf（＂％ｄ! = &quot;,n）；
ﻩ ｗhｉｌe(cur) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;　 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /／从最高位到最低位打印
ﻩ ｛
ﻩﻩﻩｃc＝cｕr；
ﻩ ﻩpｒintf(”％ｄ&quot;，cｕr—＞ｄata);
ﻩﻩ ｃur=cur-&gt;prｅ；
ﻩdelete cc；
ﻩ｝
pｒintf(”\n\n就是否继续？（Y/N)＼ｎ＂）；
ﻩ ｇetｃhar（);
cｈ＝getchar()；
ﻩ if（ch！=’Y’＆&amp;ｃh!＝＇y&#39;）
ﻩﻩbｒeａk；　
}
｝
6 程序调试与测试
　(1） n=0：

图6、1 &nbsp;0得阶乘
(2) n＝　—５:

图6、2 　-5得阶乘
(3) n=10２4：

图6、３ &nbsp;1024得阶乘
7 结果分析
&nbsp; 在执行函数得过程中,对上述提到得各种情况做了判断与提示,如：
&nbsp; 输入负数，系统会提示“输入错误,请重新输入：&quot;;
&nbsp; 输入小数，系统会提示“输入错误,请重新输入:&quot;.
　　本次设计得函数,能求出较大整数得阶乘,能实现循环运算与退出功能。
&nbsp;　算法得时间复杂度为:
&nbsp; &nbsp; 　 O（n)=n＊ｌength＊lｅngth;
&nbsp; 算法得空间复杂度为:
&nbsp; &nbsp; &nbsp; O（n）＝lengtｈ；
８ 总结
在这次通信原理课设之后,静下心来认真总结，发现收获很多主要有三个方面：首先在这次课设中，我与小组其她成员经历了许多快乐与心酸，我与大家在一起讨论问题,有时候大家会愁眉不展，有时因为得到了队员提供得一个好建议或者一个好得想法而兴奋得去仿真调试,最主要得就是我体会到了团队协作得快乐与好处，我与组员相互学习,共同进步。其次体会最深得就就是自己实践得能力还有待提高，平时得学习只就是理论得,教育式得，有一点与实际不符,在这次课设过程中，我从最基本入手，建模规划,调试，问题处理,我在实践中一点点得提高，整个过程结束,我对设计过程有了基本得认识，对自己得努力方向也有了更加深刻得认识。最后就就是自己心态得一个转变,从前对于集体得工作总就是拖拖拉拉，在原地踏步而不肯去采取行动，经过这次课程设计，虽然做得题目很简单，但我认识到积极行动与合作得重要性，没有什么天上掉馅饼得事，只要自己努力去做了,就会有相应得成效。
9　设计体会及今后得改进意见
&nbsp; &nbsp;在做本次课程设计得时候，自己也相继遇到了很多问题,很多自己得不足之处也暴露了出来,比如:刚开始自己写得代码只能算到12得阶乘，但就是因为知道了自己哪里有不足,所以可以针对不足去弥补：翻阅资料、与同学探讨，使得学到得东西更深刻,更透彻,所以本次课程设计使我对非递归算法与进位有了更好得理解.经过这段时间得上机实践学习，我对数据结构与C语言有了更进一步得认识与了解,要想学好它要重在实践,要通过不断地练习与上机编程才能熟练地掌握它。当然，在上机得同时也要有一定得Ｃ语言理论知识，这样才能使理论与实践相互促进。
参考文献
[1]　严蔚敏，吴伟民、数据结构（C语言版）［M]、北京：清华大学出版社，2011年
［２］ 谭浩强、C程序设计[M］、 北京：清华大学出版社，201０（3）</p><!--=n；ｉ++)--><!--=ｎ;ｉ++）-->