#define  Maxsize   100
#define  M  6
#define  N  6
typedef struct 
{
    int r;//行号
    int c;//列号
    int d;//元素值
}TupNode;
typedef struct
{
    int rows;//行数值
    int cols;//列数值
    int nums;//非零元素个数
    TupNode data[Maxsize];
}TSMatrix;   //三元组顺序表定义
//从一个二维矩阵创建其三元组表示的运算算法
void CreatMat(TSMatrix &t,int A[M][N])
{
    int i,j;
    t.rows =M;
    t.cols =N;
    t.nums =0;
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            if(A[i][j]!=0)  //只存储非0元
            {
                t.data[t.nums].r =i;
                t.data [t.nums ].c=j;
                t.data [t.nums ].d=A[i][j];
                t.nums ++;
            }
        }
    }
}
//三元组元素赋值运算算法
int Value(TSMatrix &t,int x,int rs,int cs) 
{
    int i,k;
    if(rs>=t.rows || cs>=t.cols)
        return 0;
    while(k<t.nums && rs>t.data[k].r)  k++; //寻找位置
    while(k<t.nums && cs>t.data[k].c)  k++;
    if(t.data[k].r==rs && t.data[k].c==cs)
        t.data[k].d=x;   //该元素存在
    else   //该元素不存在
    {
        for(i=k;i<=t.nums ;i++) //将i后面的元素后移
        {
            t.data[i+1].r=t.data[i].r;
            t.data[i+1].c=t.data[i].c;
            t.data[i+1].d=t.data[i].d;
        }
        t.data[k].r=rs;
        t.data[k].c=cs;
        t.data[k].d=x;
        t.nums ++;
    }
    return 1;
}
//将指定位置的元素赋给变量的运算算法
int Assign(TSMatrix t,int &x,int rs,int cs)
{
    int k=0;
    if(rs>=t.rows ||cs>=t.cols)
        return 0;
    while(k<t.nums && rs>t.data[k].r)  k++;
    while(k<t.nums && cs>t.data[k].c)  k++;
    if(t.data[k].r==rs&&t.data[k].c==cs)
    {
        x=t.data[k].d;
        printf("第 %d 行第 %d 列的元素为：x=%d\n",rs,cs,x);
        return x;
    }
    else return 0;
}
//输出三元组运算算法
int  DispMat(TSMatrix t)
{
    int i;
    if(t.nums <=0)
        return 0;
    printf("\t%d\t%d\t%d\n",t.rows ,t.cols ,t.nums );
    printf("------------------------------------\n");
    for(i=0;i<t.nums ;i++)
        printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
    return 1;
}
//矩阵转置算法
void TsanTat(TSMatrix t,TSMatrix &tb) 
{
    int p,q=0,v;
    tb.rows =t.cols;;
    tb.cols =t.rows;
    tb.nums =t.nums;
    if(t.nums !=0)
    {
        for(v=0;v<t.cols ;v++)
        {
            for(p=0;p<t.nums  ;p++)
            {
                if(t.data[p].c==v)
                {
                    tb.data[q].r=t.data[p].c;
                    tb.data[q].c=t.data[p].r;
                    tb.data[q].d=t.data[p].d;
                    q++;
                }
            }
        }
    }
}
//两矩阵相加运算算法
int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i=0,j=0,k=0;
    char e;
    if(a.rows !=b.rows ||a.cols!=b.cols)
    {
        printf("这两矩阵不能相加：\n");
        return 0;
    }
    c.rows=a.rows ;c.cols =a.cols ;
    while(i<a.nums && j<b.nums)
    {
        if(a.data[i].r==b.data[j].r)
        {
            if(a.data[i].c <b.data[j].c)
            {
                c.data[k].r=a.data[i].r;
                c.data[k].c=a.data[i].c;
                c.data[k].d=a.data[i].d;
                k++; i++;
            }
             else if(a.data[i].c >b.data[j].c)
            {
                 c.data[k].r=b.data[j].r;
                 c.data[k].c=b.data[j].c;
                 c.data[k].d=b.data[j].d;
                 k++;
                 j++;
            }
            else 
            {
                  e=a.data[i].d+b.data[j].d;
                  if(e!=0)
                  {
                       c.data[k].r=a.data[i].r;
                       c.data[k].c=a.data[i].c;
                       c.data[k].d=e;
                       k++;
                  }
                  i++;j++;
            }
        }
        else if(a.data[k].r <b.data[j].r)
        {
              c.data[k].r=a.data[i].r;
              c.data[k].c=a.data[i].c;
              c.data[k].d=a.data[i].d;
              k++;i++;
        }
        else
        {
             c.data[k].r=b.data[j].r;
             c.data[k].c=b.data[j].c;
                c.data[k].d=b.data[j].d;
                k++;j++;
        }
        c.nums =k;
    }
    return 1;
}
int main(  )  //主函数
{
    TSMatrix t,tb,tp;
    int e;
    int Array[M][N]={0,0,1,0,0,0,
                   0,2,0,0,0,0,
                   3,0,0,0,0,0,
                   0,0,0,5,0,0,
                   0,0,0,0,6,0,
                   0,0,0,0,0,7};
    CreatMat(t,Array);
    printf("该稀疏矩阵为：\n");      DispMat(t);
    Assign(t,e,0,2);//查找元素
    TsanTat(t,tb);
    printf("转置后的矩阵为：\n");      DispMat(tb);
    MatAdd(t,tb,tp);
    printf("两矩阵相加后所得矩阵为：\n");  DispMat(tp);
    return 0;
}