如何在C语言中创建和初始化十字链表？

在C语言中，创建和初始化十字链表（Compressed Row Storage, CRS 或 CSR，也称为三元组存储）通常涉及到三个数组：`values`用于存储非零元素，`rowPtr`用于记录每一行的非零元素的开始位置，以及`colPtr`记录列索引的跳变。

以下是基本的步骤：

1. 定义结构体 `SparseNode` 来表示链表节点，包含元素值、行和列索引：

typedef struct {
    int value;
    int row;
    int col;
    struct SparseNode* next;
} SparseNode;

2. 创建 `values`, `rowPtr` 和 `colPtr` 数组。假设有一个m x n的矩阵，你需要为每个非零元素分配一个 `SparseNode` 结构，并存储其值、行号和列号到 `values` 数组，同时更新对应的 `rowPtr` 和 `colPtr`：

SparseNode** values = malloc(sizeof(SparseNode*) * m); // 分配足够的空间存储每个行的所有节点
int* rowPtr = malloc(sizeof(int) * (m+1));  // 行结束的索引数组，最后一项存储最后一个非零元素的行号
int* colPtr = malloc(sizeof(int) * (n+1));  // 列索引的跳变位置

// 初始化列指针
for (int j = 0; j <= n; ++j)
    colPtr[j] = 0;

// 遍历矩阵，添加非零元素
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        if (matrix[i][j]) { // 如果元素不为0
            SparseNode* newNode = malloc(sizeof(SparseNode));
            newNode->value = matrix[i][j];
            newNode->row = i;
            newNode->col = j;
            newNode->next = values[i]; // 将当前行的节点指针指向新节点
            values[i] = newNode;      // 更新当前行的节点指针
            colPtr[j+1]++;           // 记录当前列的元素数量
        }
    }
    rowPtr[i+1] = colPtr[j];   // 存储行结束的位置
}

这将创建一个有效的十字链表表示给定的稀疏矩阵。