西工大 数据结构实验 noj 6 实验2.4:稀疏矩阵的乘法

主要依托教学用的ppt上的计算方法写的题解。用rpots索引元素相乘，大意如下图

1）个人写代码时首先是发现矩阵输入正确，但相乘过程中却有元素并未参与计算，反复查验代码后发现是由于采用了rpos的索引方式，循环体由A->rpos[arow] 到 A->rpos[arow+1]，而arow等于A-mu（行边界）时就会导致arow+1出错，因此将循环体结尾改成A->rpos[arow+1]-1，循环内容在外部再进行一次，内部某步循环结尾改成A->tu。

（2）同样的错误在B->rpos[brow] 到 B->rpos[brow+1]时也同样发生，不过我没能第一时间反应过来，同样找了很久才发现这个问题，然后用了if else的处理方法，其实和上面的解决方式差不多。

上代码 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Triple
{
        int  i, j;		/* 行号和列号 */
        int  data;	/* 元素值 */
}Triple;

typedef struct TSMatrix
{
        Triple  num[200];
        int  mu, nu, tu;	/* 行数、列数和非零元个数*/
        int rnum[100],rpos[100];
}TSMatrix,*PTriple;

void print(PTriple P);
PTriple creat()
{ 
    int row;
    PTriple P=(PTriple)malloc(sizeof(TSMatrix));
    scanf("%d %d",&P->mu,&P->nu);
    P->tu=0;
    int i=0;
    while(1)
    {
        scanf("%d %d %d",&(P->num[i].i),&(P->num[i].j),&(P->num[i].data));
        if((P->num[i].i)==0&&(P->num[i].j)==0&&(P->num[i].data)==0) break;
        P->tu++;
        i++;
    }
    for (row=1; row<= P->mu; ++row)
    P->rnum[row] = 0;
    for (int t = 0; t < P->tu; ++t) /*统计每行的非零元个数*/
        ++P->rnum[P->num[t].i];
    P->rpos[1] = 0; 	
    for (row = 2; row <= P->mu; ++row)
        P->rpos[row] = P->rpos[row-1] + P->rnum[row-1];
    return P;
}
PTriple MultiSMatrix (PTriple A, PTriple B, PTriple C)
{
    C=(PTriple)malloc(sizeof(TSMatrix));
    int  arow, brow, ccol, p, q;
    int ctemp[B->nu+1];
    if (A->nu != B->mu) 
        return NULL;
    C->mu = A->mu;
    C->nu = B->nu;
    C->tu = 0;
    if (A->tu!=0&&B->tu!= 0) {
        for (arow=1; arow<= A->mu-1; ++arow) {
            for(int i=1;i<=B->nu;i++)
            ctemp[i]=0;
            C->rpos[arow]=C->tu;
            for (p=A->rpos[arow]; p< A->rpos[arow+1]; ++p) {
                brow=A->num[p].j;
                if(brow<B->mu)
                for (q = B->rpos[brow]; q<B->rpos[brow+1]; ++q)  {
                    ccol=B->num[q].j;
                    ctemp[ccol]+=A->num[p].data*B->num[q].data;
                } //for q
                else
                for (q = B->rpos[brow]; q<B->tu; ++q)  {
                    ccol=B->num[q].j;
                    ctemp[ccol]+=A->num[p].data*B->num[q].data;
                } //for q
            } // for p	
            for (ccol=1; ccol<=C->nu; ++ccol) {
                if (ctemp[ccol]) {
                    C->num[C->tu].i = arow;
                    C->num[C->tu].j = ccol;
                    C->num[C->tu].data = ctemp[ccol];
                    C->tu++;
                    }  //else
                } //if
            } //for ccol
            for(int i=1;i<=B->nu;i++)
            ctemp[i]=0;
            C->rpos[arow]=C->tu;
            for (p=A->rpos[arow]; p< A->tu; ++p) {
                brow=A->num[p].j;
                if(brow<B->mu)
                for (q = B->rpos[brow]; q<B->rpos[brow+1]; ++q)  {
                    ccol=B->num[q].j;
                    ctemp[ccol]+=A->num[p].data*B->num[q].data;
                } //for q
                else
                for (q = B->rpos[brow]; q<B->tu; ++q)  {
                    ccol=B->num[q].j;
                    ctemp[ccol]+=A->num[p].data*B->num[q].data;
                } //for q
            } // for p	
            for (ccol=1; ccol<=C->nu; ++ccol) {
                if (ctemp[ccol]) {
                    C->num[C->tu].i = arow;
                    C->num[C->tu].j = ccol;
                    C->num[C->tu].data = ctemp[ccol];
                    C->tu++;
                    }  //else
                } //if
    } //for arrow
    return C;
}  //if

void print(PTriple P)
{
    for(int m=0;m<P->tu;m++)                                         //输出P矩阵
        printf("%d %d %d\n",P->num[m].i,P->num[m].j,P->num[m].data);
}

void run ()
{
    PTriple Z1=creat();
    PTriple Z2=creat();
    PTriple Z3=MultiSMatrix(Z1,Z2,Z3);
    if(Z3==NULL)
    printf("ERROR");
    else
    print(Z3);
}
int main()
{
    run();
    return 0;
}