C语言十字链表详解（高效存储稀疏矩阵与图结构的利器）

为什么使用十字链表？

对于一个大型但大部分元素为零的矩阵（即稀疏矩阵），如果用二维数组存储，会浪费大量内存。而十字链表只存储非零元素，并通过指针连接，大大节省空间。此外，在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 **row_head;     // 行头指针数组    OLNode **col_head;     // 列头指针数组    int rows, cols, nums;  // 矩阵行数、列数、非零元素个数} CrossList;

创建十字链表的基本步骤

1. 初始化行头和列头指针数组，全部置为NULL。
2. 遍历原始矩阵，遇到非零元素就创建新节点。
3. 将新节点插入到对应行和列的链表中（按列号/行号顺序插入）。

下面是一个简化版的插入函数示例：

void insert_node(CrossList *M, int row, int col, int value) {    OLNode *new_node = (OLNode*)malloc(sizeof(OLNode));    new_node->row = row;    new_node->col = col;    new_node->value = value;    new_node->right = NULL;    new_node->down = NULL;    // 插入到行链表中    OLNode *p = M->row_head[row];    while (p->right && p->right->col < col) {        p = p->right;    }    new_node->right = p->right;    p->right = new_node;    // 插入到列链表中    OLNode *q = M->col_head[col];    while (q->down && q->down->row < row) {        q = q->down;    }    new_node->down = q->down;    q->down = new_node;    M->nums++;}

应用场景与优势

十字链表不仅适用于稀疏矩阵存储，在C语言图结构中也大有用武之地。例如，在有向图中，每个顶点可以看作矩阵的一行一列，边的存在对应非零元素。通过十字链表，我们可以快速找到某个顶点的所有出边（通过行链表）和入边（通过列链表）。

相比邻接矩阵，它节省空间；相比邻接表，它能同时高效访问入度和出度——这正是十字链表实现的独特优势。

总结

通过本文，你应该已经理解了C语言十字链表的基本原理、结构设计和简单实现。虽然初看复杂，但只要抓住“每个节点同时属于一行一列”这一核心思想，就能轻松掌握。建议你动手编写完整代码，尝试构建一个3×3的稀疏矩阵，亲自体验十字链表的魅力！

掌握数据结构，是成为优秀C语言程序员的关键一步。