数据结构实验报告四

附页第页陕西科技大学实验报告第页班级学号姓名实验组别实验日期2010/12/22室温报告日期2010/12/22成绩报告内容：(目的和要求，原理，步骤，数据，计算，小结等)实验名称：实验四递归程序设计一、实验目的：理解递归程序设计基本方法。熟练运用C语言实现递归算法的编程。灵活运用递归算法解决实际问题。二、实验内容：根据整数乘法运算的特点，给出整数乘法运算的递归实现方法。编写一个递归实现乘法运算法函数，并进行测试，验证设计的正确性。三、实验学时：2学时四、实验涉及知识点：在定义一个过程或函数时又出现调用本过程或本函数的成分，成为递归。递归适用于“问题的定义是递归的”、“数据结构是递归的”、“问题的求解方法是递归的”等几种情况下使用；递归算法中要包含递归体和递归出口，前者确定求解的递推关系，后者确定递归何时结束。五、程序流程分析：本实验的顺序递归和链式递归实现两个整数乘法运算的程序都分别包含一个子程序和一个主程序顺序存储结构实现递归乘法运算的程序流程图如下：图1.顺序存储结构实现递归乘法运算的主程序操作流程图图2.顺序存储结构实现递归乘法运算的子程序操作流程图链式存储结构实现递归乘法运算的程序流程图如下：图3.链式存储结构实现递归乘法运算的主程序操作流程图图4.链式存储结构实现递归乘法运算的子程序操作流程图六、实验源程序：用顺序存储结构实现递归乘法运算的源程序为：#include<stdio.h>longintmultiply(intm,intn){ longintt; if(m==0) return0; elseif(m==1) returnn; else returnn+multiply(m-1,n); //m*n=(m-1)*n+n;}voidmain(){ while(1) { intm,n; //m和n代表进行相乘运算的两个数 longintmul; //mul代表乘积结果 printf("请输入两个数据:\n"); scanf("%d",&m); scanf("%d",&n); mul=multiply(m,n); printf("这两个数的乘积为%d。\n",mul); }}用链式存储结构实现递归乘法运算时，对链表操作时仍然可以运用书中的对单链表的基本操作的算法，具体包括初始化、数据的插入、将这些操作的算法和单链表的数据结构写入头文件“xianxinglianbiao.h”，并在主程序中包含，具体的程序如下：头文件“xianxinglianbiao.h”中的程序为：#include<malloc.h>typedefint datatype;typedefstructnode{ datatypedata; structnode*next;}lnode,*pnode,*linklist;intinitlist(linklist*h){ *h=(linklist)malloc(sizeof(lnode)); if(!h) { printf("初始化链表错误!\n"); return0; } (*h)->next=NULL; return1;}intlistinsert(linklisth,intpos_in,datatypeitem_in){ pnodep=h,q; inti=0; while(p&&i<pos_in-1) { p=p->next; i++; } if(!p||i>pos_in-1) { printf("插入位置不合法!\n"); return0; } q=(pnode)malloc(sizeof(lnode)); if(!q) { printf("不能生成新结点\n"); return0; } q->data=item_in; q->next=p->next; p->next=q; return1;}用链式存储结构实现递归乘法运算的主程序为：#include<stdio.h>#include"xianxinglianbiao.h"longintmultiply(linklisth){ if(!h->next) returnh->data; else returnh->data*multiply(h->next);}intmain(){ int m,n; longintmul; //mul代表乘积结果 linklisth=NULL; initlist(&h); printf("请输入两个数据:\n"); scanf("%d",&m); scanf("%d",&n); if(!listinsert(h,1,m)) { printf("将数据插入链表时出现错!\n"); return0; } if(!listinsert(h,2,n)) { printf("将数据插入链表时出现错!\n"); return0; } mul=multiply(h->next); printf("这两个数的乘积为%d:\n",mul);}七、实验步骤顺序存储结构的递归乘法运算的实验步骤：进行VisualStudio开发环境；创建项目：文件—新建—项目—WIN32项目—输入项目名称test5；创建源文件sxdiguimul.c，将预先编制好的程序输入；保存文件；选择调试—开始调试。对于链式队列的实验步骤，与上述步骤略有不同，首先项目名称为test6，另外还应该先编写头文件xianxinglianbiao.h以及在源文件的开头包含此头文件，当然输入的程序也是不同的。由于我在顺序存储结构的递归乘法运算的程序中加了while（1）的常成立的循环控制语句，所以可以不断地输入两个数，进行乘法运算，调试比较方便，但是调试时应该注意除了输入一般的自然数进行相乘以后，还应该照顾特殊情况，即乘数或者被乘数为0的情况，顺序存储结构的递归乘法运算的调试结果如下所示：图1.顺序存储结构的递归乘法运算程序运行结果链式存储结构实现的递归乘法运算的调试结果如下所示：图2.链式存储结构实现的递归乘法运算的运行结果（2乘3）图3.链式存储结构实现的递归乘法运算的运行结果（2乘0）图4.链式存储结构实现的递归乘法运算的运行结果（0乘3）八、实验小结本次实验在编写的过程中又一次深深地体会到了用递归实现的数据处理方法的巧妙，对于同一大类的问题都可以用递归来轻易实现，本身在编写程序、调试程序的过程中并没有出现问题，只不过是让老师检查的时候，发现一个问题：就是存在对题意的曲解，题目的意思只是实现两个整数的相乘运算，而我认为既然要用递归，想必不是简单的两个数相乘的问题，所以就想当然地给题目换了意思，理解成了几个