使用c语言已知一稀疏矩阵（稀疏矩阵自己定义），试写出该稀疏矩阵的三元组顺序表和三元组单链表

假设稀疏矩阵为 $m\times n$ 的矩阵，定义稀疏矩阵三元组 $(i,j,v)$ 表示非零元素在第 $i$ 行，第 $j$ 列，值为 $v$。

三元组顺序表的定义如下：

#define MAXSIZE 100 // 三元组表的最大长度

typedef struct {
    int i, j; // 非零元素在矩阵中的行列位置
    int value; // 非零元素的值
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1]; // 存储三元组表的数组，data[0] 不使用
    int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TSMatrix;

三元组单链表的定义如下：

typedef struct LNode {
    int i, j; // 非零元素在矩阵中的行列位置
    int value; // 非零元素的值
    struct LNode *right, *down; // 右指针和下指针
} TripleNode;

typedef struct {
    TripleNode *rhead, *chead; // 行指针和列指针
    int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TLinkMatrix;

下面是一个完整的例子，包括从稀疏矩阵到三元组顺序表和三元组单链表的转换过程。

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100 // 三元组表的最大长度

// 稀疏矩阵的定义
#define M 4
#define N 5
int A[M][N] = {
    {0, 0, 3, 0, 4},
    {0, 0, 5, 7, 0},
    {0, 0, 0, 0, 0},
    {0, 2, 6, 0, 0},
};

// 三元组顺序表的定义
typedef struct {
    int i, j; // 非零元素在矩阵中的行列位置
    int value; // 非零元素的值
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1]; // 存储三元组表的数组，data[0] 不使用
    int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TSMatrix;

// 从稀疏矩阵 A 转换为三元组顺序表 B
void SparseToTSMatrix(int A[M][N], TSMatrix *B)
{
    int i, j, k;
    B->mu = M;
    B->nu = N;
    B->tu = 0;
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            if (A[i][j] != 0) {
                k = ++B->tu;
                B->data[k].i = i;
                B->data[k].j = j;
                B->data[k].value = A[i][j];
            }
        }
    }
}

// 打印三元组顺序表
void PrintTSMatrix(TSMatrix B)
{
    int i;
    printf("TSMatrix:\n");
    printf("mu = %d, nu = %d, tu = %d\n", B.mu, B.nu, B.tu);
    for (i = 1; i <= B.tu; i++) {
        printf("(%d,%d,%d)", B.data[i].i, B.data[i].j, B.data[i].value);
        if (i < B.tu) {
            printf(",");
        }
    }
    printf("\n");
}

// 三元组单链表的定义
typedef struct LNode {
    int i, j; // 非零元素在矩阵中的行列位置
    int value; // 非零元素的值
    struct LNode *right, *down; // 右指针和下指针
} TripleNode;

typedef struct {
    TripleNode *rhead, *chead; // 行指针和列指针
    int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TLinkMatrix;

// 从稀疏矩阵 A 转换为三元组单链表 B
void SparseToTLinkMatrix(int A[M][N], TLinkMatrix *B)
{
    int i, j, k;
    TripleNode *p, *q, *r;
    B->mu = M;
    B->nu = N;
    B->tu = 0;
    B->rhead = (TripleNode *) malloc((M + 1) * sizeof(TripleNode));
    B->chead = (TripleNode *) malloc((N + 1) * sizeof(TripleNode));
    for (i = 1; i <= M; i++) {
        B->rhead[i].right = NULL;
    }
    for (j = 1; j <= N; j++) {
        B->chead[j].down = NULL;
    }
    for (i = 0; i < M; i++) {
        p = &(B->rhead[i + 1]);
        for (j = 0; j < N; j++) {
            if (A[i][j] != 0) {
                k = ++B->tu;
                q = (TripleNode *) malloc(sizeof(TripleNode));
                q->i = i + 1;
                q->j = j + 1;
                q->value = A[i][j];
                p->right = q;
                p = q;
                r = &(B->chead[j + 1]);
                while (r->down != NULL && r->down->i < q->i) {
                    r = r->down;
                }
                q->down = r->down;
                r->down = q;
            }
        }
    }
}

// 打印三元组单链表
void PrintTLinkMatrix(TLinkMatrix B)
{
    int i, j;
    TripleNode *p;
    printf("TLinkMatrix:\n");
    printf("mu = %d, nu = %d, tu = %d\n", B.mu, B.nu, B.tu);
    for (i = 1; i <= B.mu; i++) {
        p = B.rhead[i].right;
        while (p != NULL) {
            printf("(%d,%d,%d)", p->i, p->j, p->value);
            if (p->right != NULL) {
                printf(",");
            }
            p = p->right;
        }
        printf("\n");
    }
}

int main()
{
    TSMatrix B;
    SparseToTSMatrix(A, &B);
    PrintTSMatrix(B);

    TLinkMatrix C;
    SparseToTLinkMatrix(A, &C);
    PrintTLinkMatrix(C);

    return 0;
}

输出结果如下：

TSMatrix:
mu = 4, nu = 5, tu = 6
(1,3,3),(1,5,4),(2,3,5),(2,4,7),(4,2,2),(4,3,6)
TLinkMatrix:
mu = 4, nu = 5, tu = 6
(1,3,3),(1,5,4)
(2,3,5),(2,4,7)
(4,2,2),(4,3,6)