《数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现》由会员分享，可在线阅读，更多相关《数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现（11页珍藏版）》请在金锄头文库上搜索。
1、/* 数据结构 C 语言版 稀疏矩阵的三元组顺序表存储表示和实现 P98 编译环境：Dev-C+ 4.9.9.2 日期：2011 年 2 月 8 日 */typedef int ElemType;/ 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 / 非零元个数的最大值 typedef struct int i,j;/ 行下标,列下标 ElemType e; / 非零元素值 Triple;typedef struct Triple dataMAXSIZE+1; / 非零元三元组表,data0未用 int mu,nu,tu;/ 矩阵的行数、列数和非零元个数 TSMatri
2、x;/ 创建稀疏矩阵 Mint CreateSMatrix(TSMatrix *M) int i,m,n; ElemType e; int k;printf(“请输入矩阵的行数,列数,非零元素个数：（逗号）n“);scanf(“%d,%d,%d“, (*M).data0.i=0;/ 为以下比较顺序做准备 for(i = 1; i (*M).mu | n (*M).nu) k=1; if(m i,Np-i) case 1: *Qe=*Mp; Mp+; break; case 0: / M、N 矩阵当前非零元素的行相等,继续比较列switch(comp(Mp-j,Np-j) case 1: *Qe
3、=*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 SubtSM
4、atrix(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 的非零元素个数，初值为 0 ElemType *Qe; if(M.nu!=N.mu) return 0; (*Q).mu=M.mu
5、; (*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.datai.i-1)*l+N.dataj.j-1) += M.datai.e * N.dataj.e;
6、 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; (*T).nu=M.mu; (*T).tu=M.tu; i
7、f(*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; num=(int *)ma
8、lloc(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)
9、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( PrintSMatrix(A);printf(“由矩阵 A 复制矩阵 B: “);CopySMatrix
10、(A, PrintSMatrix(B);DestroySMatrix( printf(“销毁矩阵 B 后:n“);PrintSMatrix(B);printf(“重创矩阵 B:(注意与矩阵 A 的行、列数相同，这样方便后面的测试“ “行、列分别为%d,%d)n“, A.mu, A.nu);CreateSMatrix( PrintSMatrix(B);printf(“矩阵 C1(A+B): “);AddSMatrix(A,B, PrintSMatrix(C); DestroySMatrix(printf(“矩阵 C2(A-B): “);SubtSMatrix(A,B, PrintSMatrix(
11、C); DestroySMatrix(printf(“矩阵 C3(A 的转置): “);TransposeSMatrix(A, PrintSMatrix(C); DestroySMatrix( DestroySMatrix( DestroySMatrix(printf(“创建矩阵 A2: “);CreateSMatrix( PrintSMatrix(A);printf(“创建矩阵 B3:(行数应与矩阵 A2 的列数相同=%d)n“,A.nu);CreateSMatrix( PrintSMatrix(B);printf(“矩阵 C5(A*B): “);MultSMatrix(A,B, Print
12、SMatrix(C); DestroySMatrix( DestroySMatrix( DestroySMatrix(printf(“创建矩阵 A: “);CreateSMatrix( PrintSMatrix(A);FastTransposeSMatrix(A, printf(“矩阵 B(A 的快速转置): “);PrintSMatrix(B);DestroySMatrix( DestroySMatrix(system(“pause“); return 0; /* 输出效果：创建矩阵 A: 请输入矩阵的行数,列数,非零元素个数：（逗号）3,3,3 请按行序顺序输入第 1 个非零元素所在的行(
13、13),列(13),元素值：(逗号)1,1,1 请按行序顺序输入第 2 个非零元素所在的行(13),列(13),元素值：(逗号)1,3,2 请按行序顺序输入第 3 个非零元素所在的行(13),列(13),元素值：(逗号)3,3,33 行 3 列 3 个非零元素。行 列 元素值1 1 11 3 23 3 3 由矩阵 A 复制矩阵 B:3 行 3 列 3 个非零元素。行 列 元素值1 1 11 3 23 3 3 销毁矩阵 B 后:0 行 0 列 0 个非零元素。行 列 元素值 重创矩阵 B:(注意与矩阵 A 的行、列数相同，这样方便后面的测试行、列分别为 3,3) 请输入矩阵的行数,列数,非零元素
14、个数：（逗号）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 12 1 23 1 3 矩阵 C1(A+B): 3 行 3 列 6 个非零元素。行 列 元素值1 1 11 2 11 3 22 1 23 1 33 3 3 矩阵 C2(A-B): 3 行 3 列 6 个非零元素。行 列 元素值1 1 11 2 -
15、11 3 22 1 -23 1 -33 3 3 矩阵 C3(A 的转置): 3 行 3 列 3 个非零元素。行 列 元素值1 1 13 1 23 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 11 3 23 3 3 创建矩阵 B3:(行数应
