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

1、数据结构 C 语言版 稀疏矩阵的三元组顺序表存储表示和实现.txt对的时间遇见对的人是生幸福；对的时间遇见错的人是一场心伤；错的时间遇见对的人是一段荒唐；错的时间遇见 错的人是一声叹息。/*数据结构 C语言版稀疏矩阵的三元组顺序表存储表示和实现P98编译环境：Dev-C+ 4.9.9.2日期：2011年 2 月 8日*/typedef int ElemType;/稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 100 /非零元个数的最大值typedef structint i,j;/ 行下标，列下标ElemType e; /非零元素值Triple;typedef structTr

2、iple dataMAXSIZE+1; /非零元三元组表，data0 未用int mu,nu,tu;/矩阵的行数、列数和非零元个数TSMatrix;/创建稀疏矩阵 Mint CreateSMatrix(TSMatrix *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(请按行序顺序输入第

3、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.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,所

4、有元素置空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(%4d%4d%8dn”,M.datai.i,M.datai.j,M.datai.e);/由稀疏矩阵 M复制得到 Tint CopySMatrix(TSMatrix M,TSMatrix *T

5、)(*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,TSMatrix *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=&

6、amp;M.data1;Np=&N.data1;Me=&M.dataM.tu;Ne=&N.dataN.tu;Qh=Qe=(*Q).data;/ Mp/ Np/ Me的初值指向矩阵 M的非零元素首地址的初值指向矩阵N的非零元素首地址 指向矩阵M的非零元素尾地址 指向矩阵N的非零元素尾地址while(Mp = Me & Np i,Np-i)( case 1:/ Ne/ Qh、Qe 的初值指向矩阵 Q 的非零元素首地址的前一地址Ne)*Qe=*Mp;Mp+;break;case 0:/ M、N 矩阵当前非零元素的行相等， 继续比较列switch(comp(Mp-j,N

7、p-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(Mp=Me) Qe+;*Qe=*Mp;Mp+; (*Q).tu=Qe-Qh; / 矩阵 Q的非零元素个数 return 1;/求稀疏矩阵的差 Q=M-Nint SubtSMatrix

8、(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的行、列值，Qn 为矩阵 Q的非零元素个数，初值为 0ElemType *Qe;if(M.nu!=N.mu)return 0;(*Q).mu=M.mu;(*Q).nu=N.nu;Qe

9、=(ElemType *)malloc(h*l*sizeof(ElemType); / Qe为矩阵 Q 的临时数组/矩阵 Q 的第 i行 j 列的元素值存于*(Qe+(i-1)*l+j-1) 中，初值为 0for(i=0;ih*l;i+)*(Qe+i)=0; / 赋初值 0for(i=1;i=M.tu;i+) /矩阵元素相乘，结果累加到Qefor(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.

10、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;(*T).nu=M.mu;(*T).tu=M.tu;if(*T).tu)(q=1;for(col=1;col=M.nu;+col)/先将列转换成行f

11、or(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;num=(int *)malloc(M.nu+1)*sizeof(int);/ 生成数组cpot=(int *)malloc(M.nu

12、+1)*sizeof(int);/ 生成数组(*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)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)(col=M.da

13、tap.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);PrintSMatrix(B);DestroySMatrix(&B);printf(

14、 销毁矩阵 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);0不用）0不用）PrintSMatrix(C);DestroySMatrix(&C);printf(矩阵 C2(A-B):);SubtSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&

15、amp;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):);Mul

16、tSMatrix(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);system(pause);return 0;

17、/*输出效果：创建矩阵 A:请输入矩阵的行数，列数，非零元素个数：(逗号)3,3,3请按行序顺序输入第1个非零兀素所在的行(13),列(13),儿系值：(逗号)1,1,1请按行序顺序输入第2个非零兀素所在的行(13),列(13),儿系值：(逗号)1,3,2请按行序顺序输入第3个非令兀素所在的仃(13),列(13),儿系值：(逗号)3,3,33 行 3列 3个非零元素。行列元素值1111323 33由矩阵 A复制矩阵 B:3 行 3列 3个非零元素。行列元素值111132333销毁矩阵 B 后：0 行 0列 0个非零元素。行列元素值重创矩阵 B:(注意与矩阵 A 的行、列数相同，这样方便后面的测

18、试行、列分别为 请输入矩阵的行数，列数，非零元素个数：(逗号)3,3,3请按行序顺序输入第1个非零兀素所在的行(13),列(13),儿系值：(逗号)1,2,1请按行序顺序输入第2个非零兀素所在的行(13),列(13),儿系值：(逗号)2,1,2请按行序顺序输入第3个非令兀素所在的仃(13),列(13),儿系值：(逗号)3,1,33 行 3列 3个非零元素。行列元素值121212313矩阵 C1(A+B):3 行 3列 6个非零元素。行列兀素值1 111 213,3)1 322 123 133 33矩阵 C2(A-B):3 行 3 列 6个非零兀素行列兀素值1 111 2-11 322 1-23 1-33 33矩阵 C3(A的转置):3 行 3列 3个非零元素。行列元素值111312