数据结构稀疏矩阵转置,加法

1/8《数据结构》实验报告◎实验题目:稀疏矩阵的转置、加法（行逻辑链接表）◎实验目的：学习使用三元组顺序表表示稀疏矩阵，并进行简单的运算◎实验内容：以三元组表表示稀疏矩阵，并进行稀疏矩阵的转置和加法运算。一、需求分析该程序目的是为了用三元组表实现稀疏矩阵的转置和加法运算。1、输入时都是以三元组表的形式输入；2、输出时包含两种输出形式：运算后得到的三元组表和运算后得到的矩阵；3、测试数据：（1）转置运算时输入三元组表：121213931-3361443245218611564-7得到转置后的三元组表：13-3161521122518319342446-76314（2）进行加法运算时先输入矩阵A（以三元组表形式）：11122223431-4输入矩阵B（以三元组表形式）：13-223-531832-6A与B的和矩阵以矩阵形式输出为：10-202-14-60(二)概要设计为了实现上述操作首先要定义三元组表，稀疏矩阵：typedefstruct{inti,j;inte;}Triple;//三元组2/8typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}Matrix;//稀疏矩阵1.基本操作voidCreatMatrix(Matrix*m)操作结果：创建一个稀疏矩阵。voidPrintMatrix(Matrixm)初始条件：矩阵m已存在。操作结果：将矩阵m以矩阵的形式输出。voidFastTransposeMatrix(Matrixa,Matrix*b)初始条件：稀疏矩阵a已存在；操作结果：将矩阵a进行快速转置后存入b中。voidAddMatrix(Matrixa,Matrixb,Matrix*c)初始条件：稀疏矩阵a和b都已存在；操作结果：将矩阵a和b的和矩阵存入c中。2.本程序包含了两个模块：（1）头文件模块；其中包括定义三元组表Triple和稀疏矩阵Matrix，以及创建矩阵voidCreatMatrix(Matrix*m)和输出矩阵voidPrintMatrix(Matrixm)两个函数；（2）主程序模块；包括主函数main()，快速转置函数voidFastTransposeMatrix(Matrixa,Matrix*b)和实现矩阵相加函数voidAddMatrix(Matrixa,Matrixb,Matrix*c)(三)详细设计定义三元组和稀疏矩阵类型：typedefstruct{inti,j;inte;}Triple;typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}Matrix;创建头文件:“Matrix.h”voidCreatMatrix(Matrix*m)//矩阵的初始化{intp=1,a,b,c;printf(请输入矩阵的行数、列数、非零元的个数（数据用空格隔开）:);scanf(%d%d%d,&(*m).mu,&(*m).nu,&(*m).tu);3/8while(p=(*m).tu){printf(请输入第%d个非零元素的行数，列数，元素值（数据用空格隔开）：,p);scanf(%d%d%d,&a,&b,&c);(*m).data[0].i=0;(*m).data[0].j=0;(*m).data[p].i=a;(*m).data[p].j=b;(*m).data[p].e=c;p++;}}voidPrintMatrix(Matrixm)//矩阵的输出{inti,j,p=1;printf(%d行%d列%d个非零元素以矩阵形式输出：\n,m.mu,m.nu,m.tu);for(i=1;i=m.mu;i++){for(j=1;j=m.nu;j++){if((m.data[p].i==i)&&(m.data[p].j==j)){printf(%4d,m.data[p].e);p++;}elseprintf(%4d,0);}printf(\n);}}主程序模块：#includeMatrix.h#includestdio.hvoidFastTransposeMatrix(Matrixa,Matrix*b)//采用三元组顺序表存储表示，求稀疏矩阵a的转置矩阵b{intp,q,col,t;intnum[MAXSIZE+1];intcpot[MAXSIZE+1];(*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;4/8if((*b).tu){for(col=1;col=a.nu;col++)num[col]=0;for(t=1;t=a.tu;t++)//求a中每一列含非零元的个数num[a.data[t].j]++;cpot[1]=1;//求第col列中第一个非零元在b.data中的序号for(col=2;col=a.nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p=a.tu;p++){col=a.data[p].j;q=cpot[col];(*b).data[q].i=a.data[p].j;(*b).data[q].j=a.data[p].i;(*b).data[q].e=a.data[p].e;cpot[col]++;}//forp}//if}//FastTransposeMatrixvoidAddMatrix(Matrixa,Matrixb,Matrix*c)//采用行逻辑链接的顺序表，求矩阵a和b的和{intx,ce,pa=1,pb=1,pc=1;(*c).mu=a.mu;(*c).nu=b.nu;(*c).tu=0;for(x=1;x=a.mu;x++)//对矩阵的每一行进行加法{while(a.data[pa].i==x&&b.data[pb].i==x){if(a.data[pa].j==b.data[pb].j){ce=a.data[pa].e+b.data[pb].e;if(ce)//如果和不为零,则将结果保存到C矩阵中对应的位置{(*c).data[pc].i=x;(*c).data[pc].j=a.data[pa].j;(*c).data[pc].e=ce;pa++;pb++;pc++;}5/8}elseif(a.data[pa].jb.data[pb].j)//若a的列数比b的列数大，则将b矩阵对应的值存入c{(*c).data[pc].i=x;(*c).data[pc].j=b.data[pb].j;(*c).data[pc].e=b.data[pb].e;pb++;pc++;}else//若b的列数比a的列数大，则将a矩阵对应的值存入c{(*c).data[pc].i=x;(*c).data[pc].j=a.data[pa].j;(*c).data[pc].e=a.data[pa].e;pa++;pc++;}}while(a.data[pa].i==x)//将a矩阵第x行中的剩余元素存入c{(*c).data[pc].i=x;(*c).data[pc].j=a.data[pa].j;(*c).data[pc].e=a.data[pa].e;pa++;pc++;}while(b.data[pb].i==x)//将b矩阵第x行中的剩余元素存入c{(*c).data[pc].i=x;(*c).data[pc].j=b.data[pb].j;(*c).data[pc].e=b.data[pb].e;pb++;pc++;}}//for(*c).tu=pc-1;}intmain(){Matrixa,b,c;inti,k;printf(输入1进行矩阵的快速转置运算，输入0进行矩阵行逻辑加法运算：);6/8scanf(%d,&i);if(i==1)//选择运算，当i为1时进行矩阵的转置运算，不为1则进行矩阵的加法运算{printf(创建矩阵A：\n);CreatMatrix(&a);printf(矩阵A以矩阵形式输出为：\n);PrintMatrix(a);printf(转置后的矩阵为：\n);FastTransposeMatrix(a,&b);printf(以三元组表输出为：\n);for(k=1;k=b.tu;k++){printf(%4d%4d%4d\n,b.data[k].i,b.data[k].j,b.data[k].e);}printf(以矩阵的形式输出为：\n);PrintMatrix(b);}else{printf(创建矩阵A：\n);CreatMatrix(&a);printf(矩阵A以矩阵形式输出为：\n);PrintMatrix(a);printf(创建矩阵B：\n);CreatMatrix(&b);printf(矩阵B以矩阵形式输出为：\n);PrintMatrix(b);AddMatrix(a,b,&c);printf(A与B的和矩阵C以三元组形式表示为：\n);for(k=1;k=c.tu;k++){printf(%4d%4d%4d\n,c.data[k].i,c.data[k].j,c.data[k].e);}printf(A与B的和矩阵C以矩阵的形式表示为：\n);PrintMatrix(c);}return0;}(四)程序使用说明及测试结果1．程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：输入1进行矩阵的快速转置运算，输入0进行矩阵行逻辑加法运算：7/8根据需要选择要进行的运算。2测试结果（1）当输入1时进行矩阵的转置运算：测试三元组为：121213931-3361443245218611564-7测试结果如图所示：当输入0时进行矩阵的加法运算：测试的两个矩阵为：A：（三元组形式）1112228/823431-4B：（三元组形式）13-223-531832-6测试结果如图所示：（五）、实验总结(实验心得)本次实验上机编程简单，难度不大，但是用稀疏矩阵的快速转置和行逻辑链接的加法这两个算法逻辑性很强，不太容易弄懂，稀疏矩阵的快速转置算法教材上有可以参考，但是加法算法需要自己分析，有难度，关键在于逻辑上要搞清楚。