稀疏矩阵及其实现

/*--------稀疏矩阵的三元组顺序表存储表示----------*/
typedef int ElemType;

#define MAXSIZE 12500       // 假设非零元个数的最大数值为12500
typedef struct {
    int i, j;               // 该非零元的行下标和列下标
    ElemType e;
}Triple;

typedef struct {
    Triple data[MAXSIZE + 1];
    int mu, nu, tu;         // 矩阵的行数、列数、和非零元个数
}TSMatrix;

/*--------------数据结构定义结束---------------*/

/*-----------------基本操作-------------------*/

/*创建稀疏矩阵M*/
Status CreateSMatrix(TSMatrix *M){  
    if (!M)return ERROR;        //若空间分配失败，则返回ERROR

    // 让矩阵初始行列数都为0，非零元个数也为0
    M->mu = 0;
    M->nu = 0;
    M->tu = 0;
    return OK;
}

/*销毁稀疏矩阵*/
Status DestroySMatrix(TSMatrix *M){
    free(M);

    if (M)return ERROR;         //若M仍存在，则销毁失败，返回ERROR
    return OK;
}
/*给稀疏矩阵赋值*/
Status Assign(TSMatrix *M){
    int p, q, r, t = 0;

    for (p = 0; p < M->mu; p++){
        for (q = 0; q < M->nu; q++){
            printf_s("[%d][%d] = ", p + 1, q + 1);
            scanf_s("%d", &r);

            if (r != 0){
                t++;
                M->data[t].i = p + 1;
                M->data[t].j = q + 1;
                M->data[t].e = r;
            }
        }
    }

    M->tu = t;
    return OK;
}

/*输出稀疏矩阵*/
void PrintSMatrix(TSMatrix M){
    int m;
    for (m = 1; m <= M.tu; m++){
        printf_s("======[%d][%d] = %d\n", M.data[m].i, M.data[m].j, M.data[m].e);
    }
}

/*由稀疏矩阵M复制得到T*/
Status CopySMatrix(TSMatrix M, TSMatrix *T){
    CreateSMatrix(T);

    if (!T)return ERROR;

    //将M的行列数以及非零元的个数赋给T
    T->mu = M.mu;
    T->nu = M.nu;
    T->tu = M.tu;

    //将M的data数组赋给T
    int m;
    for (m = 1; m < M.tu; m++){
        T->data[m].i = M.data[m].i;
        T->data[m].j = M.data[m].j;
        T->data[m].e = M.data[m].e;
    }

    return OK;
}

/*若稀疏矩阵M与N的行数和列数对应相等，求稀疏矩阵的和Q = M + N*/
Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q){
    if (M.mu != N.mu || M.nu != N.nu)return ERROR;      //若行数和列数不对应相等，则返回ERROR

    CreateSMatrix(Q);

    //给Q设置行数和列数
    Q->mu = M.mu;
    Q->nu = M.nu;

    int m, n, q;            //设立m,n,q来计算矩阵元素个数
    m = 1;
    n = 1;
    q = 0;

    while (m < M.tu && n < N.tu){
        if (M.data[m].i == N.data[n].i){
            if (M.data[m].j == N.data[n].j){
                q++;
                Q->data[q].i = M.data[m].i;                 //Q.data[q]的行下标为M.data[m]的行下表
                Q->data[q].j = M.data[m].j;                 //Q.data[q]的列下标为M.data[m]的列下表
                Q->data[q].e = M.data[m].e + N.data[n].e;   //Q.data[q]的数值为两个矩阵对应位置的数值之和

                m++;
                n++;
            }
            else if (M.data[m].j < N.data[n].j){
                q++;
                Q->data[q].i = M.data[m].i;
                Q->data[q].j = M.data[m].j;
                Q->data[q].e = M.data[m].e;

                m++;
            }
            else if (M.data[m].j > N.data[n].j){
                q++;
                Q->data[q].i = N.data[n].i;
                Q->data[q].j = N.data[n].j;
                Q->data[q].e = N.data[n].e;

                n++;
            }
        }
        else if (M.data[m].i < N.data[n].i){
            q++;
            Q->data[q].i = M.data[m].i;
            Q->data[q].j = M.data[m].j;
            Q->data[q].e = M.data[m].e;

            m++;
        }
        else if (M.data[m].i > N.data[n].i){
            q++;
            Q->data[q].i = M.data[m].i;
            Q->data[q].j = M.data[m].j;
            Q->data[q].e = M.data[m].e;

            m++;
        }

    }

    //当有矩阵非零元用完了之后，处理剩下的一个矩阵中的剩余元素
    while (m <= M.tu){
        q++;
        Q->data[q].i = M.data[m].i;
        Q->data[q].j = M.data[m].j;
        Q->data[q].e = M.data[m].e;

        m++;
    }

    while (n <= N.tu){
        q++;
        Q->data[q].i = N.data[n].i;
        Q->data[q].j = N.data[n].j;
        Q->data[q].e = N.data[n].e;

        n++;
    }

    Q->tu = q;
    return OK;
}

/*若稀疏矩阵M与N的行数和列数对应相等，求稀疏矩阵的差 Q = M - N*/
Status SubSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q){
    //这个方法实际上就是对AddSMatrix(M, -N, Q)的实现
    return OK;
}