haha.c

矩阵运算包含加减乘三元组顺序表存储的c语言

  #include <stdio.h>

  #include <conio.h>

  #include <stdlib.h>

 

  #define MAXR 20  /*最大行数*/

  #define MAXC 20  /*最大列数*/

  #define MAXSIZE MAXR*MAXC  /*最多非零元个数*/

 

  typedef struct{

    int i;  /*行下标*/

    int j;  /*列下标*/

    int e;  /*非零元值*/

  }Triple;  /*三元组类型*/

 

  typedef struct {

    Triple data[MAXSIZE];  /*三元组表*/

    int *rpos;  /*指向各行第一个非零元的位置表*/

    int mu;  /*行数*/

    int nu;  /*列数*/

    int tu;  /*非零元个数*/

  }RLSMatrix;

 

  int CreatSM(RLSMatrix *M){

    /*创建稀疏矩阵M*/

    int i,t=0,prei=0,prej=0;

 

    do{

      printf("\n请输入矩阵的行数(1~%d)：",MAXR);

      scanf("%d",&M->mu);

    }while(M->mu<1||M->mu>MAXR);

 

    do{

      printf("请输入矩阵的列数(1~%d)：",MAXC);

      scanf("%d",&M->nu);

    }while(M->nu<1||M->nu>MAXC);

 

    printf("请按行序输入各三元组，输入0,0,0表示结束。\n");

 

    while(t<MAXSIZE){

      printf("%3d:  ",t+1);

      scanf("%d,%d,%d",&M->data[t].i,&M->data[t].j,&M->data[t].e);

      if (!M->data[t].i&&!M->data[t].j&&!M->data[t].e) break;

      if (M->data[t].i<1||M->data[t].i>M->mu){

       printf("行下标越界！请重新输入！\n");

        continue;

      }

      if (M->data[t].j<1||M->data[t].j>M->nu){

        printf("列下标越界！请重新输入！\n");

        continue;

      }

      if ((M->data[t].i<prei)||(M->data[t].i==prei&&M->data[t].j<prej)){

        printf("\n错误！未按行序输入三元组！\n按任一键返回主菜单...");

        getch();

        return 0;

      }

      prei=M->data[t].i;

      prej=M->data[t].j;

      t++;

    }/*while*/

 

    M->tu=t;

 

    if (M->rpos) free(M->rpos);

    M->rpos=(int *)malloc(M->mu*sizeof(int));

    if (!M->rpos) exit(-2);

 

    t=0;

    for(i=0;i<M->mu;++i){

      M->rpos[i]=t;

      while(M->data[t].i==i+1) t++;

    }

    return 1;

  }/*CreatSM*/

 

  void PrintSM(RLSMatrix *M){

    /*输出稀疏矩阵M*/

    int i,j,t;

    t=0;

    for(i=1;i<=M->mu;++i){

      for(j=1;j<=M->nu;++j){

       if ((M->data[t].i==i)&&(M->data[t].j==j)){

         printf("%5d",M->data[t].e);

         t++;

       }/*if*/

       else printf("%5d",0);

      }/*for_j*/

      printf("\n");

    }/*for_i*/

  }/*PrintSM*/

 

  int AddSM(RLSMatrix *M, RLSMatrix *N ,RLSMatrix *Q){

    /*稀疏矩阵相加，Q=M+N*/

    int row,d,pm,pn,qm,qn;

    if (M->mu!=N->mu||M->nu!=N->nu){

      printf("\n两矩阵行列数不等，不能相加！\n按任一键继续...");

      getch();

      return 0;

    }/*if*/

 

    Q->mu=M->mu;

    Q->nu=M->nu;

    Q->tu=0;

 

    if (Q->rpos) free(Q->rpos);

    Q->rpos=(int *)malloc(Q->mu*sizeof(int));

    if (!Q->rpos) exit(-2);

 

    for(row=0;row<Q->mu;++row){

      pm=M->rpos[row];

      pn=N->rpos[row];

      Q->rpos[row]=Q->tu;

      if (row==Q->mu-1){ qm=M->tu;  qn=N->tu; }

      else{ qm=M->rpos[row+1];  qn=N->rpos[row+1]; }

      /*令qm指向M中当前行最后一个三元组的下一位置*/

      /*令qn指向N中当前行最后一个三元组的下一位置*/

      while(pm<qm&&pn<qn){

       if (M->data[pm].j<N->data[pn].j){

          /*M中当前三元组列下标较小，即N中对应位置为零元素*/

         Q->data[Q->tu].i=M->data[pm].i;

         Q->data[Q->tu].j=M->data[pm].j;

         Q->data[Q->tu].e=M->data[pm].e;

          Q->tu++;

          pm++;

        }

       else if (M->data[pm].j>N->data[pn].j){/*N中当前三元组列下标较小*/

              Q->data[Q->tu].i=N->data[pn].i;

              Q->data[Q->tu].j=N->data[pn].j;

              Q->data[Q->tu].e=N->data[pn].e;

               Q->tu++;

               pn++;

             }

             else{/*M和N中当前三元组列下标相等*/

              d=M->data[pm].e+N->data[pn].e;

               if (d){

               Q->data[Q->tu].i=M->data[pm].i;

               Q->data[Q->tu].j=M->data[pm].j;

                 Q->data[Q->tu].e=d;

                 Q->tu++;

               }/*if_d*/

               pm++;

               pn++;

             }/*else*/

      }/*while*/

      while(pm<qm){

       Q->data[Q->tu].i=M->data[pm].i;

       Q->data[Q->tu].j=M->data[pm].j;

       Q->data[Q->tu].e=M->data[pm].e;

        Q->tu++;

        pm++;

      }/*while_pm<qm*/

      while(pn<qn){

       Q->data[Q->tu].i=N->data[pn].i;

       Q->data[Q->tu].j=N->data[pn].j;

       Q->data[Q->tu].e=N->data[pn].e;

        Q->tu++;

        pn++;

      }/*while_pn<qn*/

    }/*for*/

    return 1;

  }/*AddSM*/

 

  int MinusSM(RLSMatrix *M, RLSMatrix *N ,RLSMatrix *Q){

    /*稀疏矩阵相减，Q=M-N*/

    int row,d,pm,pn,qm,qn;

    if (M->mu!=N->mu||M->nu!=N->nu){

      printf("\n两矩阵行列数不等，不能相减！\n按任一键继续...");

      getch();

      return 0;

    }/*if*/

    Q->mu=M->mu;

    Q->nu=M->nu;

    Q->tu=0;

    if (Q->rpos) free(Q->rpos);

    Q->rpos=(int *)malloc(Q->mu*sizeof(int));

    if (!Q->rpos) exit(-2);

    pm=M->rpos[0]; /*令pm指向M中第一行第一个三元组*/

    pn=N->rpos[0]; /*令pn指向N中第一行第一个三元组*/

 

    for(row=0;row<Q->mu;++row){

      Q->rpos[row]=Q->tu;

      if (row==Q->mu-1){ qm=M->tu;  qn=N->tu; }

      else{ qm=M->rpos[row+1];  qn=N->rpos[row+1]; }

      /*令qm指向M中当前行最后一个三元组的下一位置*/

      /*令qn指向N中当前行最后一个三元组的下一位置*/

      while(pm<qm&&pn<qn){

        if (M->data[pm].j<N->data[pn].j){

          /*M中当前三元组列下标较小，即N中对应位置为零元素*/

          Q->data[Q->tu].i=M->data[pm].i;

          Q->data[Q->tu].j=M->data[pm].j;

          Q->data[Q->tu].e=M->data[pm].e;

          Q->tu++;

          pm++;

        }

        else if (M->data[pm].j>N->data[pn].j){/*N中当前三元组列下标较小*/

               Q->data[Q->tu].i=N->data[pn].i;

               Q->data[Q->tu].j=N->data[pn].j;

               Q->data[Q->tu].e=-N->data[pn].e;

               Q->tu++;

               pn++;

             }

             else{/*M和N中当前三元组列下标相等*/

               d=M->data[pm].e-N->data[pn].e;

               if (d){

                 Q->data[Q->tu].i=M->data[pm].i;

                 Q->data[Q->tu].j=M->data[pm].j;

                 Q->data[Q->tu].e=d;

                 Q->tu++;

               }/*if_d*/

               pm++;

               pn++;

             }/*else*/

      }/*while*/

      while(pm<qm){

        Q->data[Q->tu].i=M->data[pm].i;

        Q->data[Q->tu].j=M->data[pm].j;

        Q->data[Q->tu].e=M->data[pm].e;

        Q->tu++;

        pm++;

      }/*while_pm<qm*/

      while(pn<qn){

        Q->data[Q->tu].i=N->data[pn].i;

        Q->data[Q->tu].j=N->data[pn].j;

        Q->data[Q->tu].e=-N->data[pn].e;

        Q->tu++;

        pn++;

      }/*while_pn<qn*/

    }/*for*/

    return 1;

  }/*MinusSM*/

 

  int MultSM(RLSMatrix *M, RLSMatrix *N ,RLSMatrix *Q){

    /*稀疏矩阵相乘，Q=M*N */

    int i,j,p,q,k,tn,tm;

    int ctemp[MAXC];

    if (M->nu!=N->mu){

      printf("\n左阵列数与右阵行数不等，不能相乘！\n按任一键继续...");

      getch();

      return 0;

    }/*if*/

    Q->mu=M->mu;

    Q->nu=N->nu;

    Q->tu=0;

    if (M->tu&&N->tu){

      if (Q->rpos) free(Q->rpos);

      Q->rpos=(int *)malloc(Q->mu*sizeof(int));

      if (!Q->rpos) exit(-2);

      for(i=0;i<M->mu;++i){/*对M (亦即Q) 的每行*/

       for(j=0;j<Q->nu;++j)

         ctemp[j]=0;  /*ctemp中暂存Q当前行各元素值*/

       Q->rpos[i]=Q->tu;  /*Q当前行第一个非零元的存储位置*/

       if (i<M->mu-1) tm=M->rpos[i+1];

         else tm=M->tu;

       for(p=M->rpos[i];p<tm;++p){

          k=M->data[p].j-1;

         if (k<N->mu-1) tn=N->rpos[k+1];

         else tn=N->tu;

         for(q=N->rpos[k];q<tn;++q){

            j=N->data[q].j-1;

            ctemp[j]+=M->data[p].e*N->data[q].e;

          }/*for_q*/

        }/*for_p*/

        for(j=0;j<Q->nu;++j)/*压缩存储Q的当前行*/

          if (ctemp[j]){/*若当前元素为非零元*/

           if (Q->tu==MAXSIZE){

              printf("\nQ中非零元过多！\n按任一键继续...");

              getch();

              return 0;

           }/*if*/

            Q->data[Q->tu].i=i+1;

            Q->data[Q->tu].j=j+1;

           Q->data[Q->tu].e=ctemp[j];

           Q->tu++;

          }/*if_ctemp[j]*/

       }/*for_i*/

    }/*if_M.tu&&N.tu*/

    return 1;

  }/*MultSM*/

 

  main(){

    RLSMatrix M,N,Q;

    int end=0;

    char choice;

    M.rpos=N.rpos=Q.rpos=NULL;

    while(!end){

      clrscr();

      printf("  欢迎使用稀疏矩阵运算器\n");

      printf("**************************\n\n");

      printf("1-矩阵相加\n");

      printf("2-矩阵相减\n");

      printf("3-矩阵相乘\n");

      printf("0-退    出\n");

      printf("请输入您的选择(1,2,3,0):");

      do{

        scanf("%c",&choice);

      }while(choice-'0'<0||choice-'0'>3);

      switch(choice){

        case '1':

          clrscr();

          printf("请输入第一个矩阵\n");

          printf("==============\n");

         if (CreatSM(&M)){

           printf("\n请输入第二个矩阵\n");

           printf("==============\n");

           if (CreatSM(&N)){

             if (AddSM(&M,&N,&Q)){

                printf("\n两矩阵之和为：\n");

              PrintSM(&Q);

               printf("\n按任一键继续...");

                getch();

              }

            }

          }

          break;

        case '2':

          clrscr();

          printf("请输入第一个矩阵\n");

          printf("==============\n");

          if (CreatSM(&M)){

            printf("\n请输入第二个矩阵\n");

            printf("==============\n");

            if (CreatSM(&N)){

              if (MinusSM(&M,&N,&Q))
              {
              printf("\n两矩阵之差为：\n");

              PrintSM(&Q);

               printf("\n按任一键继续...");

                getch();

              }

            }

          }

          break;

        case '3':

          clrscr();

          printf("请输入第一个矩阵\n");

          printf("==============\n");

          if (CreatSM(&M)){

            printf("\n请输入第二个矩阵\n");

            printf("==============\n");

            if (CreatSM(&N)){

             if (MultSM(&M,&N,&Q)){

                printf("\n两矩阵之积为：\n");

              PrintSM(&Q);

               printf("\n按任一键继续...");

                getch();

              }

            }

          }

          break;

        case '0':

          end=1;

      }/*switch*/

    }/*while_end*/

  }/*main*/