西工大数据结构实验报告 矩阵运算.doc

数据结构实验报告一实验题目必做：稀疏矩阵转置、加法(行逻辑链接表)选做：稀疏矩阵乘法二程序设计(一) 需求分析1.程序运行步骤：（1）开始；（2）选择要进行的运算：1.矩阵转置2.矩阵加法3.矩阵乘法；（3）选择矩阵运算后，输入矩阵；（4）对矩阵进行相应的运算；（5）输出运算结果；（6）结束。（二）概要设计程序模块及思想：1主函数主函数的主体是一个switch选择结构。内部分为三种情况：矩阵转置、矩阵加法和矩阵乘法。（1） 矩阵转置运算：（1） 输入矩阵；（2） 输出这个矩阵；（3） 转置这个矩阵；（4） 输出转置后的结果；（5） 结束。（2） 矩阵加法运算：（1） 输入矩阵A和矩阵B；（2） 输出这两个矩阵；（3） 将两个矩阵相加；（4） 输出相加后的结果；（5） 结束。（3） 矩阵乘法运算：（1）输入矩阵A和矩阵B；（2）输出这两个矩阵；（3）将两个矩阵相加；（4）输出相加后的结果；（5）结束。2基本操作。 typedef struct int i,j; ElemType e; Triple; 操作结果：定义三元组typedef struct Triple dataMAXSIZE+1; int mu,nu,tu,cnumMAXSIZE+1,rnumMAXSIZE+1,cpotMAXSIZE+1,rposMAXSIZE+1; /某一列非零元的个数，某一行非零元的个数，某一列第一个非零元在b.data中的位置，某一行非零元在b.data中的位置 TSMatrix; 操作结果：定义稀疏矩阵int GetSMatrix(TSMatrix &t) 操作结果：创建稀疏矩阵，以三元组表形式储存int TransposeSMatrix(TSMatrix M,TSMatrix &T)操作结果：转置矩阵int PrintSMatrix(TSMatrix t)操作结果：输出矩阵int AddSMatrix(TSMatrix t,TSMatrix s,TSMatrix &a)操作结果：矩阵相加（三）详细设计1结构体定义typedef struct int i,j; /行，列 ElemType e; /非零元素的值 Triple; 操作结果：定义三元组typedef struct Triple dataMAXSIZE+1; int mu,nu,tu,cnumMAXSIZE+1,rnumMAXSIZE+1,cpotMAXSIZE+1,rposMAXSIZE+1; /行数，列数，非零元素个数，某一列非零元的个数，某一行非零元的个数，某一列第一个非零元在b.data中的位置，某一行非零元在b.data中的位置 TSMatrix; 操作结果：定义稀疏矩阵2.每个模块的分析：（1） 主程序模块：int main() int k; TSMatrix t,s,a; printf(请输入需要执行的操作的序号：（1.矩阵转置 2.矩阵相加 3.矩阵乘法）n); scanf(%d,&k); switch(k) case(1): GetSMatrix(t); /转置模块 printf(输入的矩阵为：n); PrintSMatrix(t); TransposeSMatrix(t,s);printf(转置后的矩阵为：n);PrintSMatrix(s); break; case(2): printf(请依次输入两个矩阵n); /加法模块GetSMatrix(t);printf(nn); GetSMatrix(s); printf(输入的两个矩阵分别为：n);printf(矩阵a：n); PrintSMatrix(t); printf(矩阵b：n);PrintSMatrix(s); if(t.mu!=s.mu|t.nu!=s.nu) printf(ERROR);else AddSMatrix(t,s,a); printf(相加后的矩阵为：n);PrintSMatrix(a); break; case(3): printf(请依次输入两个矩阵n); /乘法模块GetSMatrix(t); printf(nn); GetSMatrix(s); printf(输入的两个矩阵分别为：n);printf(矩阵a：n); PrintSMatrix(t); printf(矩阵b：n);PrintSMatrix(s); if(t.nu!=s.mu) printf(ERRORn);else MultSMatrix(t,s,a);printf(相乘后的矩阵为：n);PrintSMatrix(a); break;return 0; （2） 基本操作函数：（1） 矩阵的创建：int GetSMatrix(TSMatrix &t) /创建稀疏矩阵，以三元组表形式储存 int i,k; um0=0;t.cpot0=1;t.rnum0=0,t.rpos0=1; /第零列非零元的个数，第零行非零元的个数，第零列第一个非零元在b.data中的位置，第零行非零元在b.data中的位置等参数的初始值为零 printf(请输入矩阵的行数、列数以及非零元个数：n);scanf(%d %d %d,&t.mu,&t.nu,&t.tu);printf(请依次输入%d个非零元的行数、列数以及非零元的值：n,t.tu);for (i=1;i=t.tu;i+) scanf(%d %d %d,&t.datai.i,&t.datai.j,&t.datai.e); /输入每个非零元素的行坐标，列坐标和值 for(i=1;i=t.nu;i+) t.cpoti=t.cpoti-1+umi-1; /某一列第一个非零元素在t.data中的位置等于上一列第一个非零元在t.data中的位置加上上一列的非零元个数 umi=0; /这一列非零元的个数初始值为零 for(k=1;k=t.tu;k+) if(t.datak.j=i) umi+=1; /求这一列非零元的个数 for(i=1;i=t.mu;i+) t.rposi=t.rposi-1+t.rnumi-1; /某一行第一个非零元在t.data的位置等于上一行第一个非零元在t.data中的位置加上上一行的非零元个数 t.rnumi=0; /这一行非零元的个数初始值为零 for(k=1;k=t.tu;k+) if(t.datak.i=i) t.rnumi+=1; /求这一行非零元的个数 return OK; （2）矩阵的转置int TransposeSMatrix(TSMatrix M,TSMatrix &T) /转置矩阵T.mu=M.nu; /T的行数与M的列数相同T.nu=M.mu; /T的列数与M的列数相同T.tu=M.tu;int col,p,q; if(T.tu)q=1;for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j = col)T.dataq.i = M.datap.j; /将转置后的矩阵M的赋值给TT.dataq.j = M.datap.i;T.dataq.e = M.datap.e;+q; return OK;（3） 矩阵的加法：int AddSMatrix(TSMatrix t,TSMatrix s,TSMatrix &a) /矩阵相加int i,k,j,q=1; a.mu=t.mu;a.nu=t.nu; a.tu=0; /S,T矩阵的行列必须相同for(i=1;i=t.mu;i+) k=t.rposi; j=s.rposi; /k,j分别等于每一列第一个非零元在的T.data和s.data中的位置if(i=t.mu) /如果i等于行数t.rposi+1=t.rposi+t.tu-k+1; /下一行第一个非零元在t.data中的位置等于总非零元的个数加一s.rposi+1=s.rposi+s.tu-j+1; /求下一行第一个非零元在s.data中的位置 while(kt.rposi+1&js.rposi+1) /当t与s还有非零元存在时if(t.datak.j!=s.dataj.j) /当T与S列行坐标不相等时if(t.datak.js.dataj.j) /当t的列坐标小于s的列坐标时a.dataq.i=i;a.dataq.j=t.datak.j; /a.dataq赋值为t.dataka.dataq.e=t.datak.e; q+;k+;a.tu+; else /a.dataq赋值为s.dataqa.dataq.i=i;a.dataq.j=s.dataj.j;a.dataq.e=s.dataj.e;q+;j+;a.tu+; else /当T与S列行坐标相等时a.dataq.i=i;a.dataq.j=t.datak.j;a.dataq.e=t.datak.e+s.dataj.e;q+;k+; /相加j+;a.tu+; while(kt.rposi+1) /若仅有t还有非零元a.dataq.i=i;a.dataq.j=t.datak.j; /a.dataq赋值为t.dataqa.dataq.e=t.datak.e; q+;k+;a.tu+; while(js.rposi+1) /若仅s还有非零元a.dataq.i=i;a.dataq.j=s.dataj.j; / a.dataq赋值为s.dataqa.dataq.e=s.dataj.e; q+;j+;a.tu+; return OK;（4） 矩阵的乘法int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) int arow,brow,ccol,ctempMAXSIZE+1,tp,t,p,q,i;if(M.nu!=N.mu) return ERROR; Q.mu=M.mu;Q.nu=N.nu; /确定矩阵的参数Q.tu=0; if(M.tu*N.tu!=0) for(arow=1;arow=M.mu;+arow) for(i=1;i=N.nu;i+) ctempi=0; /累加器清零Q.rposarow = Q.tu+1; /每一个Q.rposarow赋相同的初值Q.tu+1。 if(arowM.mu) tp=M.rposarow+1; /定位驱动元素M.datap的范围。M每一行在M.data 中元素范围， /M.rposarrow, M.rposarrow+1,但是最后一行的范围M.rposarrow，M.tu+1, M.tu与tu不同,不是转置运算else tp=M.tu+1; for(p=M.rposarow; ptp; +p) /遍历M的一行元素，M.rposarow，tp,驱动元素M.datapbrow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1;for(q=N.rposbrow; qt; +q) ccol=N.dataq.j; /相乘ctempccol+=M.datap.e*N.dataq.e;for(ccol=1;ccol MAXSIZE) return ERROR;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempccol; return OK;(四) 程序使用说明及测试结果程序运行截图如下：1.矩阵转置 （2）矩阵加法：（3）矩阵乘法：（五）、实验总结(实验心得)1.你在编程过程中花时多少？ 答：从设计到编写，从调试到完成，直至最终完成实验报告一共用了约八个小时。2.多少时间在纸上设计？答：两个小时。3.多少时间上机输入和调试？答：四个多小时。4.多少时间在思考问题？答：设计前就思考，直至完成报告，十个小时。5.遇到了哪些难题？又是怎么克服的？答：答：在做这项作业时。我可以说自己遇到了无数难题，以为我的C语言成绩并不好，栈的熟悉度恐怕只有10%。因此完成这项作业的过程可谓艰辛。首先遇到的困难就是设计程序。去年C语言学得很不扎实，我对三元组的结构都不甚了解，更别说运用与之相关的算法了。在设计程序之前：我花了很长时间复习书上与之相关的算法。在周五下午数据结构的实验课上，我又将数据结构书上的算法仔细分析了一遍。由于知识的匮乏，我只能先将书上的三元组稀疏矩阵有关的算法逐句逐句的分析，然后在纸上设计相应的流程。最后凭借自己的知识，并利用同学的帮助，磕磕绊绊地编写了程序。接下来的困难，也就是最大，最麻烦，解决起来最耗费脑力，最枯燥乏味的问题调试程序。最初的程序编译之后，问题触目惊心，我根据系统的提示，首先补上了缺失的间隔符，又定义了遗漏的变量，再次编译，错误有所减少，但依然多，我又重新修改。接下来的错误越来越“高级”，数据类型，返回类型，函数类型等有关