1. 什么是十字链表？

十字链表（Orthogonal List）是一种用于存储稀疏矩阵的数据结构。它通过将稀疏矩阵的非零元素组织成一个十字交叉的链表，从而高效地表示矩阵的行和列关系。与传统的二维数组存储方式相比，十字链表可以显著节省存储空间，并方便进行矩阵的转置、加法、乘法等运算。

2. 十字链表的结构

十字链表中的每个非零元素用一个结点表示，每个结点包含五个域：

• row：元素所在的行号。
• col：元素所在的列号。
• value：元素的值。
• right：指向同一行中下一个非零元素的指针。
• down：指向同一列中下一个非零元素的指针。

此外，还需要两个一维数组：

• 行头指针数组（rhead）：指向每一行的第一个非零元素结点。
• 列头指针数组（chead）：指向每一列的第一个非零元素结点。

3. 十字链表的优点

• 节省空间：只存储非零元素，适合稀疏矩阵。
• 操作灵活：插入、删除、修改非零元素相对方便。
• 便于矩阵运算：沿行或列遍历效率高，易于实现转置、加法等。

4. 十字链表的C语言实现

以下是一个简单的十字链表创建与遍历的C语言示例：

#include <stdio.h> #include <stdlib.h> typedef struct OLNode { int row, col; int value; struct OLNode *right, *down; } OLNode, *OLink; typedef struct { OLink *rhead, *chead; int rows, cols, nums; // 行数、列数、非零元个数 } CrossList; // 初始化十字链表 void InitCrossList(CrossList *M, int rows, int cols) { M->rows = rows; M->cols = cols; M->nums = 0; M->rhead = (OLink *)malloc((rows + 1) * sizeof(OLink)); M->chead = (OLink *)malloc((cols + 1) * sizeof(OLink)); for (int i = 1; i <= rows; i++) M->rhead[i] = NULL; for (int j = 1; j <= cols; j++) M->chead[j] = NULL; } // 插入一个非零元素 int InsertNode(CrossList *M, int row, int col, int value) { if (row < 1 || row > M->rows || col < 1 || col > M->cols) return 0; OLNode *p = (OLNode *)malloc(sizeof(OLNode)); p->row = row; p->col = col; p->value = value; p->right = NULL; p->down = NULL; // 处理行插入 OLNode *q = M->rhead[row]; if (q == NULL || col < q->col) { p->right = q; M->rhead[row] = p; } else { while (q->right && q->right->col < col) q = q->right; p->right = q->right; q->right = p; } // 处理列插入 q = M->chead[col]; if (q == NULL || row < q->row) { p->down = q; M->chead[col] = p; } else { while (q->down && q->down->row < row) q = q->down; p->down = q->down; q->down = p; } M->nums++; return 1; } // 打印十字链表（按行） void PrintCrossList(CrossList *M) { for (int i = 1; i <= M->rows; i++) { OLNode *p = M->rhead[i]; while (p) { printf("(%d, %d, %d) ", p->row, p->col, p->value); p = p->right; } printf("\n"); } } int main() { CrossList M; InitCrossList(&M, 5, 5); InsertNode(&M, 1, 2, 3); InsertNode(&M, 2, 3, 5); InsertNode(&M, 4, 1, 7); InsertNode(&M, 4, 4, 9); printf("十字链表内容（按行输出）：\n"); PrintCrossList(&M); return 0; }

5. 应用场景

• 稀疏矩阵存储：科学计算、图形学中大量零元素的矩阵。
• 图论：邻接矩阵的稀疏表示。
• 数据库：某些稀疏关系表的存储优化。
• 网络分析：表示稀疏的连接关系。

6. 总结

十字链表是处理稀疏矩阵的高效数据结构，它通过链式结构将行和列关联起来，在保证操作效率的同时大幅节约了存储空间。掌握十字链表的原理和实现，有助于在涉及稀疏数据的算法设计中做出更优的选择。