数据结构实验报告四

实验日期  2010/12/22 室温             报告日期   2010/12/22  成绩              

报告内容：(目的和要求，原理，步骤，数据，计算，小结等)

实验名称：          实验四  递归程序设计

一、实验目的：

（1）理解递归程序设计基本方法。

（2）熟练运用C语言实现递归算法的编程。

（3）灵活运用递归算法解决实际问题。

二、实验内容：

（1）根据整数乘法运算的特点，给出整数乘法运算的递归实现方法。

（2）编写一个递归实现乘法运算法函数，并进行测试，验证设计的正确性。

三、实验学时：2学时

四、实验涉及知识点：

1.在定义一个过程或函数时又出现调用本过程或本函数的成分，成为递归。

2.递归适用于“问题的定义是递归的”、“数据结构是递归的”、“问题的求解方法是递归的”等几种情况下使用；

3.递归算法中要包含递归体和递归出口，前者确定求解的递推关系，后者确定递归何时结束。

五、程序流程分析：

本实验的顺序递归和链式递归实现两个整数乘法运算的程序都分别包含一个子程序和一个主程序

顺序存储结构实现递归乘法运算的程序流程图如下：

图1.顺序存储结构实现递归乘法运算的主程序操作流程图

图2.顺序存储结构实现递归乘法运算的子程序操作流程图

链式存储结构实现递归乘法运算的程序流程图如下：

图3.链式存储结构实现递归乘法运算的主程序操作流程图

图4.链式存储结构实现递归乘法运算的子程序操作流程图

六、实验源程序：

用顺序存储结构实现递归乘法运算的源程序为：

#include

long int multiply(int m,int n)

{

    long int t;

    if(m==0)

        return 0;

    else if(m==1)

        return n;

    else

        return n+multiply(m-1,n);                //m*n=(m-1)*n+n;

}

void main()

{

    while(1)

    {

    int m,n;                //m和n代表进行相乘运算的两个数

    long int mul;                    //mul代表乘积结果

    printf("请输入两个数据:\\n");

    scanf("%d",&m);

    scanf("%d",&n);

    mul=multiply(m,n);

    printf("这两个数的乘积为%d。\n",mul);

    }

}

用链式存储结构实现递归乘法运算时，对链表操作时仍然可以运用书中的对单链表的基本操作的算法，具体包括初始化、数据的插入、将这些操作的算法和单链表的数据结构写入头文件“xianxinglianbiao.h”，并在主程序中包含，具体的程序如下：

头文件“xianxinglianbiao.h”中的程序为：

#include

typedef int    datatype;

typedef struct node

{

    datatype data;

    struct node *next;

}lnode,*pnode,*linklist;

int initlist(linklist *h)

{

    *h=(linklist)malloc(sizeof(lnode));

    if(!h)

    {

        printf("初始化链表错误!\\n");

        return 0;

    }

(*h)->next=NULL;

    return 1;

}

int listinsert(linklist h,int pos_in,datatype item_in)

{

    pnode p=h,q;

    int i=0;

while(p&&i    {

     p=p->next;

        i++;

    }

if(!p||i>pos_in-1)

    {

        printf("插入位置不合法!\\n");

        return 0;

    }

    q=(pnode)malloc(sizeof(lnode));

    if(!q)

    {

        printf("不能生成新结点\n");

        return 0;

    }

q->data=item_in;

q->next=p->next;

p->next=q;

    return 1;

}

用链式存储结构实现递归乘法运算的主程序为：

#include

#include "xianxinglianbiao.h"

long int multiply(linklist h)

{

if(!h->next)

     return h->data;

    else

     return h->data*multiply(h->next);

}

int main()

{

    int    m,n;

    long int mul;            //mul代表乘积结果

    linklist h=NULL;

    initlist(&h);    

    printf("请输入两个数据:\\n");

        scanf("%d",&m);

        scanf("%d",&n);

        if(!listinsert(h,1,m))

        {

            printf("将数据插入链表时出现错!\\n");

            return 0;

        }

        if(!listinsert(h,2,n))

        {

            printf("将数据插入链表时出现错!\\n");

            return 0;

        }

mul=multiply(h->next);    

    printf("这两个数的乘积为%d:\\n",mul);

}

七、实验步骤

顺序存储结构的递归乘法运算的实验步骤：

1.进行Visual Studio开发环境；

2.创建项目：

文件—新建—项目—WIN32项目—输入项目名称test5；

3.创建源文件sxdiguimul.c，将预先编制好的程序输入；

4.保存文件；

5.选择调试—开始调试。

对于链式队列的实验步骤，与上述步骤略有不同，首先项目名称为test6，另外还应该先编写头文件xianxinglianbiao.h以及在源文件的开头包含此头文件，当然输入的程序也是不同的。

由于我在顺序存储结构的递归乘法运算的程序中加了while（1）的常成立的循环控制语句，所以可以不断地输入两个数，进行乘法运算，调试比较方便，但是调试时应该注意除了输入一般的自然数进行相乘以后，还应该照顾特殊情况，即乘数或者被乘数为0的情况，

顺序存储结构的递归乘法运算的调试结果如下所示：

图1. 顺序存储结构的递归乘法运算程序运行结果

链式存储结构实现的递归乘法运算的调试结果如下所示：

图2. 链式存储结构实现的递归乘法运算的运行结果（2乘3）

图3. 链式存储结构实现的递归乘法运算的运行结果（2乘0）

图4. 链式存储结构实现的递归乘法运算的运行结果（0乘3）

八、实验小结

     本次实验在编写的过程中又一次深深地体会到了用递归实现的数据处理方法的巧妙，对于同一大类的问题都可以用递归来轻易实现，本身在编写程序、调试程序的过程中并没有出现问题，只不过是让老师检查的时候，发现一个问题：就是存在对题意的曲解，题目的意思只是实现两个整数的相乘运算，而我认为既然要用递归，想必不是简单的两个数相乘的问题，所以就想当然地给题目换了意思，理解成了几个整数相乘的问题，虽然不是一般性还可以实现两个整数的相乘的功能，但是已经不是题目所表达的意思了，所以我又对原有程序进行了简单的修改，实现了两个数相乘的运算。

    我应该吸取这次的教训，在以后的学习、考试也或者是研究工作中，首先的第一步是搞清楚自己的设计任务，理清流程，然后再去实施设计，否则可能既浪费了精力和时间，而且还搞出错误的结果。