十字链表

十字链表（英语：Orthogonal linked list）是计算机科学中的一种高级数据结构，在Linux内核中应用广泛。具体说，一个二维十字链表是链表的元素同时链接左右水平邻结点与上下垂直邻结点。这一方法可以推广到更高维以存储稀疏矩阵、图等数据集合。^[1]

简介

典型用于稀疏矩阵存储时，矩阵每个元素为以下五元组：

typedef struct OLNode {    
     int  LineNumber, ColumneNumber;          //行号与列号     
     ElemType value;        //值     
     struct OLNode *right, *down;  //同行、同列下一个元素的指针     
}OLNode, *OList;

分别创建两个指针数组，分别存放每行或每列的第一个结点的地址。

参见

• 链表
• 舞蹈链