22.txt

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

#include "stdio.h"
#include "stdlib.h"
#define   MAXSIZE   20
#define   MAXRC   50
#define   error 0
typedef   struct{int i,j;
      int e;} Triple ; 
typedef   struct{
Triple   data[MAXSIZE+1];
int   rpos[MAXRC+1];
int   mu,nu,tu;
} RLSMatrix ; 

void ADD(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q)
{   void PRINTF(RLSMatrix *Q);
  int x=1;
  int y=1;
  int z=1;   
  Q->tu=0; 
  Q->mu=A->mu;
  Q->nu=A->nu;   
  while(x<=A->tu){if(A->data[x].i<B->data[y].i){
      Q->data[z].i=A->data[x].i;
      Q->data[z].j=A->data[x].j;
      Q->data[z].e=A->data[x].e;   
      x++;z++;}   
    else if(A->data[x].i==B->data[y].i){
    if(A->data[x].j>B->data[y].j){
      Q->data[z].i=B->data[y].i;
      Q->data[z].j=B->data[y].j;
      Q->data[z].e=B->data[y].e;   
      y++;z++;}
    else if(A->data[x].j==B->data[y].j){
    if((Q->data[z].e=A->data[x].e+B->data[y].e)!=0)
{Q->data[z].i=A->data[x].i;
    Q->data[z].j=A->data[x].j;
x++;
y++;
z++;}
else
{x++;
y++;}}
    else if(A->data[x].j<B->data[y].j){
      Q->data[z].i=A->data[x].i;
      Q->data[z].j=A->data[x].j;
      Q->data[z].e=A->data[x].e;
      x++;z++;}}
    else if(A->data[x].i>B->data[y].i){
      Q->data[z].i=B->data[y].i;
      Q->data[z].j=B->data[y].j;
      Q->data[z].e=B->data[y].e;   
      y++;z++;}
  if(y>=B->tu)
    break;}//while
  if(x<=A->tu){
    while(x<=A->tu){
      Q->data[z].i=A->data[x].i;
      Q->data[z].j=A->data[x].j;
      Q->data[z].e=A->data[x].e;
      x++;z++; }}
  if(y<=B->tu){while(y<=B->tu){ 
        Q->data[z].i=B->data[y].i;
        Q->data[z].j=B->data[y].j;
        Q->data[z].e=B->data[y].e;
        y++;z++;}}

Q->tu=z;   
PRINTF(A);
PRINTF(B);
PRINTF(Q);}

void SUB(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q)
{
void PRINTF(RLSMatrix *Q);
Q->tu=0;
Q->mu=A->mu;
Q->nu=A->nu;
int x=1;
int y=1;
int z=1;
while(x<=A->tu){if(A->data[x].i<B->data[y].i){
      Q->data[z].i=A->data[x].i;
      Q->data[z].j=A->data[x].j;
      Q->data[z].e=A->data[x].e;   
      x++;z++;}
      else if(A->data[x].i==B->data[y].i)
    {if(A->data[x].j>B->data[y].j)
    { Q->data[z].i=B->data[y].i;
      Q->data[z].j=B->data[y].j;
      Q->data[z].e=0-B->data[y].e;   
      y++;z++;}
    else if(A->data[x].j==B->data[y].j){
      if((Q->data[z].e=A->data[x].e-B->data[y].e)!=0)
{Q->data[z].i=A->data[x].i;
Q->data[z].j=A->data[x].j;
x++;
y++;
z++;}
else
{x++;
y++;}
}
else if(A->data[x].j<B->data[y].j)
  { Q->data[z].i=A->data[x].i;
    Q->data[z].j=A->data[x].j;
    Q->data[z].e=A->data[x].e;
    x++;z++;}
    }

    else if(A->data[x].i>B->data[y].i)
    {   Q->data[z].i=B->data[y].i;
      Q->data[z].j=B->data[y].j;
      Q->data[z].e=0-B->data[y].e;   
      y++;z++;}
  if(y>=B->tu)
  break;
  }//while   
  if(x<=A->tu){
    while(x<=A->tu){
      Q->data[z].i=A->data[x].i;
      Q->data[z].j=A->data[x].j;
      Q->data[z].e=A->data[x].e;
      x++;z++;}
  }
  if(y<=B->tu){
    while(y<=B->tu){ 
      Q->data[z].i=B->data[y].i;
      Q->data[z].j=B->data[y].j;
      Q->data[z].e=0-B->data[y].e;
      y++;z++; }
  }   
Q->tu=z; 
PRINTF(A);
PRINTF(B);
PRINTF(Q);}

