十字鍊表

十字鍊表（英語：Orthogonal linked list）是計算機科學中的一種高級數據結構，在Linux內核中應用廣泛。具體說，一個二維十字鍊表是鍊表的元素同時鏈接左右水平鄰結點與上下垂直鄰結點。這一方法可以推廣到更高維以存儲稀疏矩陣、圖等數據集合。^[1]

簡介

典型用於稀疏矩陣存儲時，矩陣每個元素為以下五元組：

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

分別創建兩個指針數組，分別存放每行或每列的第一個結點的地址。

參見

• 鍊表
• 舞蹈鏈