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

1、/*数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现 P98日期：2011年2月8日 */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(TS

2、Matrix *M)int i,m,n;ElemType e;int k;printf("请输入矩阵的行数,列数,非零元素个数：（逗号）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).

3、nu);scanf("%d,%d,%d",&m,&n,&e);k=0;/ 行或列超出范围 if(m < 1 | m > (*M).mu | n < 1 | n > (*M).nu) k=1;if(m < (*M).datai-1.i | m = (*M).datai-1.i&& n <= (*M).datai-1.j) / 行或列的顺序有错 k=1;while(k);(*M).datai.i = m;/行下标(*M).datai.j = n;/列下标(*M).datai.e = e;/该下标所对应的

4、值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%8sn", "行", "列", "元素值");for(i=1;i<=M.tu;i+)printf("%4

5、d%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(c1<c2)i=1;else if(c1=c2)i=0;elsei=-1;return i;/ 求稀疏矩阵的和Q=M+Nint AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) Triple *Mp,*Me,*Np,*Ne

6、,*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 <= Me &&am

7、p; Np <= Ne)Qe+;switch(comp(Mp->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(Mp&

8、gt;Me) / 矩阵M的元素全部处理完毕 while(Np<=Ne)Qe+;*Qe=*Np;Np+;if(Np>Ne) / 矩阵N的元素全部处理完毕 while(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*N

9、int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) int i,j,h=M.mu,l=N.nu,Qn=0;/ h,l分别为矩阵Q的行、列值,Qn为矩阵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;i<h*l;i+)*(Qe+

10、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.datai.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)

11、;(*Q).tu=Qn;return 1;/ 算法5.1 P99/ 求稀疏矩阵M的转置矩阵T。int TransposeSMatrix(TSMatrix M,TSMatrix *T)int p,q,col;(*T).mu=M.nu;(*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.

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

13、)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) 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);fre

14、e(cpot);return 1;int main()TSMatrix A,B,C;printf("创建矩阵A: ");CreateSMatrix(&A);PrintSMatrix(A);printf("由矩阵A复制矩阵B: ");CopySMatrix(A,&B);PrintSMatrix(B);DestroySMatrix(&B);printf("销毁矩阵B后:n");PrintSMatrix(B);printf("重创矩阵B:(注意与矩阵A的行、列数相同，这样方便后面的测试""

15、;行、列分别为%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(&C);printf("矩阵C3(A的转置): ");Transp

16、oseSMatrix(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): ");MultS

17、Matrix(A,B,&C);PrintSMatrix(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);sys

18、tem("pause");return 0;/*输出效果：创建矩阵A: 请输入矩阵的行数,列数,非零元素个数：（逗号）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由矩阵A复制矩阵B:3行3列3个非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3销毁矩阵B后:0行0列0个

19、非零元素。 行 列 元素值重创矩阵B:(注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为3,3)请输入矩阵的行数,列数,非零元素个数：（逗号）3,3,3请按行序顺序输入第1个非零元素所在的行(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个非零