void MUL(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q)
{   void PRINTF(RLSMatrix *Q);   
int ctemp[MAXRC];
int tp,p,t,arow,brow,q,ccol,i;   
Q->mu=A->mu;
Q->nu=B->nu;
Q->tu=0;
if(A->tu*B->tu!=0){
  for(arow=1;arow<=A->mu;++arow)
  { 
    for(i=1;i<=Q->nu;i++)
    ctemp=0;       
    Q->rpos[arow]=Q->tu+1;
    if(arow<A->mu)
      tp=A->rpos[arow+1];
    else
      tp=A->tu+1;
    for(p=A->rpos[arow];p<tp;++p){
      brow=A->data[p].j;
      if(brow<B->mu)
        t=B->rpos[brow+1];
      else
        t=B->tu+1;
      for(q=B->rpos[brow];q<t;++q){
        ccol=B->data[q].j;
        ctemp[ccol]+=A->data[p].e*B->data[q].e;}
    }
    for(ccol=1;ccol<=Q->nu;++ccol)
    {if(ctemp[ccol])
{if(++Q->tu<=MAXSIZE)
{Q->data[Q->tu].i=arow;
  Q->data[Q->tu].j=ccol;
  Q->data[Q->tu].e=ctemp[ccol];}
    }
    }
}
}

PRINTF(A);
PRINTF(B);
PRINTF(Q);}


void PRINTF( RLSMatrix *A)
{
int arow,i=1,col;
int z=0;
for(arow=1;arow<=A->mu;arow++)
{   printf("\n");
for(col=1;col<=A->nu;col++)
{   if(A->data.i==arow&&A->data.j==col&&i<=A->tu)
    printf("%-4d",A->data[i++].e);
else printf("%-4d",z);}
}
printf("\n");}
  
void main()
{   void ADD(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q);
void SUB(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q);
void MUL(RLSMatrix *A,RLSMatrix *B,RLSMatrix *Q); 
int k,c,num[MAXRC];
char cmd;
RLSMatrix *A,*B,*Q;   
A=( RLSMatrix *)malloc(sizeof( RLSMatrix));
B=( RLSMatrix *)malloc(sizeof( RLSMatrix));
Q=( RLSMatrix *)malloc(sizeof( RLSMatrix));
do{
printf("请输入矩阵A的行数列数和非零元个数:");
scanf("%d %d %d",&A->mu,&A->nu,&A->tu);
printf("请输入矩阵A的非零元：");
for(k=1;k<=A->tu;k++)
  scanf("%d %d %d",&A->data[k].i,&A->data[k].j,&A->data[k].e);
for(k=1;k<=A->mu;k++)
num[k]=0;
for(k=1;k<=A->tu;k++)
++num[A->data[k].i];
A->rpos[1]=1;
for(k=2;k<=A->mu;k++)
A->rpos[k]=A->rpos[k-1]+num[k-1]; 
printf("请输入矩阵B的行数列数和非零元个数:");
scanf("%d %d %d",&B->mu,&B->nu,&B->tu);
printf("请输入矩阵B的非零元：");
for(k=1;k<=B->tu;k++)
  scanf("%d %d %d",&B->data[k].i,&B->data[k].j,&B->data[k].e);

for(k=1;k<=B->mu;k++)
num[k]=0;
for(k=1;k<=B->tu;k++)
++num[B->data[k].i];
B->rpos[1]=1;
for(k=2;k<=B->mu;k++)
B->rpos[k]=B->rpos[k-1]+num[k-1]; 
getchar();
printf("请输入要进行的操作:");
c=getchar();
if(c=='+')
{
  if(A->mu==B->mu&&A->nu==B->nu)
    ADD(A,B,Q);}
else if(c=='-')
{
  if(A->mu==B->mu&&A->nu==B->nu)
    SUB(A,B,Q);}
else if(c=='*')
{
  if(A->nu==B->mu)
    MUL(A,B,Q);}
else
  printf("error operation!");
printf(" Y或y继续");
scanf("%s",&cmd);
}while(cmd=='Y'||cmd=='y');
}