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

/* 数据结构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; / 矩阵的行数、列数和非零元个数TSMatrix; / 创建稀疏矩阵M int 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+) do printf(请按行序顺序输入第%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 ，所有元素置空void DestroySMatrix(TSMatrix *M) (*M).mu=0; (*M).nu=0; (*M).tu=0; / 输出稀疏矩阵M void 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复制得到T int 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; else i=-1; return i; / 求稀疏矩阵的和Q=M+N int 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=&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 & 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(Mp=Me) Qe+; *Qe=*Mp; Mp+; (*Q).tu=Qe-Qh; / 矩阵 Q的非零元素个数return 1; / 求稀疏矩阵的差Q=M-N int 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 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;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; 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; 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的转置矩阵Tint 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) 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); 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(销毁矩阵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(&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(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 个非零元素所在的行(1 3), 列(1 3), 元素值： ( 逗号 ) 1,1,1 请按行序顺序输入第2 个非零元素所在的行(1 3), 列(1 3), 元素值： ( 逗号 ) 1,3,2 请按行序顺序输入第3 个非零元素所在的行(1 3), 列(1 3), 元素值： ( 逗号 ) 3,3,3 3 行 3 列 3 个非零元素。

行列元素值 1 1 1 1 3 2 3 3 3 。