1.txt

- 严蔚敏《数据结构(c语言版)习题集》 参考答案 [数据结构与算法——面向对象的C++设计模式.rar] - 本书的主要内容是数据结构和算法的基本原理－－这是设计大而复杂的软件产品所必须具备的基

#include <stdio.h>
#define MAXSIZE 1000
#define MAXRC 100
typedef struct
{
     int i,j;
     int e;
}Triple;
typedef struct
{
     Triple data[MAXSIZE+1];
     int rpos[MAXRC+1];
     int mu,nu,tu;
}RLSMatrix;

ScanRLSMatrix(RLSMatrix *T)
{
     int k;
  printf("     ***********************************************************\n");
     printf("             请输入矩阵的行数，列数，非零元素个数         \n");
     printf("         ");
     scanf("%d,%d,%d",&(*T).mu,&(*T).nu,&(*T).tu);
     if((*T).tu>MAXSIZE){printf("非零个数超出定义范围！");exit(0);}
     for(k=1;k<=(*T).tu;k++){
                 printf("         按行存储请输入第%d个非零元素的行数,列数,其值:",k);
                 scanf("%d,%d,%d",&(*T).data[k].i,&(*T).data[k].j,&(*T).data[k].e);
        if(!(*T).data[k].i||!(*T).data[k].j||(*T).data[k].i>(*T).mu||(*T).data[k].j>(*T).nu){
                       printf("输入有误！");
                    exit(0);
                 }

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


     int num[(*T).mu+1],row,cpot[(*T).mu+1];
     cpot[1]=1;
     for(k=1;k<=(*T).mu;k++)
           num[k]=0;

     for(k=1;k<=(*T).tu;k++)
           ++num[(*T).data[k].i];
     for(row=2;row<=(*T).mu;row++)
                 cpot[row]=cpot[row-1]+num[row-1];

     for(row=1;row<=(*T).mu;row++){
           if(cpot[row]<=(*T).tu)
              if((*T).data[cpot[row]].i==row){
                  (*T).rpos[row]=cpot[row];
                 }
              else
                    (*T).rpos[row]=0;
           else
                 (*T).rpos[row]=0;
           }
}

PrintRLSMatrix(RLSMatrix T)
{int a,b,m=0;
  printf("       -----------------------------------------\n");

     for(a=1;a<=(T).mu;a++){printf("           ");
           for(b=1;b<=(T).nu;b++){
                 if((T).rpos[a]&&a==(T).data[(T).rpos[a]].i&&b==(T).data[(T).rpos[a]].j){
                       //(T).rpos[a]不为零时，输出该行的非零元
                       printf("%4d",(T).data[(T).rpos[a]].e);
                       (T).rpos[a]++;
                       }
                 else
                       {
                    printf("%4d",m);}
                 }
           printf("\n");
           }
  printf("       ----------------------------------------\n");
}

FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q)
{
     int col,t,p,q,num[M.nu],cpot[M.nu];
     (*Q).mu=M.nu;(*Q).nu=M.mu;(*Q).tu=M.tu;
     if((*Q).tu){
           for(col=1;col<=M.nu;++col)num[col]=0;
           for(t=1;t<=M.tu;++t)++num[M.data[t].j];
           cpot[1]=1;
           
           for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];
           for(p=1;p<=M.tu;++p){
                 col=M.data[p].j;q=cpot[col];
                 (*Q).data[q].i=M.data[p].j;
                 (*Q).data[q].j=M.data[p].i;
                 (*Q).data[q].e=M.data[p].e;
                 ++cpot[col];
           }
     }

     int Num[(*Q).mu+1],row,Cpot[(*Q).mu+1],k;
     Cpot[1]=1;
     for(k=1;k<=(*Q).mu;k++)
           Num[k]=0;

     for(k=1;k<=(*Q).tu;k++)
           ++Num[(*Q).data[k].i];
     for(row=2;row<=(*Q).mu;row++)
                 Cpot[row]=Cpot[row-1]+Num[row-1];

     for(row=1;row<=(*Q).mu;row++){
           if(Cpot[row]<=(*Q).tu)
              if((*Q).data[Cpot[row]].i==row){
                  (*Q).rpos[row]=Cpot[row];
                 }
              else
                    (*Q).rpos[row]=0;
           else
                 (*Q).rpos[row]=0;
           }
     return 1;
}

HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)
{
  if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
           {printf("不满足矩阵相加的条件!");return 0;}
     int k=1;
     Triple *p,*q;
 
     p=&(*M).data[1];
     q=&(*N).data[1];
     while(p<(*M).data+(*M).tu+1&&q<(*N).data+(*N).tu+1)
           if((*p).i<=(*q).i)
                 if((*p).i<(*q).i){
                       (*Q).data[k].i=(*p).i;
                       (*Q).data[k].j=(*p).j;
                       (*Q).data[k].e=(*p).e;
                       k++;p++;
                       }
                 else
                       if((*p).j<=(*q).j)
                          if((*p).j<(*q).j){
                                   (*Q).data[k].i=(*p).i;
                                   (*Q).data[k].j=(*p).j;
                                   (*Q).data[k].e=(*p).e;
                                   k++;p++;
                                   }
                          else
                                   {
                                   (*Q).data[k].i=(*p).i;
                                   (*Q).data[k].j=(*p).j;
                                   (*Q).data[k].e=(*p).e+(*q).e;
                                   k++;p++;q++;
                                   }
                       else {
                             (*Q).data[k].i=(*q).i;
                             (*Q).data[k].j=(*q).j;
                             (*Q).data[k].e=(*q).e;
                             k++;q++;
                             }
           else
                 {
                 (*Q).data[k].i=(*q).i;
                 (*Q).data[k].j=(*q).j;
                 (*Q).data[k].e=(*q).e;
                 k++;q++;
                 }
    if(p<=(*M).data+(*M).tu)
      while(p<=(*M).data+(*M).tu){
                    (*Q).data[k].i=(*p).i;
                    (*Q).data[k].j=(*p).j;
                    (*Q).data[k].e=(*p).e;
                    k++;p++;
                    }
    if(q<=(*N).data+(*N).tu)
      while(q<=(*N).data+(*N).tu){
                    (*Q).data[k].i=(*q).i;
                    (*Q).data[k].j=(*q).j;
                    (*Q).data[k].e=(*q).e;
                    k++;q++;
                    }

     (*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;


     int num[(*Q).mu+1],row,cpot[(*Q).mu+1];
     cpot[1]=1;
     for(k=1;k<=(*Q).mu;k++)
           num[k]=0;

     for(k=1;k<=(*Q).tu;k++)
           ++num[(*Q).data[k].i];
     for(row=2;row<=(*Q).mu;row++)
                 cpot[row]=cpot[row-1]+num[row-1];

     for(row=1;row<=(*Q).mu;row++){
           if(cpot[row]<=(*Q).tu)
              if((*Q).data[cpot[row]].i==row){
                  (*Q).rpos[row]=cpot[row];
                 }
              else
                    (*Q).rpos[row]=0;
           else
                 (*Q).rpos[row]=0;
     }
}


ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)
{
  if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
           {printf("不满足矩阵相减的条件!");return 0;}
     int i;
     for(i=1;i<=(*N).nu;i++)
           (*N).data.e*=-1;
     HeRLSMatrix(&(*M),&(*N),&(*Q));

}

JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{
     int arow,ctemp[N.nu+1],p,tp,i=1,j=1,t,q,ccol,h=1,n=1;
     if(M.nu!=N.mu){
           printf("不满足矩阵相乘的条件！");exit(0);}
     (*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(n=0;n<N.nu+1;n++)
                 ctemp[n]=0;
        if(M.rpos[arow]!=0){
                       p=M.rpos[arow];
                    if(arow<M.mu){
                          if(M.rpos[arow+1]==0){
                              if(arow+1<M.mu){
                                    while(arow+i<M.mu&&M.rpos[arow+i]==0)
                                            i++;
                                    tp=M.rpos[arow+i];
                                    if(tp==0)
                                         tp=M.tu+1;
                              }
                             else tp=M.tu+1;
                          }
                       else tp=M.rpos[arow+1];
                    }
                    else tp=M.tu+1;
                for(p;p<tp;p++){
                      if(N.rpos[M.data[p].j]!=0){
                            q=N.rpos[M.data[p].j];
                            if(M.data[p].j<N.mu){
                              if(N.rpos[M.data[p].j+1]==0){
                                    if(M.data[p].j+1<N.mu){
                                        while(M.data[p].j+1<N.mu&&N.rpos[M.data[p].j+j]==0)
                                                j++;
                                        t=N.rpos[M.data[p].j+j];
                                        if(t==0)
                                              t=N.tu+1;
                                    }
                                    else t=N.tu+1;
                              }
                              else t=N.rpos[M.data[p].j+1];
                        }
                        else t=N.tu+1;
                        for(q;q<t;q++){
                              ccol=N.data[q].j;
                              ctemp[ccol]+=M.data[p].e*N.data[q].e;
                        }
                  }
          }
        for(ccol=1;ccol<=N.nu+1;ccol++)
                    if(ctemp[ccol]){
                             if(h>MAXSIZE){printf("非零个数超出定义范围！");exit(0);}
                          (*Q).data[h].i=arow;
                          (*Q).data[h].j=ccol;
                          (*Q).data[h].e=ctemp[ccol];
                          h++;
                       }
              }
        }
  }
  (*Q).tu=h-1;


  int num[(*Q).mu+1],row,cpot[(*Q).mu+1],k;
     cpot[1]=1;
     for(k=1;k<=(*Q).mu;k++)
           num[k]=0;

     for(k=1;k<=(*Q).tu;k++)
           ++num[(*Q).data[k].i];
     for(row=2;row<=(*Q).mu;row++)
                 cpot[row]=cpot[row-1]+num[row-1];

     for(row=1;row<=(*Q).mu;row++){
           if(cpot[row]<=(*Q).tu)
              if((*Q).data[cpot[row]].i==row){
                  (*Q).rpos[row]=cpot[row];
                 }
              else
                    (*Q).rpos[row]=0;
           else
                 (*Q).rpos[row]=0;
           }
}


