稀疏矩阵相乘.cpp

C语言实现的稀疏矩阵相乘。采用了子函数结构

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define MAXRC 10
#define FALSE 0
#define TRUE 1
typedef struct {
                int i,j;
                int e;
}Triple;

typedef struct {
                Triple data[MAXSIZE+1];
                int mu,nu,tu;
                int rpos[MAXRC];
                int num[MAXRC];
}TSMatrix; 

void createTriple(TSMatrix*);
int MultSMatrix( TSMatrix M, TSMatrix N, TSMatrix *Q);
void print(TSMatrix);

main()
{TSMatrix matrix1,matrix2,matrix;
 int statue;
     printf("第一个矩阵：\n"); 
     createTriple(&matrix1);
     
     printf("第二个矩阵：\n"); 
     createTriple(&matrix2);
   
     printf("\n");
     statue=MultSMatrix(matrix1,matrix2,&matrix);
     if(statue==TRUE)
     print(matrix);
 system("pause");
 return 0; 

}

void createTriple(TSMatrix*p)
{int a,b,e;
 int i,j,k=1,r=0;
     
       p->tu=0;
       printf("请输入矩阵的行数：");
       scanf("%d",&a);
       p->mu=a;
       printf("请输入矩阵的列数：");
       scanf("%d",&b);
       p->nu=b;
       printf("请输入矩阵元素,每行结束请按回车：\n");
       for(i=1;i<=a;i++)                                   //创建三元组 
              for(j=1;j<=b;j++)
                  {  scanf("%d",&e);
                    if(e!=0)
                    {
                      p->data[k].i=i;
                      p->data[k].j=j;
                      p->data[k].e=e;
                      k++;
                    }
                   } 
       p->tu=k; 
    
}

int MultSMatrix( TSMatrix M, TSMatrix N,TSMatrix *Q)
{  /*稀疏矩阵相乘*/
   int i,arow,brow,ccol,t,temp,p,q;
   int ctemp[MAXRC+1]={0};

   if (M.nu!=N.mu)
       printf("Multiply error!");

   Q->mu=M.mu;
   Q->nu=N.nu;
   Q->tu=0;        /*Q初始化*/

 /*---------------查询M中rpos的位置------------------*/
   for (i=1;i<=M.mu;i++)
        M.num[i]=0;
   for (t=1;t<=M.tu;t++)
        ++M.num[M.data[t].i];
   M.rpos[1]=1;

   for (i=2;i<=M.mu;i++)
        M.rpos[i]=M.rpos[i-1]+M.num[i-1];

 /*---------------查询N中rpos的位置------------------*/
   for (i=1;i<=N.mu;i++)
        N.num[i]=0;
   for (t=1;t<=N.tu;t++)
        ++N.num[N.data[t].i];
   N.rpos[1]=1;

   for (i=2;i<=N.mu;i++)
        N.rpos[i]=N.rpos[i-1]+N.num[i-1];

 /*---------------矩阵的相乘------------------*/
   if (M.tu*N.tu!=0)     /*Q为非零矩阵*/
   {
       for (arow=1;arow<=M.mu;arow++)
       {
           for (i=0;i<=N.nu;i++)   /*处理M中的每一行*/
                ctemp[i]=0;       /*累加器ctemp每次都要清零*/

           Q->rpos[arow]=Q->tu+1;

           if (arow<M.mu)
               temp=M.rpos[arow+1];
           else
               temp=M.tu+1;

           for (p=M.rpos[arow];p<temp;p++)    /*对当前行中每一个非零元*/
           {
               brow=M.data[p].j;           /*找到对应元在N中的行号*/

               if (brow<N.mu)
                   t=N.rpos[brow+1];
               else
                   t=N.tu+1;

               for (q=N.rpos[brow];q<t;q++)
               {
                   ccol=N.data[q].j;        /*乘积元素在Q中列号*/
                   ctemp[ccol]+=M.data[p].e*N.data[q].e;
               }
           }        /*求得Q中第crow( =arow)行的非零元*/
           for (ccol=1;ccol<=Q->nu;ccol++)       /*压缩存储该行非零元*/

              if (ctemp[ccol])
              {
                  if ( (++Q->tu) > MAXSIZE )
                       printf("error!");

                  Q->data[Q->tu].i=arow;
                  Q->data[Q->tu].j=ccol;
                  Q->data[Q->tu].e=ctemp[ccol];
              }
        }
    }
    else
        printf("There's no unzeroed element!");
}

//打印矩阵 
void print(TSMatrix matrix)
{
int i,j,k=1;
printf("矩阵之积为：\n");
for(i=1;i<=matrix.mu;i++)
    {for(j=1;j<=matrix.nu;j++)
        {if(matrix.data[k].i==i&&matrix.data[k].j==j)
            {printf("%d  ",matrix.data[k].e);
             k++;}
        else printf("0  ");
        }
     printf("\n");
   }   
printf("\n");
}