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

1、typedef int ElemType;/ 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 / 非零元个数的最大值 typedef structint i,j;/ 行下标,列下标 ElemType e; / 非零元素值 Triple;typedef structTriple dataMAXSIZE+1; / 非零元三元组表,data0未用 int mu,nu,tu;/ 矩阵的行数、列数和非零元个数 TSMatrix;/ 创建稀疏矩阵Mint CreateSMatrix(TSMatrix *M)int i,m,n;ElemType e;int k;printf(请输入矩

2、阵的行数,列数,非零元素个数：（逗号）n);scanf(%d,%d,%d,&(*M).mu,&(*M).nu,&(*M).tu);(*M).data0.i=0;/ 为以下比较顺序做准备 for(i = 1; i = (*M).tu; i+)doprintf(请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值：(逗号)n, i,(*M).mu,(*M).nu);scanf(%d,%d,%d,&m,&n,&e);k=0;/ 行或列超出范围 if(m (*M).mu | n (*M).nu) k=1;if(m (*M).datai-1.i | m = (*M).datai-1.

3、i& n = (*M).datai-1.j) / 行或列的顺序有错 k=1;while(k);(*M).datai.i = m;/行下标(*M).datai.j = n;/列下标(*M).datai.e = e;/该下标所对应的值return 1;/ 销毁稀疏矩阵M，所有元素置空void DestroySMatrix(TSMatrix *M) (*M).mu=0;(*M).nu=0;(*M).tu=0;/ 输出稀疏矩阵Mvoid PrintSMatrix(TSMatrix M)int i;printf(n%d行%d列%d个非零元素。n,M.mu,M.nu,M.tu);printf(%4s%4s

4、%8sn, 行, 列, 元素值);for(i=1;i=M.tu;i+)printf(%4d%4d%8dn,M.datai.i,M.datai.j,M.datai.e);/ 由稀疏矩阵M复制得到Tint CopySMatrix(TSMatrix M,TSMatrix *T) (*T)=M;return 1;/ AddSMatrix函数要用到int comp(int c1,int c2) int i;if(c1c2)i=1;else if(c1=c2)i=0;elsei=-1;return i;/ 求稀疏矩阵的和Q=M+Nint AddSMatrix(TSMatrix M,TSMatrix N,T

5、SMatrix *Q) Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;if(M.mu!=N.mu)return 0;if(M.nu!=N.nu)return 0;(*Q).mu=M.mu;(*Q).nu=M.nu;Mp=&M.data1;/ Mp的初值指向矩阵M的非零元素首地址 Np=&N.data1;/ Np的初值指向矩阵N的非零元素首地址 Me=&M.dataM.tu;/ Me指向矩阵M的非零元素尾地址 Ne=&N.dataN.tu;/ Ne指向矩阵N的非零元素尾地址 Qh=Qe=(*Q).data;/ Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址 while(Mp

6、 = Me & Np i,Np-i)case 1: *Qe=*Mp;Mp+;break;case 0: / M、N矩阵当前非零元素的行相等,继续比较列switch(comp(Mp-j,Np-j) case 1: *Qe=*Mp;Mp+;break;case 0: *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(NpNe) / 矩阵N的元素全部处理完毕 while(

7、Mp=Me)Qe+;*Qe=*Mp;Mp+;(*Q).tu=Qe-Qh; / 矩阵Q的非零元素个数 return 1;/ 求稀疏矩阵的差Q=M-Nint SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) int i;for(i=1;i=N.tu;i+)N.datai.e*=-1;AddSMatrix(M,N,Q);return 1;/ 求稀疏矩阵的乘积Q=M*Nint MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) int i,j,h=M.mu,l=N.nu,Qn=0;/ h,l分别为矩阵Q的行、列值,Q

