数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现

typedef intElemType；//稀疏矩阵的三元组顺序表存储表示ttdefine MAXSIZE100//非零元个数的最大值typedef struct{int i,j；//行下标，列下标ElemType e；//非零元素值}Triple；typedef structTriple data[MAXSIZE+1];//非零元三元组表，data

[0]未用int mu,nu,tu；//矩阵的行数、列数和非零元个数}TSMatrix；//创建稀疏矩阵Mint CreateSMatrixTSMatrix*Mint i,m,n;ElemType e；int k；printf〃请输入矩阵的行数，列数，非零元素个数逗号\n;scanf%d,%d,%d“，*M.mu,*Mnu,*M.tu；«data

[0].i=0；//o为以下比较顺序做准备for i=1；i=i++{do{printf请按行序顺序输入第％d个非零元素所在的行素〜％d行”列l~%d，元素值逗号、n”，i,*Mo mu,*Mnu；scanf%d,%d,%dv,m,n,e；k=0;//行或列超出范围if m1||m〉*M0mu|n{1||n*M.nuk=l；if m〈*M odata[iT]i II m==*Mdata[i—1].in=*Mdata[i—l]o j//行或列的顺序有错k=l;}while k；*Mdata Li],i二m；〃行下标*Mdata[i].j=n;〃列下标*Mdata[i]e=e；〃该下标所对应的值}return1;o//销毁稀疏矩阵M,所有元素置空3行3列2个非零元素行列元素值132212请按任意键继续.*/void DestroySMatrixTSMatrix*M*Mmu=0;*M,nu=0；*M.tu=0；}//输出稀疏矩阵Mvoid PrintSMatrixTSMatrix Mint i；printf\n%d行％1列%1个非零元素.\n〃,M mu,Mnu,M tu；printf%4s%4s%8s\n〃，〃o o行「〃列〃，”元素值〃；for i=l;i=M.tu;i++printf，，%4d%4d%8d\nv,Mo data[i]i,M.data[i]j,M.data[i].e；}o o//由稀疏矩阵M复制得到Tint CopySMatrixTSMatrix M,TSMatrix*T{*T=M；return1;//AddSMatrix函数要用到int compint cl,intc2{int i;if clc2i=l；else ifcl==c2i二0；elsei=-1；return i；//求稀疏矩阵的和Q=M+Nint AddSMatrixTSMatrix M,TSMatrix N,TSMatrix*Q Triple*Mp,*Np,*Ne,*Qh,*Qe；if Mo mu!=No mu return0；i fM.nu!=No nureturn0；*Qmu=Mo mu;*Qnu=M.nu;Mp=M.data

[1]；//Mp的初值指向矩阵M的非零元素首地址Np=N.data[l];//Np的初值指向矩阵N的非零元素首地址Me=Mo data[Mo tu]；//Me指向矩阵M的非零元素尾地址Ne=N.data[N.tu]；//Ne指向矩阵N的非零元素尾地址Qh=Qe=*Qdata；//Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址while Mp〈二MeNp〈二Ne{Qe++;switchcompMp-i,Np-icase1*Qe=*Mp;Mp++；break；case0//M、N矩阵当前非零元素的行相等，继续比较列switchcompMp-j,Np一〉jcase1:*Qe二*Mp；Mp++；break;case0:*Qe=*Mp；Qe—〉e+=Np-〉e；if!Qe-e//元素值为0,不存入压缩矩阵Qe;Mp++;Np++；break；case-1:*Qe=*Np；Np++；break；case-1*Qe=*Np;Np++；}}if MpMe//矩阵M的元素全部处理完毕while Np=NeQe++；*Qe=*Np；Np++；ifNp Ne//矩阵N的元素全部处理完毕while Mp=Me Qe++；*Qe=*Mp；Mp++;}*Qtu=Qe-Qh;〃矩阵Q的非零元素个数return1;}//求稀疏矩阵的差Q=M-N intSubtSMatrix TSMatrixM,TSMatrix N,TSMatrix*Qint i；fori=l；i=No tu;i++N.data[i].e*=一1;AddSMatrix M,N,Q;return1;//求稀疏矩阵的乘积Q二M*Nint MultSMatrixTSMatrixM,TSMatrix N,TSMatrix*Q{int i,j,h=Mo mu,1二N nu,Qn=0；//h,1分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数,初值为0ElemType*Qe;if Mo nu!=N.mureturn0；*Q.mu=Mo mu；*Q.nu=No nu;Qe=ElemType*malloc h*l*sizeof ElemType;//Qe为矩阵Q的临时数组//矩阵Q的第i行j列的元素值存于*Qe+i—1中，初值为0for i=0；i〈h*l；i++*Qe+i=0；//赋初值0fori=l；i=Mo tu；i++//矩阵元素相乘,结果累加到Qe for j=l;j=No tu;j++if M.data[i]j=N.data[j].i*Qe+M.data[i]o i-l*1+N.data[j].jT+=Mo data[i].e*Ndata[j]e；for i=l;i=Mo mu；i++forj=l；j=No nu;j++if*oQe+i-l*l+j-D!=0Qn++;*Q.data[Qn]e=*Qe+i-l*l+j—1;o*Qdata[Qn].i=i;*Q.data[Qn]o j=j；}free Qe;*Qtu=Qn;return1；}//算法

