// 稀疏矩阵的十字链表存储与输出。

稀疏矩阵的十字链表存储方式是一种常用的存储方式，可以有效地节省存储空间。下面是一个简单的例子，演示如何使用十字链表存储稀疏矩阵，并输出矩阵。

假设有一个 $4 \times 5$ 的稀疏矩阵，其中只有 $6$ 个元素不为 $0$，矩阵如下：

$$
\begin{bmatrix}
1 & 0 & 0 & 0 & 2 \\
0 & 3 & 0 & 0 & 0 \\
0 & 0 & 0 & 4 & 0 \\
5 & 0 & 0 & 0 & 6 \\
\end{bmatrix}
$$

使用十字链表存储该矩阵，可以定义如下的节点结构体：

typedef struct OLNode {
    int i, j; // 行列下标
    int e; // 元素值
    struct OLNode *right, *down; // 向右和向下的指针
} OLNode, *OLink;

其中，`i` 和 `j` 分别表示节点所在的行和列，`e` 表示节点的元素值，`right` 和 `down` 分别表示向右和向下的指针。

使用头节点数组存储十字链表的头节点，定义如下：

typedef struct {
    OLink *row_head, *col_head; // 行和列的头节点数组
    int m, n, k; // 矩阵的行数、列数和非零元素个数
} CrossList;

其中，`row_head` 和 `col_head` 分别表示行和列的头节点数组，`m` 和 `n` 分别表示矩阵的行数和列数，`k` 表示非零元素的个数。

下面是使用十字链表存储稀疏矩阵的代码：

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

typedef struct OLNode {
    int i, j; // 行列下标
    int e; // 元素值
    struct OLNode *right, *down; // 向右和向下的指针
} OLNode, *OLink;

typedef struct {
    OLink *row_head, *col_head; // 行和列的头节点数组
    int m, n, k; // 矩阵的行数、列数和非零元素个数
} CrossList;

void CreateSMatrix(CrossList *M)
{
    int i, j, e;
    printf("请输入矩阵的行数、列数和非零元素个数：");
    scanf("%d%d%d", &M->m, &M->n, &M->k);
    M->row_head = (OLink*)malloc((M->m + 1) * sizeof(OLink));
    M->col_head = (OLink*)malloc((M->n + 1) * sizeof(OLink));
    for (i = 1; i <= M->m; i++) {
        M->row_head[i] = NULL;
    }
    for (j = 1; j <= M->n; j++) {
        M->col_head[j] = NULL;
    }
    printf("请输入矩阵的非零元素：\n");
    for (i = 1; i <= M->k; i++) {
        printf("请输入第%d个非零元素的行、列和值：", i);
        scanf("%d%d%d", &i, &j, &e);
        OLink p = (OLink)malloc(sizeof(OLNode));
        p->i = i;
        p->j = j;
        p->e = e;
        p->right = NULL;
        p->down = NULL;
        if (M->row_head[i] == NULL || M->row_head[i]->j > j) {
            p->right = M->row_head[i];
            M->row_head[i] = p;
        } else {
            OLink q = M->row_head[i];
            while (q->right != NULL && q->right->j < j) {
                q = q->right;
            }
            p->right = q->right;
            q->right = p;
        }
        if (M->col_head[j] == NULL || M->col_head[j]->i > i) {
            p->down = M->col_head[j];
            M->col_head[j] = p;
        } else {
            OLink q = M->col_head[j];
            while (q->down != NULL && q->down->i < i) {
                q = q->down;
            }
            p->down = q->down;
            q->down = p;
        }
    }
}

void PrintSMatrix(CrossList M)
{
    int i, j;
    OLink p;
    printf("稀疏矩阵的行数、列数和非零元素个数为：%d %d %d\n", M.m, M.n, M.k);
    printf("稀疏矩阵的三元组表如下：\n");
    printf("行 列 值\n");
    for (i = 1; i <= M.m; i++) {
        p = M.row_head[i];
        for (j = 1; j <= M.n; j++) {
            if (p != NULL && p->j == j) {
                printf("%2d %2d %2d\n", p->i, p->j, p->e);
                p = p->right;
            } else {
                printf("%2d %2d %2d\n", i, j, 0);
            }
        }
    }
}

int main()
{
    CrossList M;
    CreateSMatrix(&M);
    PrintSMatrix(M);
    return 0;
}

运行程序，输入矩阵的行数、列数和非零元素个数，以及每个非零元素的行、列和值，即可输出稀疏矩阵的三元组表。