课程设计：数据结构课程设计(精华版)

1/1课程设计：数据结构课程设计(精华版)

数据结构课程设计

设计说明书

N!非递归算法的设计与实现

同学成

学号1118064050

班级网络1102班

成果

指导老师余冬梅

数学与计算机科学学院2023年1月5日

课程设计任务书

2023—2023学年第一学期

设计容：

本次课程设计的任务是N!非递归算法的设计与实现，在设计过程中应留意n值大小与数据类型表数围之间的关系，并尽可能求出较大n值的阶乘。

通过本次的实践，要求同学完成以下任务：

（一）阐述设计思想，画出流程图；

（二）说明测试方法，写出完整的运行结果；

（三）从时间、空间对算法效率进行分析；

（四）较好的界面设计；

（五）加强团队合作精神，开拓创新力量；

（六）编写课程设计报告，文档资料完整规。

指导老师：余冬梅教研室负责人：余冬梅

课程设计评阅

名目

1课题描述(1)

2需求分析(1)

3概要设计(1)

4具体设计(2)

4.1定义存储结构和部分代码(2)

4.2流程图(3)

5程序编码(4)

6程序调试与测试(6)

7结果分析(8)

8总结(8)

9设计体会及今后的改进意见(8)

1课题描述

尽管递归算法是一种自然且合乎规律的解决问题的方式，但递归算法的执行效率通常比较差。因此在求解很多问题时常采纳递归算法来分析问题，用非递归方法来求解问题，另外一些程序不支持递归算法来求解问题，所以我们都会用非递归算法来求解问题。

本次课程设计主要容是：用非递归算法实现n!的计算，由于计算机中数据的存储围有限，而又要求出尽可能大的n的阶乘的值，用链表构造n的运算结果的存储结构，用链式存储方式，最终输出n!的运算结果。

本次课程设计的目的是：通过本次课程设计，可以使大家了解缓存中数据的存储围，提高自学力量，增加团队合作意识。

2需求分析

在本次n!非递归算法的课程设计中主要用到的学问有：链表、函数，选择条件中的结构语句（ifelse），和循环结构语句中的语句while语句、do…while语句和for语句，选择语句if的运用。

对n!的非递归的算法，主要是运用非递归的算法实现n的阶乘。

限制条件：

1.要求的n必需是整数；

2.n的围；

3.数据类型和表数围。

3概要设计

递归和非递归算法是相通的，递归是一种直接或间接调用自身的算法，而非递归不调用自身函数。

递推采纳的是递归和归并法，而非递推只采纳递归法。递推法一般简单溢出，所以一般都采纳递推法分析，而用非递推法设计程序。

本次试验分为两个步骤：

(1).实现阶乘的模块m(n):从2开头连乘到n，实现求n的阶乘，相对简洁，简单计算。

(2).当n较大时，假如用int型结果就会溢出，所以实现阶乘需要特别处理:从较小值开头，进行数值分解，比如将182分解为18和2，2存储在链表数据域的其次个位置（第一个位置是1，表示0的阶乘是1），然后将18作为进位，假如进位不为0，则连续分解。最终会以1,8,2的形式存储在链表当中，这样就不存在存的溢出。最终通过遍历的方法，遍历到最高位，及1，然后依次输出后续的数字，便是阶乘的结果。

4具体设计

4.1定义存储结构和部分代码

#include

//结构体列表

structNode

{

intdata;

Node*next;//指向大数的高位

Node*pre;//指向大数的低位

};

//非递归算法计算阶乘

for(i=2;idata)+jinwei;

cur->data=temp%10;//取个位存下来,如91*2=182,取2存储

jinwei=temp/10;//十位和百位作为进位,192中取18为进位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存储下来

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作为进位

}

}

4.2流程图

图4.1主函数流程图

5程序编码

#include

structNode

{

intdata;

Node*next;//指向大数的高位

Node*pre;//指向大数的低位

};

voidmain

{

intn,temp,i,jinwei,mark;

Node*head,*cc,*cur;

charch;

printf("****计算阶乘****\n\n");

while(1)

{

head=newNode;//存放第一个节点,值为1

head->data=1;

head->pre=head->next=NULL;

printf("Pleaseinputanumber:");

mark=scanf("%d",

if(ndata)+jinwei;

cur->data=temp%10;//取个位存下来,如91*2=182,取2存储

jinwei=temp/10;//十位和百位作为进位,192中取18为进位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存储下来

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作为进位

}

}

cur=head,i=0;

while(cur->next)

cur=cur->next;//遍历到最高位

printf("%d!=",n);

while(cur)//从最高位到最低位打印

{

cc=cur;

printf("%d",cur->data);

cur=cur->pre;

deletecc;

}

printf("\n\n是否连续?(Y/N)\n");

getchar;

ch=getchar;

if(ch!='Y'

}

}

6程序调试与测试

(1)n=0：

图6.10的阶乘(2)n=-5：

图6.2-5的阶乘

(3)n=1024：

图6.31024的阶乘

7结果分析

在执行函数的过程中，对上述提到的各种状况做了推断和提示，如：

输入负数，系统会提示“输入错误，请重新输入：”；

输入小数，系统会提示“输入错误，请重新输入：”。

本次设计的函数，能求出较大整数的阶乘，能实现循环运算和退出功能。

算法的时间简单度为：

O（n）=n*length*length;

算法的空间简单度为:

O（n）=length;

8总结

在这次通信原理课设之后，静下心来仔细总结，发觉收获许多主要有三个方面：首先在这次课设中，我和小组其他成员经受了很多欢乐与心酸，我和大家在一起争论问题，有时候大家会愁眉不展，有时由于得到了队员供应的一个好建议或者一个好的想法而兴奋的去仿真调试，最主要的是我体会到了团队协作的欢乐与好处，我和组员相互学习，共同进步。其次体会最深的就是自己实践的力量还有待提高，平常的学习只是理论的，教育式的，有一点与实际不符，在这次课设过程中，我从最基本入手，建模规划，调试，问题处理，我在实践中一点点的提高，整个过程结束，我对设计过程有了基本的熟悉，对自己的努力方向也有了更加深刻的熟悉。最终就是自己心态的一个转变，从前对于集体的工作总是拖拖拉拉，在原地踏步而不愿去实行行动，经过这次课程设计，虽然做的题目很简洁，但我熟悉到乐观行动与合作的重要性，没有什么天上掉馅饼的事，只要自己努力去做了，就会有相应的成效。

9设计体会及今后的改进意见

在做本次课程设计的时候，自己也相继遇到了许多问题，许多自己的不足之处也暴露了出来，比如：刚开头自己写的代码只能算到