include <stdio.h>

include <stdlib.h>

define OK 1

define ERROR -1

define MAX 100

typedef struct
{
int i, j;//该非零元的下标
int e;
} Tripe;
typedef struct TSMatrix
{
Tripe data[MAX+1];//下标从1开始
int mu, nu, tu;//矩阵行数列数和非零元素个数
} TSMatrix;

void Print(TSMatrix T)
{
TSMatrix *T1;
T1 = &T;
int r, c, num = 0;
int k = 1;
for(r = 1; r <= T1->mu; r++)
{
for(c = 1; c <= T1->nu; c++)
{
if((T1->data[k].i == r) && (T1->data[k].j == c))
{
printf("%d ", T1->data[k].e);
k++;
num++;
}
else
{
printf("0 ");
num++;
}
if(num % T1->mu == 0)
{
printf("\n");
}
}
}
}
void CreateTSM(TSMatrix T)
{
int n = 1;
printf("请输入矩阵的行数和列数及非零元素个数：");
scanf("%d", &T->mu);
scanf("%d", &T->nu);
scanf("%d", &T->tu);
printf("\n");
printf("请输入非零元素行数和列数及数值: \n");
while(n <= T->tu)
{
scanf("%d", &T->data[n].i);
scanf("%d", &T->data[n].j);
scanf("%d", &T->data[n].e);
n++;
}
printf("\n");
Print(T);
}

void FastTransMatrix(TSMatrix a, TSMatrix b)
{
int p, q, col, k;
int num[MAX], cpot[MAX];
b.mu = a.nu;
b.nu = a.mu;
b.tu = a.tu;
if(b.tu==0) printf(" The Matrix A=0\n" );
else
{
for (col=1; col<=a.nu; ++col) num[col]=0;
for (k=1 ; k<=a.tu ; ++k)
++num[ a.data[k].j];
for (cpot[1]=1, 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[q].i=a.data[p].j;
b.data[q].j=a.data[p].i ;
b.data[q].e=a.data[p].e ;
++cpot[col] ;
}
}
printf("转置后：\n");
Print(b);
}

int AddTSM(TSMatrix Ta, TSMatrix Tb, TSMatrix Tc){
int k = 1, n = 1, p = 1, e;
if(Ta.mu != Tb.mu || Ta.nu != Tb.nu) return ERROR;
Tc->mu = Ta.mu;
Tc->nu = Ta.nu;
Tc->tu = 0;
while(k <= Ta.tu && n <= Tb.tu){
if((Ta.data[k].i == Tb.data[n].i) && (Ta.data[k].j == Tb.data[n].j)){
e = Ta.data[k].e + Tb.data[n].e;
if(e != 0){
Tc->data[p].i = Ta.data[k].i;
Tc->data[p].j = Ta.data[k].j;
Tc->data[p].e = e;
Tc->tu++;
k++;
p++;
n++;
}else{
k++;
n++;
}
}else if(((Ta.data[k].i == Tb.data[n].i) && (Ta.data[k].j < Tb.data[n].j)) || (Ta.data[k].i < Tb.data[n].i)){
Tc->data[p].i = Ta.data[k].i;
Tc->data[p].j = Ta.data[k].j;
Tc->data[p].e = Ta.data[k].e;
Tc->tu++;
p++;
k++;
}else if(((Ta.data[k].i == Tb.data[n].i) && (Ta.data[k].j > Tb.data[n].j)) || (Ta.data[k].i > Tb.data[n].i)){
Tc->data[p].i = Tb.data[n].i;
Tc->data[p].j = Tb.data[n].j;
Tc->data[p].e = Tb.data[n].e;
Tc->tu++;
p++;
n++;
}
}
while(k <= Ta.tu){
Tc->data[p].i = Ta.data[k].i;
Tc->data[p].j = Ta.data[k].j;
Tc->data[p].e = Ta.data[k].e;
Tc->tu++;
p++;
k++;
}
while(n <= Tb.tu){
Tc->data[p].i = Tb.data[n].i;
Tc->data[p].j = Tb.data[n].j;
Tc->data[p].e = Tb.data[n].e;
Tc->tu++;
p++;
n++;
}
printf("Add: \n");
Print(Tc);
return OK;
}
int main()
{
TSMatrix Ta, Ta1, Tb, Tc;
CreateTSM(&Ta);
FastTransMatrix(Ta, Tb);
CreateTSM(&Ta1);
AddTSM(Ta, Ta1, &Tc);
return 0;
}