transmatrix.c

数据结构实验与学习指导

/* TransMatrix.c */
#include"sj.h"
typedef struct
{ int i,j;
  int v;
}SPNode;                       /*定义三元组*/
typedef struct
{ SPNode data[MAXSIZE+1];
  int mu,nu,tu;
}SPMatrix;                    /*定义三元组表*/
void Input(SPMatrix *B){     /*按三元组格式输入稀疏矩阵*/
   int i;
   printf("请输入行数列数和非零元素个数:mu ,nu ,tu\n");        /*输入矩阵*/
   scanf("%d,%d,%d",&B->mu,&B->nu,&B->tu);
   for(i=1;i<=B->tu;i++)
     { printf("请输入行号列号和结点信息:i,j,v\n");
       scanf("%d,%d,%d",&B->data[i].i,&B->data[i].j,&B->data[i].v);
     }
  }/* Input*/
void Output(SPMatrix OUM)
 { int i;
   printf("mu=%d,nu=%d,tu=%d\n",OUM.mu,OUM.nu,OUM.tu);
   for(i=1;i<=OUM.tu;i++)
   printf("%d,%d,%d\n",OUM.data[i].i,OUM.data[i].j,OUM.data[i].v);
}/* Output*/
void TransM1(SPMatrix *A,SPMatrix *B)          /*矩阵转置*/
{  int col,p,q,k;
   B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;         /*行数、列数交换*/
   if(B->tu!=0)
    {q=1;
     for(col=1;col<=A->nu;col++)               /*读三元组表*/
       for(p=1;p<=A->tu;p++)
       if(A->data[p].j==col)
        {B->data[q].i=A->data[p].j;
         B->data[q].j=A->data[p].i;
         B->data[q].v=A->data[p].v;
         q++;}
    }
 } /* TransM1*/
SPMatrix *TransM2(SPMatrix *A,SPMatrix *B)
{                                              /*改进的转置方法*/
  int  p,q,col,k;
  int num[MAXSIZE],cpot[MAXSIZE];
  B->mu=A->nu;  B->nu=A->mu; B->tu=A->tu;     /* 稀疏矩阵的行、列、元素个数 */
 if (B->tu>0)                                     /* 有非零元素则转换 */
  {  for (col=1;col<=A->nu;col++)  num[col]=0;
     for (k=1;k<=A->tu;k++)                     /* 求矩阵A中每一列非零元素的个数 */
        num[A->data[k].j]++;
    cpot[1]=1;                 /* 求矩阵A中每一列第一个非零元素在B.data中的位置*/
    for (col=2;col<=A->nu;col++)
      cpot[col]= cpot[col-1]+num[col-1];
    for (p=1;p<=A->tu;p++)     /* 扫描三元组表 */
        { col=A->data[p].j;     /* 当前三元组的列号 */
          q=cpot[col];       /* 当前三元组在B.data中的位置 */
          B->data[q].i=A->data[p].j ;
          B->data[q].j=A->data[p].i ;
          B->data[q].v=A->data[p].v;
          cpot[col]++;
       } /*for  */
  }
 return B;                       /*返回的是转置矩阵的指针*/
}/* TransM2*/
Status SPMatrix_Addto(SPMatrix A, SPMatrix B, SPMatrix *C)
{ /*  两个用三元组表示的矩阵相加，先检查合法性  */
    int pa=1,pb=1,pc=1,nv;
    if (A.nu!=B.nu || A.mu!=B.mu ) {
           printf("操作不能进行!\n");
           return ERROR; }
    while ((pa<=A.tu) && (pb<=B.tu))
    {  if ( (A.data[pa].i < B.data[pb].i) || ( (A.data[pa].i == B.data[pb].i) && (A.data[pa].j < B.data[pb].j) ))
       { C->data[pc].i=A.data[pa].i ;
         C->data[pc].j=A.data[pa].j ;
         C->data[pc].v=A.data[pa].v ;
         pa++;pc++; }
       if ( (A.data[pa].i == B.data[pb].i) &&  (A.data[pa].j==B.data[pb].j) )
             /* 行列值都相等的元素 */
             {  nv=A.data[pa].v+B.data[pb].v ;
               if (nv)            /*  和不为0  */
                 { C->data[pc].i=A.data[pa].i ;
                   C->data[pc].j=A.data[pa].j ;
                   C->data[pc].v=nv ;
                   pc++;
                 } /* if (nv) */
      pa++; pb++ ;
      } /*  if */
  if ( (A.data[pa].i >B.data[pb].i) || ( (A.data[pa].i == B.data[pb].i) && (A.data[pa].j>B.data[pb].j) ))
    { C->data[pc].i=B.data[pb].i;
      C->data[pc].j=B.data[pb].j;
      C->data[pc].v=B.data[pb].v;
      pb++;pc++;
     }
       }  /* while */
   while(pa<=A.tu)
      { C->data[pc].i=A.data[pa].i ;
        C->data[pc].j=A.data[pa].j ;
        C->data[pc].v=A.data[pa].v;
        pa++;pc++;
      }
   while(pb<=B.tu)
    { C->data[pc].i=B.data[pb].i ;
      C->data[pc].j=B.data[pb].j ;
      C->data[pc].v=B.data[pb].v;
      pb++;pc++;
    }
   C->tu=pc-1;C->nu=A.nu;C->mu=A.mu;
   return TRUE;
  }/*  SPMatrix_Addto  */
void main()
{  int i;
   SPMatrix A1,A2,T1,T2,C;
   printf("输入矩阵A1\n");
   Input(&A1);
   printf("矩阵A1转置前如下\n");
   Output(A1);
   TransM1(&A1,&T1);         /*调用矩阵转置函数1*/
   printf("第一种方法转置的结果\n");
   Output(T1);
   printf("输入矩阵A2\n");
   Input(&A2);
   printf("矩阵A2转置前如下\n");
   Output(A2);
   printf("按任意键继续!\n");
   getch();
   TransM2(&A2,&T2);         /*调用矩阵转置函数2*/
   printf("第二种方法转置的结果\n");
   Output(T2);
   i=SPMatrix_Addto(A1,A2,&C);
   if(i==TRUE)
     { printf("矩阵相加C=A1+A2\n");
    Output(C);}
   getch();
}