123.txt

稀疏矩阵

稀疏矩阵运算问题

作者 ： 安庆大学 汤军 2006.06.10
#include   <stdio.h>
#include   <stdlib.h>
#include   "iostream.h"
#define   ERROR -1
#define   OK   1
#define   MAXRC   20
#define   MAXSIZE   1250
typedef   int     ElemType ;
typedef   int     Status   ;

typedef struct {
    int     i,j;
    ElemType   e;
} Triple;

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

Status MultSMatrix( RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{ 
int k,arow,tp,p,brow,t,q,ccol,ctemp[MAXRC+1];
if(M.nu!=N.mu) return ERROR;
Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;
if (M.tu*N.tu!=0)
  { for (arow=1; arow<=M.mu; ++arow) {
    for (k=1;k<=Q.nu;k++) ctemp[k]=0;     
    Q.rpos[arow]=Q.tu+1;
    if (arow<M.mu) tp=M.rpos[arow+1];
      else tp=M.tu+1;
    for(p=M.rpos[arow];p<tp;++p)
      { brow=M.data[p].j;
        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;
            ctemp[ccol]+= M.data[p].e * N.data[q].e;
            }
      }
  for(ccol=1;ccol<=Q.nu;++ccol)
      if(ctemp[ccol]) {
        if (++Q.tu >MAXSIZE) return ERROR;
        Q.data[Q.tu].i= arow;
        Q.data[Q.tu].j= ccol;
        Q.data[Q.tu].e= ctemp[ccol];
        }
  }
  }
  return OK;
}


Status AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &A)
{
int t,c,k;
t=1; c=1; k=1;
while((t<=M.tu) && (c<=N.tu))
    if(M.data[t].i==N.data[c].i)
      if(M.data[t].j<N.data[c].j)
        { A.data[k].i=M.data[t].i;
          A.data[k].j=M.data[t].j;   
          A.data[k].e=M.data[t].e;
          k++;   
          t++;
        }
      else if(M.data[t].j>N.data[c].j)
          { A.data[k].i=N.data[c].i;
            A.data[k].j=N.data[c].j;   
            A.data[k].e=N.data[c].e;
            k++;   
            c++;
          }
          else
            { A.data[k].i=M.data[t].i;
              A.data[k].j=M.data[t].j;   
              A.data[k].e= M.data[t].e + N.data[c].e;
              if(A.data[k].e) k++;
              t++;
              c++;
              }
    else if(M.data[t].i<N.data[c].i)
          { A.data[k].i=M.data[t].i;
            A.data[k].j=M.data[t].j;   
            A.data[k].e=M.data[t].e;
            k++;   
            t++;
          } 
        else 
          {   A.data[k].i=N.data[c].i;
            A.data[k].j=N.data[c].j;   
            A.data[k].e=N.data[c].e;
            k++;   
            c++;
          }
while(t<=M.tu)
    { A.data[k].i=M.data[t].i;
      A.data[k].j=M.data[t].j;   
      A.data[k].e=M.data[t].e;
      k++;   
      t++;
      } 
while(c<=N.tu)
    { A.data[k].i=N.data[c].i;
      A.data[k].j=N.data[c].j;   
      A.data[k].e=N.data[c].e;
      k++;   
      c++;
      }     
A.mu=M.mu;
A.nu=M.nu;
A.tu=k-1;
return OK;
}

Status SubSMatrix(RLSMatrix M,RLSMatrix &N,RLSMatrix &S)
{ int c;
  for(c=1;c<=N.tu;c++)
    N.data[c].e = 0-N.data[c].e;
  AddSMatrix(M,N,S);
  return OK;
}

int CreateRLSMatrix(RLSMatrix &M)
{ int k,t;
printf("please input M.mu,M.nu,M.tu:\n");
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
printf("please order the hang rule input M:\n");
for(k=1;k<=M.tu;k++)
  { printf("please input di %d ge shu,i j e:\n",k);
    scanf("%d%d%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
    printf(" M.data[k].i=%d,M.data[k].j=%d,M.data[k].e=%d\n",M.data[k].i,M.data[k].j,M.data[k].e);
    }
printf("please input rpos[]:\n");
for (t=1;t<=M.mu;t++)
  { printf("M.rpos[%d]= ",t);
    scanf("%d",&M.rpos[t]);
    } 
return OK;
}

void Print( RLSMatrix &M)
{ int k,t;/*,c=1;*/
printf("hang shu : %d\nlie shu : %d\nfei lin yuan ge shu : %d\n",M.mu,M.nu,M.tu);

/*for(k=1 ; k<=M.mu ; k++)                     //试试按行列打印？？？？
  { if(k==M.data[c].i)
   { for(t=1;t<=M.nu;t++)
      if(t==M.data[c].j)
       printf(" %d ",M.data[c++].e);
        else printf(" 0 ");
    printf("\n");
    }
    else {
      for(t=1;t<=M.nu;t++) printf(" 0 ");
      printf("\n");
      }
  }*/

  for(k=1;k<=M.tu;k++)
  printf(" M.data[k].i=%d,M.data[k].j=%d,M.data[k].e=%d\n",M.data[k].i,M.data[k].j,M.data[k].e);
  printf("\n");
}


void main()
{ RLSMatrix M,N,Q,A,S;
printf("please input M:\n");
CreateRLSMatrix(M);
printf("M:\n");
Print(M);
printf("please input N:\n");
CreateRLSMatrix(N);
printf("N:\n");
Print(N);
MultSMatrix(M,N,Q);
printf("M * N :\n");
Print(Q);
AddSMatrix(M,N,A);
printf("M + N :\n");
Print(A);
printf("M - N :\n");
SubSMatrix(M,N,S);       //注意N已改变了，请看SubSMatrix（）函数!!!
Print(S);   
}