数据结构课程设计

设计说明书

2014年 1 月 5 日  

课程设计任务书

2013  —  2014  学年第 一 学期

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

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

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

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

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

（4）较好的界面设计；

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

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

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

课程设计评阅

评语：

                                指导教师签名：

采用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)

                    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作为进位

            } 

        } 

        cur=head,i=0;

        while(cur->next)

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

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

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

        {

            cc=cur;

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

            cur=cur->pre; 

            delete cc; 

        } 

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

        getchar(); 

        ch=getchar(); 

        if(ch!='Y'&&ch!='y') 

            break; 

    }

}

6 程序调试与测试

  (1) n=0：

图6.1  0的阶乘

(2) n= -5：

图6.2  -5的阶乘

(3) n=1024：

图6.3  1024的阶乘

7 结果分析

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

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

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

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

   算法的时间复杂度为：

       O（n）=n*length*length;

   算法的空间复杂度为:

       O（n）=length;

8 总结

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

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

    在做本次课程设计的时候，自己也相继遇到了很多问题，很多自己的不足之处也暴露了出来，比如：刚开始自己写的代码只能算到12的阶乘，但是因为知道了自己哪里有不足，所以可以针对不足去弥补：翻阅资料、和同学探讨，使得学到的东西更深刻，更透彻，所以本次课程设计使我对非递归算法和进位有了更好的理解。经过这段时间的上机实践学习，我对数据结构和C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断地练习和上机编程才能熟练地掌握它。当然，在上机的同时也要有一定的C语言理论知识，这样才能使理论和实践相互促进。

参考文献

[1] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，2011年

[2] 谭浩强.C程序设计[M]. 北京：清华大学出版社,2010（3）下载本文