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

数据结构课程设计

设计说明书

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

学生成

学号1118064050

班级网络1102班

成绩

指导教师余冬梅

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

课程设计任务书

2013 — 2014 学年第一学期

设计容：

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

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

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

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

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

（四）较好的界面设计；

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

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

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

课程设计评阅

摘要

采用VC++作为软件开发环境，编写设计了一个非递归算法实现 n! 的计算，该软件具有计算从0到任何数之间整数的阶乘的功能。采用链式存储结构，遍历出运算结果，按照栈的先进后出思想输出结果，实现了整数的阶乘运算，界面清晰，易于用户使用。

关键词：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)

参考文献 (9)

1 课题描述

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

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

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

2 需求分析

在本次n!非递归算法的课程设计中主要用到的知识有：链表、函数，选择条件中的结构语句（if....else），和循环结构语句中的语句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

//结构体列表

struct Node

{

int data;

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

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

};

//非递归算法计算阶乘

for(i=2;i<=n;i++) //从2开始连乘到n

{

cur=head;

jinwei=0;

while(1)

{

temp=i*(cur->data)+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=new Node;

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

struct Node

{

int data;

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

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

};

void main()

{

int n,temp,i,jinwei,mark;

Node *head,*cc,*cur;

char ch;

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

while(1)

{

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

head->data=1;

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

printf("Please input a number: ");

mark=scanf("%d",&n);

if(n<0) //出错处理

{

printf("输入有误，请重新输入:\n");

getchar();

continue;

}

for(i=2;i<=n;i++) //从2开始连乘到n

{

cur=head;

jinwei=0;

while(1)

{

temp=i*(cur->data)+jinwei;

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

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

if(cur->next==NULL)