8、n为矩阵Q的非零元素个数，初值为0 ElemType *Qe;if(M.nu!=N.mu)return 0;(*Q).mu=M.mu;(*Q).nu=N.nu;Qe=(ElemType *)malloc(h*l*sizeof(ElemType); / Qe为矩阵Q的临时数组 / 矩阵Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为0 for(i=0;ih*l;i+)*(Qe+i)=0; / 赋初值0 for(i=1;i=M.tu;i+) / 矩阵元素相乘，结果累加到Qe for(j=1;j=N.tu;j+)if(M.datai.j=N.dataj.i)*(Qe+(M.da

9、tai.i-1)*l+N.dataj.j-1) +=M.datai.e * N.dataj.e;for(i=1;i=M.mu;i+)for(j=1;j=N.nu;j+)if(*(Qe+(i-1)*l+j-1)!=0)Qn+;(*Q).dataQn.e=*(Qe+(i-1)*l+j-1);(*Q).dataQn.i=i;(*Q).dataQn.j=j;free(Qe);(*Q).tu=Qn;return 1;/ 算法5.1 P99/ 求稀疏矩阵M的转置矩阵T。int TransposeSMatrix(TSMatrix M,TSMatrix *T)int p,q,col;(*T).mu=M.nu;

10、(*T).nu=M.mu;(*T).tu=M.tu;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;(*T).dataq.j=M.datap.i;(*T).dataq.e=M.datap.e;+q;return 1;/ 算法5.2 P100/ 快速求稀疏矩阵M的转置矩阵T。int FastTransposeSMatrix(TSMatrix M,TSMatrix *T) int p,q,t,col,*num,*cpot;n

11、um=(int *)malloc(M.nu+1)*sizeof(int);/ 生成数组（0不用） cpot=(int *)malloc(M.nu+1)*sizeof(int);/ 生成数组（0不用） (*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if(*T).tu)for(col=1;col=M.nu;+col)numcol=0; / 设初值 for(t=1;t=M.tu;+t) / 求M中每一列含非零元素个数 +numM.datat.j;cpot1=1;/ 求第col列中第一个非零元在(*T).data中的序号for(col=2;col=M.nu;+col)

12、cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;(*T).dataq.i=M.datap.j;(*T).dataq.j=M.datap.i;(*T).dataq.e=M.datap.e;+cpotcol;free(num);free(cpot);return 1;int main()TSMatrix A,B,C;printf(创建矩阵A: );CreateSMatrix(&A);PrintSMatrix(A);printf(由矩阵A复制矩阵B: );CopySMatrix(A,&B);PrintSMatr

13、ix(B);DestroySMatrix(&B);printf(销毁矩阵B后:n);PrintSMatrix(B);printf(重创矩阵B:(注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为%d,%d)n, A.mu, A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf(矩阵C1(A+B): );AddSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf(矩阵C2(A-B): );SubtSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix

14、(&C);printf(矩阵C3(A的转置): );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);PrintSMatrix(B);printf(矩阵C5(A*B): );MultSMatrix(A,B,&C);PrintSMatrix(

15、C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);printf(创建矩阵A: );CreateSMatrix(&A);PrintSMatrix(A);FastTransposeSMatrix(A,&B);printf(矩阵B(A的快速转置): );PrintSMatrix(B);DestroySMatrix(&A);DestroySMatrix(&B);system(pause);return 0;/*输出效果：创建矩阵A: 请输入矩阵的行数,列数,非零元素个数：（逗号）3,3,3请按行序顺序输入第1个非零元素所在的行(13

16、),列(13),元素值：(逗号)1,1,1请按行序顺序输入第2个非零元素所在的行(13),列(13),元素值：(逗号)1,3,2请按行序顺序输入第3个非零元素所在的行(13),列(13),元素值：(逗号)3,3,33行3列3个非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3由矩阵A复制矩阵B:3行3列3个非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3销毁矩阵B后:0行0列0个非零元素。 行 列 元素值重创矩阵B:(注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为3,3)请输入矩阵的行数,列数,非零元素个数：（逗号）3,3,3请按行序顺序输入第1个非零元素

17、所在的行(13),列(13),元素值：(逗号)1,2,1请按行序顺序输入第2个非零元素所在的行(13),列(13),元素值：(逗号)2,1,2请按行序顺序输入第3个非零元素所在的行(13),列(13),元素值：(逗号)3,1,33行3列3个非零元素。 行 列 元素值 1 2 1 2 1 2 3 1 3矩阵C1(A+B):3行3列6个非零元素。 行 列 元素值 1 1 1 1 2 1 1 3 2 2 1 2 3 1 3 3 3 3矩阵C2(A-B):3行3列6个非零元素。 行 列 元素值 1 1 1 1 2 -1 1 3 2 2 1 -2 3 1 -3 3 3 3矩阵C3(A的转置):3行3列3

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