5.1P99//求稀疏矩阵M的转置矩阵Toint TransposeSMatrixTSMatrixM,TSMatrix*T intp,q,col;*Tmu=M.nu;^T.nu=Momu;*T.tu=Mo tu;if*Ttu{q=i;for col=l;col=M.nu;++col〃先将列转换成行for p=l;p=Mo tu；++p〃再将行转换成列if Mo data Lp].j=col*T.data[q].i=M data[p]j;o o*Tdata[q]j=M.data[p]i;o o*Tdata[q]e=M data[p]e；o oo++q；return1；}//算法52P100〃快速求稀疏矩阵M的转置矩阵Toint FastTransposeSMatrixTSMatrixM,TSMatrix*T intp,q,t,col,*num,*cpot；num=int*mallocMo nu+1*sizeof int;//生成数组

[0]不用cpot=int*mallocMo nu+1*sizeof int；//生成数组

[0]不用*Tmu=Monu;*T nu=M mu；o*Ttu=Mo tu；if*Ttufor col=l；col=M.nu；++col num[col]=0；//设初值for t=l；t=Mo tu；++t//求M中每一列含非零元素个数++num[Mo data[t]o j]；cpot

[1]=1；//求第col列中第一个非零元在*Tdata中的序号for col=2;col〈二M.nu；++colcpot[col]=cpot[col-1]+num[col-l]；for p=l；p=Mo tu;++p{col=Modata[p].j；q=cpot[col]；*Tdata[q].i=M data[p].j；*Tdata Eq]o j=Mdata[p]i;o*T.data[q].e=M.data[p].e；++cpot[col]；}free num；free cpot;return1；int mainTSMatrix A,B,C;printf〃创建矩阵A;CreateSMatrix A;PrintSMatrix A;printf C由矩阵A复制矩阵B〃；CopySMatrix A,B;PrintSMatrixB;DestroySMatrix B；printf销毁矩阵B后:\n；PrintSMatrix B；printf重创矩阵B注意与矩阵A的行、列数相同，这样方便后面的测试””行、列分别为%七%d\n，Ao mu,Ao nu;CreateSMatrix B；PrintSMatrix B;printf矩阵Cl A+B〃；AddSMatrixA,B,C；PrintSMatrix C；DestroySMatrix C；printf矩阵C2A-B”;SubtSMatrixA,B,C;PrintSMatrixC；DestroySMatrix C;printf〃矩阵C3A的转置:〃;TransposeSMatrix A,C；PrintSMatrix C；DestroySMatrix A；DestroySMatrix B;DestroySMatrix C;printf创建矩阵A2:〃；CreateSMatrix A；PrintSMatrix A；printf创建矩阵B3:行数应与矩阵A2的列数相同=%d\n”,A.nu;CreateSMatrix B;PrintSMatrixB；printf矩阵C5A*B；MultSMatrixA,B,C;PrintSMatrix C;DestroySMatrixA;DestroySMatrix B；DestroySMatrix C；printf创建矩阵A:〃；CreateSMatrix A；PrintSMatrixA；FastTransposeSMatrix A,B；printf矩阵BA的快速转置:；PrintSMatrix B;DestroySMatrix A；DestroySMatrixB;systempause”；return0；}/*输出效果创建矩阵A请输入矩阵的行数,列数，非零元素个数逗号3,3,3请按行序顺序输入第1个非零元素所在的行03,列13,元素值逗号〜1,1,1请按行序顺序输入第2个非零元素所在的行13,列T3，元素值逗号〜1,3,2请按行序顺序输入第3个非零元素所在的行13,列13,元素值逗号〜〜3,3,33行3列3个非零元素.行列元素值111333由矩阵A复制矩阵B3行3列3个非零元素行列元素值111132333销毁矩阵B后0行0列0个非零元素行列元素值重创矩阵B（注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为3,3）请输入矩阵的行数，列数，非零元素个数（逗号）3,3,3请按行序顺序输入第1个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜1,2,1请按行序顺序输入第2个非零元素所在的行

（13），歹U

（13）,元素值（逗号）〜〜2,1,2请按行序顺序输入第3个非零元素所在的行（1-3）,列

（13）,元素值（逗号）〜3,1,33行3列3个非零元素.行列元素值121212313矩阵Cl（A+B）3行3列6个非零元素.行列元素值111121132212313333矩阵C2（A—B）:3行3列6个非零元素行列元素值11112-113221-231—3333矩阵C3（A的转置）3行3列3个非零元素行列元素值111312333创建矩阵A2请输入矩阵的行数，列数，非零元素个数（逗号）3,3,3请按行序顺序输入第1个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜1,1,1请按行序顺序输入第2个非零元素所在的行

（13）,列（「3）,元素值（逗号）〜1,3,2请按行序顺序输入第3个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜3,3,33行3列3个非零元素行列元素值111232333创建矩阵B3:（行数应与矩阵A2的列数相同=3）请输入矩阵的行数,列数，非零元素个数（逗号）3,3,2请按行序顺序输入第1个非零元素所在的行

（13）,歹U（l~3）,元素值（逗号）〜1,3,1请按行序顺序输入第2个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜2,2,23行3列2个非零元素行列元素值131222矩阵C5（A*B）3行3列1个非零元素.行列元素值331创建矩阵A请输入矩阵的行数，列数,非零元素个数（逗号）3,3,2请按行序顺序输入第1个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜1,2,2请按行序顺序输入第2个非零元素所在的行

（13）,列

（13）,元素值（逗号）〜〜3,1,23行3列2个非零元素行列元素值122312矩阵B（A的快速转置）:。