稀疏矩阵的三元组表示法及转置

#include <stdio.h>

// 4.5.2 稀疏矩阵的顺序存储：三元组表示法
typedef int dataType;

typedef struct
{
    dataType data[100][100]; // 存放稀疏矩阵
    int m, n; // 稀疏矩阵的行、列
}matrix;

typedef dataType spMatrix[100][3]; // 存放稀疏矩阵的三元组

// 1.稀疏矩阵转换成三元组存储
void compressMatrix(matrix A,spMatrix B)
{
    int k = 1;
    for (int i = 0; i < A.m; ++i)
    {
        for (int j = 0; j < A.n; ++j)
        {
            if(A.data[i][j] != 0)
            {
                B[k][0] = i;
                B[k][1] = j;
                B[k][2] = A.data[i][j];
                k++;
            }
        }
    }
    B[0][0] = A.m;
    B[0][1] = A.n;
    B[0][2] = k-1;
}

// 三元组表示的稀疏矩阵的转置
void transSpMatrix(spMatrix B,spMatrix C)
{
    // 1.首先统计三元组B表示的原矩阵每列非零元素个数；
    // 2.计算出转置后的矩阵的每行元素的三元组表示法的起始位置
    // 3.交换行、列号并把元素放到新的三元组的最终位置上
    int x[100], y[100];
    int m = B[0][0],n = B[0][1], t = B[0][2], j;
    C[0][0] = n,C[0][1] = m,C[0][2] = t;
    for (int i = 0; i < n; ++i) x[i] = 0; // 初始化数组x
    for (int i = 1; i <= t; ++i) // 1.步骤1
        x[B[i][1]] += 1;
    y[0] = 1; // 表示第一行起始位置是1
    for (int i = 1; i < n; ++i) // 2.步骤2
        y[i] = y[i-1] + x[i-1];
    for (int i = 1; i <= t; ++i) // 3.步骤3
    {
        j = y[B[i][1]]; // j为三元组最终位置
        C[j][0] = B[i][1];
        C[j][1] = B[i][0];
        C[j][2] = B[i][2];
        y[B[i][1]] = j+1; // 同行的下一个元素的最终位置要递增
    }
}

int main()
{
    matrix A,D;
    spMatrix B,C;
    B[0][2] = 0;
    A.m = 7,A.n = 6; // 声明7行6列矩阵A
    D.m = 6,D.n = 7; // 转置后的矩阵D
    for (int i = 0; i < A.m; ++i) // 初始化矩阵A
    {
        for (int j = 0; j < A.n; ++j)
            A.data[i][j] = 0;
    }
    for (int i = 0; i < D.m; ++i) // 初始化矩阵D
    {
        for (int j = 0; j < D.n; ++j)
            A.data[i][j] = 0;
    }
    A.data[0][2] = -5,A.data[0][4] = 1;
    A.data[1][3] = 2;
    A.data[2][0] = 3;
    A.data[4][0] = 12;
    A.data[5][5] = 4;
    A.data[6][2] = 21;
    printf("矩阵A如下所示：\n");
    for (int i = 0; i < A.m; ++i)
    {
        for (int j = 0; j < A.n; ++j)
            printf("%d\t",A.data[i][j]);
        printf("\n");
    }
    compressMatrix(A,B);
    printf("稀疏矩阵有%d行%d列\n",B[0][0],B[0][1]);
    printf("第%d行第%d列的值是%d\n",B[1][0]+1,B[1][1]+1,B[1][2]);
    printf("矩阵A的三元组表示法如下所示：\n");
    for (int i = 0; i <= B[0][2]; ++i)
        printf("%d\t%d\t%d\t%d\n",i,B[i][0],B[i][1],B[i][2]);
    printf("矩阵A的转置的三元组表示法如下所示：\n");
    transSpMatrix(B,C);
    for (int i = 0; i <= C[0][2]; ++i)
    {
        D.data[C[i][0]][C[i][1]] = C[i][2]; // 三元组转为普通矩阵
        printf("%d\t%d\t%d\t%d\n",i,C[i][0],C[i][1],C[i][2]);
    }
    printf("矩阵A的转置矩阵D如下所示：\n");
    for (int i = 0; i < D.m; ++i)
    {
        for (int j = 0; j < D.n; ++j)
            printf("%d\t",D.data[i][j]);
        printf("\n");
    }
    return 0;
}