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

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个非零元素所在的行(1d），”"列（1%d）,元素值：(逗号）n”， i,（M).mu，（*M).nu）;scanf（"d，%d，d”，m，&n,&e）；k=0；/ 行或列超出范围 if(m < 1 | m (*M）.mu | n

3、 1 n （*M）。nu） k=1；if（m (M).datai1。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；/ 输出稀疏矩阵Mvoid PrintSMatrix（TSMatrix M)int i；

4、printf（”nd行d列d个非零元素.n"，M.mu，M.nu，M。tu）；printf（”4s4s8sn”, "行”, ”列", ”元素值”）；for(i=1；i<=M。tu；i+)printf（”4d4d%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

5、 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=M。data1;/ Mp的初值指向矩阵M的非零元素首地址 Np=N.data1；/ Np的初值指向矩阵N的非零元素首地址 Me=M。dataM。tu；/ Me指向矩阵M的非零元素尾地址 Ne=N。data

6、N。tu；/ Ne指向矩阵N的非零元素尾地址 Qh=Qe=（Q）。data；/ Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址 while（Mp = Me & Np = Ne）Qe+;switch（comp（Mp-i，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;Qe>e+=Npe；if(！Qe>e） / 元素值为0，不存入压缩矩阵 Qe-；Mp+；Np+;

7、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的元素全部处理完毕 while（Mp=Me）Qe+;*Qe=Mp;Mp+；(Q)。tu=QeQh； / 矩阵Q的非零元素个数 return 1;/ 求稀疏矩阵的差Q=MNint SubtSMatrix（TSMatrix M，TSMatrix N，TSMatrix *Q） int i；for（i=1;i<=N.tu;i+）N.datai.e=1；AddSMatrix(

8、M，N，Q）;return 1；/ 求稀疏矩阵的乘积Q=MNint 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(hlsizeof（ElemType）; / Qe为矩阵Q的临时数组 / 矩阵Q的第i行j列的元素值存于(Qe+（i1）l+j1)中，初值为0 for（

9、i=0；ihl；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。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；

10、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

11、 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)numcol=0； / 设初值 for(t=1；

12、t=M。tu;+t) / 求M中每一列含非零元素个数 +numM.datat.j；cpot1=1；/ 求第col列中第一个非零元在（T)。data中的序号for（col=2；col<=M。nu；+col） cpotcol=cpotcol1+numcol1；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

13、,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+

14、B）： ”)；AddSMatrix（A，B，C）;PrintSMatrix（C）；DestroySMatrix(C）；printf（”矩阵C2(AB）: ”）;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

15、（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

16、）；printf(”矩阵B（A的快速转置）： "）;PrintSMatrix（B）；DestroySMatrix（A);DestroySMatrix（&B）；system（”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个非零元素。

17、 行 列 元素值 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个非零元素. 行 列 元素值重创矩阵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列

18、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(AB）：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个非零元素。 行 列 元素值 1 1 1 3 1 2 3 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 1 1 3 2 3 3 3创建矩阵B3:（行数应与矩阵A2的列数相同=3）请输入矩阵的行数，列数，非零元素个数:（逗号）3，3，2请按行序顺序输入第1个非零元素所在的行(13），列（13）,元素值：(逗号)1，3,1请按行序顺序输入第2个非零元素所在的行（1