#include "stdio.h"
#define MAXSIZE 10000
typedef int ElemType;
typedef struct
{ int row,col;
  ElemType v;
 }Triple;

 typedef struct
 { Triple data[MAXSIZE];
   int m,n,t;
  }TriTable;

/*add part*/
void add(TriTable *A,TriTable *B,TriTable *C)
  { int i,j,k;
    if(A->m!=B->m||A->n!=B->n)
    { printf("these two arrey unable to add"); return;}
    C->m=A->m;C->n=A->n;
    C->t=0;
    if(A->t==0&&B->t==0) return;
    i=j=k=1;
    while(i<=A->t&&j<=B->t)
    { if(A->data[i].row<B->data[j].row)
        { C->data[k]=A->data[i];
          i++;k++;
        }
        else
         { if(A->data[i].row>B->data[j].row)
           { C->data[k]=B->data[j];
             j++;k++;
           }
           else
          { if(A->data[i].col<B->data[j].col)
            { C->data[k]=A->data[i];
              i++;k++;
            }
             else
            { if(A->data[i].col>B->data[j].col)
              { C->data[k]=B->data[j];
                j++;k++;
              }
              else
               {  if(A->data[i].v+B->data[j].v!=0)
                    {   C->data[k].row=A->data[i].row;
                        C->data[k].col=A->data[i].col;
                        C->data[k].v=A->data[i].v+B->data[j].v;
                        k++;
                    }
                        i++;j++;
               }
            }
          }
        }

     }
   while(i<A->t)
      {  C->data[k]=A->data[i];
              i++;k++;
      }
    while(j<B->t)
      { C->data[k]=B->data[j];
              j++;k++;
      }
      C->t=k;
}
/*Multiplicate part*/
void MultS(TriTable *A,TriTable *B,TriTable *C)
 { int k,p,crow,brow,q,ccol;
   int num[MAXSIZE],pos[MAXSIZE],ctemp[MAXSIZE];
    if (A->n==B->m)
       { for(k=1;k<=B->m;k++)
            num[k]=0;

         for(k=1;k<=B->t;k++)
            num[B->data[k].row]++;

        pos[1]=1;

         for(k=2;k<=B->t;k++)
            pos[k]=pos[k-1]+num[k-1];

            pos[1+B->t]=pos[B->t]+1;

            C->m=A->m; C->n=B->n; C->t=0; p=1;
        while(p<=A->t)
         {crow=A->data[p].row;

          for(k=1;k<=C->n;k++)
                  ctemp[k]=0;

                while (p<=A->t&&A->data[p].row==crow)
                       {
                          brow=A->data[p].col;

                           for(q=pos[brow];q<=pos[brow+1]-1;q++)
                             {  ccol=B->data[q].col;
                                ctemp[ccol]=ctemp[ccol]+A->data[p].v*B->data[q].v;
                              }
                           p=p+1;
                        }

                          for(ccol=1;ccol<=B->n;ccol++)
                             if(ctemp[ccol]!=0)
                               { C->t=C->t+1;
                                 C->data[C->t].row=crow;
                                 C->data[C->t].col=ccol;
                                 C->data[C->t].v=ctemp[ccol];
                               }

        }
      }else printf("these two arrat can't Multiplicate");return;
 }

/*Transpose part*/
void  Transpose(TriTable *A,TriTable *B)
{ int col,i,p,q;
  int num[MAXSIZE],position[MAXSIZE];
  B->t=A->t;B->m=A->n; B->n=A->m;
  if(B->t)
   {for(col=1;col<=A->n;col++)
        num[col]=0;
    for(i=1;i<=A->t;i++)
        num[A->data[i].col]++;
    position[1]=1;
    for(col=2;col<=A->n;col++)
      position[col]=position[col-1]+num[col-1];
    for(p=1;p<=A->t;p++)
       { col=A->data[p].col;q=position[col];
         B->data[q].row=A->data[p].col;
         B->data[q].col=A->data[p].row;
         B->data[q].v=A->data[p].v;
         position[col]++;
         }
      }
 }

 /*creat part*/
void creatarrey(TriTable *A)
{ int i,j;
  printf("please input the number of row:");
  scanf("%d",&A->m);
  printf("please input the number of col:");
  scanf("%d",&A->n);
  printf("please input the number of data:");
  scanf("%d",&A->t);
  for(i=1;i<=A->t;i++)
      {printf("please input the %d data:",i);
       scanf("%d,%d,%d",&A->data[i].row,&A->data[i].col,&A->data[i].v);
      }

 }
 /*output part*/
void output(TriTable *A)
 {  int i,j,t,k=0;
      t=1;
    printf(" the arrey  is: \n");

    for(i=1;i<=A->m;i++)
     {for(j=1;j<=A->n;j++)
      {  if(A->data[t].row==i&&A->data[t].col==j)
           { printf("%4d",A->data[t].v);t++;}
            else printf("%4d",k);
       }
      printf("\n");
    }
 }
 /*main part*/
void main( )
{ int i=0;
  TriTable A,B,C;
  while(i<4)
  {printf("1 add arrey,A+B=C\n");
  printf("2 transpose arrey,A->B\n");
  printf("3 Multinomial arrey A*B=C\n");
  printf("4 quit game\n");
  printf("please select item to operarting:");

  scanf("%d",&i);
  switch(i)
   {case 1: creatarrey(&A);output(&A);creatarrey(&B);output(&B);add(&A,&B,&C);output(&C);break;
    case 2: creatarrey(&A);output(&A);Transpose(&A,&B);output(&B);break;
    case 3: creatarrey(&A);output(&A);creatarrey(&B);output(&B);MultS(&A,&B,&C);output(&C);break;
    case 4: break;
    }
  }
    getch();
}