//稀疏矩阵

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 100
#define ELEMTYPE int
typedef struct
{
    int i,j;
    ELEMTYPE elem;
}Triple;
typedef struct
{
    Triple data[MAXSIZE+1];
    int rcount,ccount,counter;
}TSMatrix;

void Display(TSMatrix M)
{
    int temp;
    printf("*****************\n");
    printf("i\tj\tv\n");
    printf("*****************\n");
    for(temp=1;temp<=M.counter;temp++)
    {
        if(M.data[temp].elem)
        {
            printf("%d\t%d\t%d\n",M.data[temp].i,M.data[temp].j,M.data[temp].elem);
        }
    }
}//打印三元组

void Transpose(TSMatrix M,TSMatrix N)
{
    N.rcount=M.ccount;
    N.ccount=M.rcount;
    N.counter=M.counter;
    int p,temp,q=1;
    for(temp=1;temp<=M.ccount;temp++)
    {
        for(p=1;p<=M.counter;p++)
        {
            if(M.data[p].j==temp)
            {
                N.data[q].i=M.data[p].j;
                N.data[q].j=M.data[p].i;
                N.data[q].elem=M.data[p].elem;
                q++;
            }
        }//置换并排序
    }
    printf("The transposed triple of the original one is:\n");
    Display(N);
    printf("*****************\n\n\n");
    printf("The transposed matrix of the original one is:\n");
    int x;
    int tempr[MAXSIZE]={0},tempc[MAXSIZE]={0};
    for(x=1;x<=N.counter;x++)
    {
        if(N.data[x].elem)
            tempr[x]=N.data[x].i;
            tempc[x]=N.data[x].j;
    }
    x=1;
    int s,t;
    for(s=1;s<=N.rcount;s++)
    {
        for(t=1;t<=N.ccount;t++)
        {
            if(tempr[x]==s&&tempc[x]==t)
            {
                printf("%d\t",N.data[x].elem);
                x++;
            }
            else printf("%d\t",0);
        }
        printf("\n");
    }
}//三元组逆序并输出并根据逆序后的三元组逆序输出稀疏矩阵

void Init(int rcount,int ccount)
{
    int i,j,counter=0,temp;
    TSMatrix Storage,Transposition;
    srand((unsigned)time(NULL));
    printf("The original matrix is:\n");
    for(i=1;i<=rcount;i++)
    {
        for(j=1;j<=ccount;j++)
        {
            if(0==rand()%2) printf("%d\t",0);
            else if(0==(i*ccount+j)%2) printf("%d\t",0);
            else
            {
                temp=rand()%2+rand()%9;
                printf("%d\t",temp);
                Storage.data[++counter].elem=temp;
                Storage.data[counter].i=i;
                Storage.data[counter].j=j;
            }
        }
        printf("\n");
    }
    printf("\n\n");
    Storage.ccount=ccount;
    Storage.rcount=rcount;
    Storage.counter=counter;
    printf("The triple of the original matrix is:\n");
    Display(Storage);
    printf("*****************\n\n\n");
    Transpose(Storage,Transposition);
}//初始化稀疏矩阵并打印

void main()
{
    int rcount,ccount;
    scanf("%d %d",&rcount,&ccount);
    Init(rcount,ccount);
}