main()
{
     RLSMatrix M,N,Q;
  char ch;
     printf("                 ***************************                 \n");
     printf("                 **               **                 \n");
     printf("                 **   稀疏矩阵运算器   **                 \n");
     printf("                 **   ---------------------   **                 \n");
     printf("                 ***************************                 \n");
     printf("   _____________________________________________________________________   \n");
     printf("   |                     请选择                     |   \n");
     printf("   |   A.加法   B.减法   C.乘法   D.转置 Y.继续运算   N.结束运算 |   \n");
  printf("   |_____________________________________________________________________|   \n\n");
     printf("\2 输入数字时请用逗号隔开！\n\n");
     printf("   ->");
     scanf("%c",&ch);
     while(ch!='N'){
           switch(ch){
                 case'A':{ printf("     请输入要求和的两个矩阵：\n\n");
                        printf("     输入第一个矩阵：\n\n");
                              ScanRLSMatrix(&M);
                              printf("     输入的第一个矩阵为：\n\n");
                              PrintRLSMatrix(M);
                              printf("     输入第二个矩阵：\n\n");
                              ScanRLSMatrix(&N);
                              printf("     输入的第二个矩阵为：\n\n");
                              PrintRLSMatrix(N);
                              HeRLSMatrix(&M,&N,&Q);
                              printf("     两矩阵之和为：\n\n");
                              PrintRLSMatrix(Q);
                              printf("     是否继续运算（Y/N）？\n\n");
                              printf("   ->");
                              ch=getchar();
                             };break;
                 case'B':{ printf("     请按次序输入要求差的两个矩阵：\n\n");
                        printf("     输入第一个矩阵：\n\n");
                              ScanRLSMatrix(&M);
                              printf("     输入的第一个矩阵为：\n\n");
                              PrintRLSMatrix(M);
                              printf("     输入第二个矩阵：\n\n");
                              ScanRLSMatrix(&N);
                              printf("     输入的第二个矩阵为：\n\n");
                              PrintRLSMatrix(N);
                              ChaRLSMatrix(&M,&N,&Q);
                              printf("     两矩阵之差为：\n\n");
                              PrintRLSMatrix(Q);
                              printf("是否继续运算（Y/N）？\n\n");
                              printf("   ->");
                              ch=getchar();
                             }break;
                 case'C':{printf("       请按次序输入要求积的两个矩阵：\n\n");
                        printf("     输入第一个矩阵：\n\n");
                              ScanRLSMatrix(&M);
                              printf("     输入的第一个矩阵为：\n\n");
                              PrintRLSMatrix(M);
                              printf("     输入第二个矩阵：\n\n");
                              ScanRLSMatrix(&N);
                              printf("     输入的第二个矩阵为：\n\n");
                              PrintRLSMatrix(N);
                              JiRLSMatrix(M,N,&Q);
                              printf("     两矩阵之积为：\n\n");
                              PrintRLSMatrix(Q);
                              printf("是否继续运算（Y/N）？\n\n");
                              printf("   ->");
                              ch=getchar();
                             }break;

                 case'D':{printf("请输入要转置的矩阵：\n\n");
                        ScanRLSMatrix(&M);
                              printf("     输入的要转置的矩阵为：\n\n");
                              PrintRLSMatrix(M);
                              FasttransposeRLSMatrix(M,&Q);
                              printf("转置矩阵为：\n\n");
                              PrintRLSMatrix(Q);
                              printf("是否继续运算（Y/N）？\n\n");
                              printf("   ->");
                              ch=getchar();
                          }break;

                 case'Y':{printf("请选择运算\n");
                        printf("   ->");
                              ch=getchar();
                             }break;
                 default:printf("->");ch=getchar();break;
                 }
     }
printf("                       运算结束！\n\n");
printf("         \1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1谢谢使用!\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\n\n");
getch();
}