#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 100  //假设非零元素个数的最大值为100
#define MAXRC 10    //假设矩阵的最大行数为10
typedef int ElemType;
typedef struct
{
    int i,j;          //非零元的行下标和列下标
    ElemType e;     //非零元的值
}Triple;            //三元组定义
typedef struct
{
    Triple data[MAXSIZE];   
    int rpos[MAXRC];        //各行第一个非零元在三元组的位置表
    int hs,ls,fls;            
}TSMatrix,*Matrix;          //三元组顺序表定义
 
void Creat(TSMatrix &M)      //参数传入稀疏矩阵地址                                                                                                                        
{
    int i,k;
    for(i=1;i<=MAXRC;i++)
        M.rpos[i]=0;         //行数初始化为0
    printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");
    scanf("%d %d %d",&M.hs,&M.ls,&M.fls);
    for(i=1;i<=M.fls;i++)    //循环输入非零元素
    {
        printf("请用三元组形式输入矩阵的元素(行 列 非零元素):");
        scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
    }
    for(i=1,k=1;i<=M.hs;i++)
    {
        M.rpos[i]=k;
        while(M.data[k].i<=i && k<=M.fls)
            k++;         
        }
}
 
void Print_SMatrix(TSMatrix M)        //矩阵输出
{
    int r,c,n;
    Matrix p;
    p=&M;
    for(r=1,n=1;r<=p->hs;r++)      //控制行输出
    {
        for(c=1;c<=p->ls;c++)      //控制列输出
        {
            if(p->data[n].i==r && p->data[n].j==c)
            {
                printf("%5d",p->data[n].e);     //输出非零元素
                n++;
            }
            else  
                printf("%5d",0);
        }
        printf("\n");
    }
    printf("\n");
}
 
void Qiuhe(TSMatrix A,TSMatrix B,TSMatrix &C,int n)
{
    int a,b,temp,l;
    C.hs=A.hs;
    C.ls=A.ls;
    a=b=l=1;
    while(a<=A.fls && b<=B.fls)     //判断数组的长度小于非零元的个数
    {
        //判断AB矩阵行数列数是否相等
        if(A.data[a].i==B.data[b].i)  
            {
                if(A.data[a].j<B.data[b].j)
                    C.data[l++]=A.data[a++];
                else if(A.data[a].j>B.data[b].j)
                {
                    C.data[l]=B.data[b];
                      C.data[l++].e=n*B.data[b++].e;
                }
                else     //如果AB的行数列数相等则求AB矩阵中对应非零预算的和
                {
                    temp=A.data[a].e+n*B.data[b].e;
                     if(temp)     //如果temp为非零则
                    {
                        C.data[l]=A.data[a]; //把矩阵A的长度赋给C
                        C.data[l].e=temp;    //把和赋给矩阵C
                        l++;                 //数组的长度加1
                    }
                    a++;b++;
                }
        }
        else if(A.data[a].i<B.data[b].i)
                C.data[l++]=A.data[a++];
        else   
        {
            C.data[l]=B.data[b];
            C.data[l++].e=n*B.data[b++].e;
        }
    }

    while(a<=A.fls)
        C.data[l++]=A.data[a++];
    while(b<=B.fls)
    {
        C.data[l]=B.data[b];
        C.data[l++].e=n*B.data[b++].e;
    }
    C.fls=l-1;
}

int Chengji(TSMatrix A,TSMatrix B,TSMatrix &Q)
{
    int arow,brow,ccol,tp,p,q,t;
    int ctemp[MAXRC];
    if(A.ls!=B.hs)    //判断A的列数是否等于B的行数   
        return 0;
    Q.hs=A.hs;
    Q.ls=B.ls;
    Q.fls=0;
    if(A.fls*B.fls)
    {
         for(arow=1;arow<=A.hs;arow++)
         {
            for(ccol=1;ccol<=Q.ls;ccol++)
                ctemp[ccol]=0;
            Q.rpos[arow]=Q.fls+1;
            if(arow<A.hs)   
                tp=A.rpos[arow+1];
            else
                tp=A.fls+1;
            for(p=A.rpos[arow];p<tp;p++)
            {
                brow=A.data[p].j;
                if(brow<B.hs)   
                    t=B.rpos[brow+1];
                else   
                    t=B.fls+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.ls;ccol++)
            {
                if(ctemp[ccol]){
                    if(++Q.fls>MAXSIZE)    return 0;
                        Q.data[Q.fls].i=arow;
                    Q.data[Q.fls].j=ccol;
                    Q.data[Q.fls].e=ctemp[ccol];
                }
            }
        }
    }
    return 1;
}
 
void Zhuanzhi(TSMatrix *a,TSMatrix *b)
{
    int q,col,p;
    b->hs=a->ls;
    b->ls=a->hs;
    b->fls=a->fls;
    if(b->fls)
    {
        q=1;
        for(col=1;col<=a->ls;col++)
            for(p=1;p<=a->fls;p++)
                if(a->data[p].j==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;
                    ++q;
                }
    }
}
void Destory_SMatrix(TSMatrix &M)     //退出程序
{
    M.hs=M.ls=M.fls=0;
}

void main()      
{
    TSMatrix A,B,C;                   //定义三个稀疏矩阵                     
    TSMatrix *p=&A,*q=&B;             //将矩阵AB的地址赋给指针p q
    int flag,n;                       //定义选项flag
    while(1)
    {
        system("cls");
        printf("\n\n\n");
        printf("\t***********************************************\n");
        printf("\t****************  稀疏矩阵运算器 **************\n");
        printf("\t***********************************************\n");
        printf("\t************** 1、稀疏矩阵的加法 **************\n");
        printf("\t************** 2、稀疏矩阵的减法 **************\n");
        printf("\t************** 3、稀疏矩阵的乘法 **************\n");
        printf("\t************** 4、稀疏矩阵的转置 **************\n");
        printf("\t************** 5、退出           **************\n");
        printf("\t***********************************************\n");
        printf("输入要进行的项目的编号:");
        scanf("%d",&flag);
        if(flag==5)    break;
         Creat(A);  
        printf("矩阵A:\n");
        Print_SMatrix(A);     //输出矩阵A
        switch(flag)
        {
            case 1:   
                Creat(B);n=1;
            printf("矩阵B:\n");
            Print_SMatrix(B);
            if(A.hs==B.hs  && A.ls==B.ls)
            {
            printf("A+B:\n");
            Qiuhe(A,B,C,n);
            Print_SMatrix(C);
            }
            else
                printf("错误!行列不一致\n");
            break;
            case 2:
                Creat(B);n=-1;
            printf("矩阵B:\n");
            Print_SMatrix(B);
            if(A.hs==B.hs  && A.ls==B.ls)
            {
            printf("A-B:\n");
            Qiuhe(A,B,C,n);
            Print_SMatrix(C);
            }
            else  
                printf("错误!行列不一致\n");
            break;
             case 3:
                Creat(B);
            printf("矩阵B:\n");
            Print_SMatrix(B);
            printf("A*B:\n");
            n=Chengji(A,B,C);
            case 4:
                printf("转置结果:\n");
            Zhuanzhi(p,q);
            Print_SMatrix(B);
            break;
            if(!n)
                printf("错误!行列不匹配\n");
            else Print_SMatrix(C);
                break;
            default:printf("输入错误!\n");
        }
        Destory_SMatrix(A);
        Destory_SMatrix(B);
        Destory_SMatrix(C);
        getchar();
        getchar();
    }
    printf("\n\t\t\t   ***程序已经退出***\n");
    getchar();
}