N矩阵的n次方运算及折半查找报告--数据结构(C语言)

1、数据结构作业报告n矩阵的n次方运算报告折半查找报告姓名：江海强班级：070921班学号：07092007上机时间：2010-9-29报告时间：2010-9-10摘要1.实验目的本实验主要是让我们了解函数的调用与返回，理解递归函数的执行过程，学会利用递归函数解决实际问题。2.实验方法本程序利用全局数组变量bnn来统筹整个程序，有一个主函数和一个子函数，其中子函数为矩阵换算的函数，也作为递归函数。而递归就是本程序的主要实验方法。本程序也定义了一个全局指针变量*mid，也是有一个主函数和一个子函数，其中子函数为折半查找的函数，也作为递归函数。而递归也就是本程序的主要实验方法。3.实验结果由运行出来的

2、结果可以看出，即使为一次方，此矩阵运算的结果与实际运算得到的结果完全是一样，所以此程序是正确的，成功的。由运行出来的结果可以看出，折半查找所找到的数的位置经过验证也是正确、无误的。即使输入要查找的数不在数组中，则程序会输出error来说明查找失败。故此程序也是正确的，成功的。注：这两个程序是用c语言编辑完成的。其中代表的是n矩阵的n次方运算的程序设计，代表的是折半查找的程序设计，如果没有特别说明，以下的都是代表这样的意思。内容一问题重述给出一个n阶矩阵a，利用递归编程快速计算矩阵a的n次幂给出一组按从小到大排序的数组，利用递归编程实现折半查找，查找出所要求查找的数所在的位置 二算法描述这两个程

3、序除了运用一些条件语句，判断语句之外，主要运用了递归算法。本程序中的子函数的复杂度为o(n2+n2+n3),即为o(n3)，而递归算法运用了子函数n-1次，所以复杂度为(n-1)o(n3)。本程序中折半查找的平均查找长度为asl，要考虑到是否查找成功，则开始输入n阶矩阵ann结束调用子函数jzhs（）输出运用for循环计算矩阵相乘再自身调用子函数jzhs（）再调用直到调用了子函数n-1次为止再运用for循环计算矩阵相乘结束输出开始直到调用到*mid=key或者key不存在数组中输入数组an和所要查找的数key自身调用子函数search(a,key,lo,(mid-)自身调用子函数search(

4、a,key,(mid+),hi)调用子函数seach（） 是 *midkey?否运用for语句赋值*mid，比较*mid与key的大小先不讨论*mid=key 三变量说明全局变量n代表的是矩阵为n阶，全局变量n代表的是n阶矩阵的n次方，而ann则代表的是n阶矩阵。全局变量n代表的是数组an的个数，key是所要查找的数，*lo、*hi和*mid分别代表数组的头、尾和中间指针，并且随着运算而变化。四函数与思路说明本程序分为一个主函数和一个子函数，其中子函数为jzhs()子函数。其中jzhs()子函数将主函数中调入的n阶矩阵，通过三个for循环，计算出n阶矩阵的二次方。再将得出的矩阵和原来的矩阵自身

5、调用，输入到jzhs()子函数中，即得到n阶矩阵的三次方，利用这样的递归进行运算直到算出矩阵的n次方为止。本程序也分为一个主函数和一个子函数，其中子函数为seach()子函数。其中seach()子函数将主函数调入的数组，通过指针指向数组的头和尾，求出*mid指向中间数组。若*midkey，则调用自身函数search(a,key,lo,(mid-)，直到查找到所要查的数或者要查找的数不在数组中为止。：1.第一次运行结果:从小到大排序好的数列为:1 2 3 4 5 6 7 8 9要查找的数是:4查找到的数是:4其存储位置为:0012ff602.第二次运行结果:从小到大排序好的数列为:1 2 3 4

6、 5 6 7 8 9要查找的数是:9查找到的数是:9其存储位置为:0012ff743.第三次运行结果:从小到大排序好的数列为:1 2 3 4 5 6 7 8 9要查找的数是:11error 五程序执行结果：1.第一次运行结果：输入的3阶矩阵为:1 1 11 1 11 1 13阶矩阵的4次幂的矩阵为:27 27 2727 27 2727 27 272.第二次运行结果:输入的3阶矩阵为:1 0 00 1 00 0 13阶矩阵的4次幂的矩阵为:1 0 00 1 00 0 13.第三次运行结果:输入的3阶矩阵为:1 2 34 5 67 8 93阶矩阵的1次幂的矩阵为:1 2 34 5 67 8 9六结

7、论由上面的运行结果可以看出，矩阵运算结果是正确的，折半查找也是正确的。在矩阵运算程序中，只要在全局变量n，n修改一下数据就可以改变矩阵的阶数和次方数，同样的，在折半查找中，改变数组的个数可以通过改变全局变量n,这样子会方便许多。七编程中遇到的问题以及解决方法在编程过程中，刚开始对矩阵的相乘不太熟悉，导致一些小错误，后来自己归纳矩阵相乘的规律很快就解决了这个问题。当编好程序，运行成功，也遇上了一个问题，就是当n=1时，即矩阵为一次矩阵，不用运算，反而输出错误。后来在原来的程序上增加了几条语句，调试几次就通过了。在刚刚开始的编程过程中，我把输出放在了子函数处，导致输出结果好几次，后来引入了全局指针

8、*mid变量，把输出语句放回主函数处，从而解决了问题。编好程序之后，才发现没有把查找失败的情况算进去，后来就把子函数由void型修改为int型，通过return 1来说明查找成功，输出储存地址，return 0来说明查找失败。八附录：#include#define n 3#define n 4void jzhs(int xnn,int ynn,int z);int bnn=0;void main()int i,j,ann;printf(输入的%d阶矩阵为:n,n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&aij); for(i=0;in;i+)for(j=0

9、;jn;j+)bij=aij;jzhs(a,a,n);printf(%d阶矩阵的%d次幂的矩阵为:n,n,n);for(i=0;in;i+)for(j=0;jn;j+)printf(%dt,bij);printf(n);void jzhs(int xnn,int ynn,int z)int i,j,k,cnn,tnn;if(z=1) ;elsefor(i=0;in;i+)for(j=0;jn;j+)cij=yij; tij=xij; for(i=0;in;i+) for(j=0;jn;j+)bij=0;z-; for(i=0;in;i+) for(j=0;jn;j+) for(k=0;kn;k

10、+) bij+=tik*ykj; jzhs(b,c,z);：#include #define n 9int search(int x,int key,int *p,int *q);int *mid=0;void main()int i,t,key,an; printf(从小到大排序好的数列为:n);for(i=0;in;i+) scanf(%d,&ai); printf(要查找的数是:);scanf(%d,&key); int *lo=&a0,*hi=&an-1;t=search(a,key,lo,hi);if(t=1)printf(查找到的数是:%dn其存储位置为:%pn,*mid,mid);if(t=0)printf(errorn);int search(int a,int