《数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现》由会员分享，可在线阅读，更多相关《数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现（10页珍藏版）》请在金锄头文库上搜索。
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 1 | m （*M)。mu | n 1 n (M）。nu） k=1；if(m (*M)。datai-1。i m = (M）。datai1。
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%8sn, 行,
4、 列, ”元素值”)；for（i=1；i=M.tu;i+)printf(%4d%4d8dn”,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，TSMatrix
5、*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
6、,Np-i）)case 1： *Qe=*Mp；Mp+；break；case 0： / M、N矩阵当前非零元素的行相等,继续比较列switch（comp（Mpj，Np-j)） case 1: Qe=Mp；Mp+；break；case 0： Qe=*Mp；Qee+=Np-e;if（!Qee） / 元素值为0，不存入压缩矩阵 Qe-;Mp+；Np+;break；case -1: *Qe=*Np；Np+；break;case 1： Qe=*Np;Np+；if（MpMe） / 矩阵M的元素全部处理完毕 while(Np=Ne)Qe+;Qe=*Np；Np+;if(NpNe) / 矩阵N的元素全部处理完毕
7、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*Nint MultSMatrix（TSMatrix M，TSMatrix N,TSMatrix *Q) int i,j，h=M.mu,l=N。nu，Qn=0；/ h,l分别为矩阵Q的行、
8、列值,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+(i1)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。data
9、i.i1)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+j1）!=0)Qn+;（Q).dataQn。e=*(Qe+(i1）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；
10、(*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；num=（int )malloc（(M
11、.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=cpotcol1+numc
12、ol1；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:
