C语言十字链表详解（稀疏矩阵的高效存储与操作指南）

如上图所示，每个非零元素用一个节点表示，节点包含以下信息：

• 行下标（row）
• 列下标（col）
• 元素值（value）
• 指向同一行下一个非零元素的指针（right）
• 指向同一列下一个非零元素的指针（down）

十字链表的节点定义

首先，我们需要定义十字链表的节点结构。在C语言中，可以这样写：

typedef struct OLNode {    int row, col;          // 行号和列号    int value;             // 非零元素的值    struct OLNode *right;  // 指向同行的下一个非零元素    struct OLNode *down;   // 指向同列的下一个非零元素} OLNode;typedef struct {    OLNode **rowHead;      // 行头指针数组    OLNode **colHead;      // 列头指针数组    int rows, cols, nums;  // 矩阵行数、列数、非零元素个数} CrossList;

创建十字链表

接下来，我们实现一个函数来初始化十字链表。假设我们要创建一个 m 行 n 列的稀疏矩阵：

#include <stdio.h>#include <stdlib.h>// 初始化十字链表int CreateCrossList(CrossList *M, int m, int n) {    M->rows = m;    M->cols = n;    M->nums = 0;    // 分配行头和列头指针数组    M->rowHead = (OLNode**)malloc(m * sizeof(OLNode*));    M->colHead = (OLNode**)malloc(n * sizeof(OLNode*));    if (!M->rowHead || !M->colHead) return 0;    // 初始化所有头指针为 NULL    for (int i = 0; i < m; i++) M->rowHead[i] = NULL;    for (int j = 0; j < n; j++) M->colHead[j] = NULL;    return 1;}

插入非零元素

当我们读取到一个非零元素 (i, j, value) 时，需要将其插入到对应的行链表和列链表中。注意要保持链表有序（通常按列号或行号递增）：

// 插入一个非零元素int InsertElement(CrossList *M, int i, int j, int value) {    if (i < 0 || i >= M->rows || j < 0 || j >= M->cols) return 0;    OLNode *newNode = (OLNode*)malloc(sizeof(OLNode));    newNode->row = i;    newNode->col = j;    newNode->value = value;    // 插入到行链表（按列号递增）    OLNode *p = M->rowHead[i];    OLNode *prev = NULL;    while (p && p->col < j) {        prev = p;        p = p->right;    }    if (prev == NULL) {        newNode->right = M->rowHead[i];        M->rowHead[i] = newNode;    } else {        newNode->right = p;        prev->right = newNode;    }    // 插入到列链表（按行号递增）    p = M->colHead[j];    prev = NULL;    while (p && p->row < i) {        prev = p;        p = p->down;    }    if (prev == NULL) {        newNode->down = M->colHead[j];        M->colHead[j] = newNode;    } else {        newNode->down = p;        prev->down = newNode;    }    M->nums++;    return 1;}

打印十字链表

为了验证我们的实现是否正确，可以编写一个打印函数：

void PrintCrossList(CrossList *M) {    printf("稀疏矩阵 (%d x %d)，非零元素个数：%d\n", M->rows, M->cols, M->nums);    for (int i = 0; i < M->rows; i++) {        OLNode *p = M->rowHead[i];        while (p) {            printf("(%d, %d) = %d\n", p->row, p->col, p->value);            p = p->right;        }    }}

完整示例与使用

下面是一个完整的测试程序：

int main() {    CrossList M;    CreateCrossList(&M, 3, 4);  // 创建 3x4 的稀疏矩阵    // 插入非零元素    InsertElement(&M, 0, 1, 5);    InsertElement(&M, 1, 2, 8);    InsertElement(&M, 2, 0, 3);    InsertElement(&M, 2, 3, 6);    PrintCrossList(&M);    return 0;}

总结

通过本文，你已经掌握了C语言十字链表的基本原理和实现方法。这种结构特别适用于稀疏矩阵存储，能显著减少内存占用，并支持高效的行列遍历。无论你是学习C语言数据结构的学生，还是需要优化矩阵运算的开发者，掌握十字链表实现都将为你带来巨大优势。

希望这篇教程对你有帮助！动手试试吧，实践是掌握数据结构的最佳方式。