十字鍊表

十字鍊表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鍊表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

十字鍊表的構成

用鍊表模擬矩陣的行（或者列，這可以根據個人喜好來定），然後，再構造代表列（或者是行）的鍊表，將每一行中的元素節點插入到對應的列中去。十字鍊表的邏輯結構就像是一個圍棋盤（沒見過，你就想一下蒼蠅拍，這個總見過吧!），而非零元就好像是在棋盤上放的棋子，總共占的空間就是，確定那些線的表頭節點和那些棋子代表的非零元節點。最後，我們用一個指針指向這個棋盤，這個指針就代表了這個稀疏矩陣。

十字鍊表

十字鍊表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鍊表。在十字鍊表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。

十字鍊表之於有向圖，類似於鄰接表之於無向圖。

也可以理解為 將行的單鍊表和列的單鍊表結合起來存儲稀疏矩陣稱為十字鍊表， 每個節點表示一個非零元素。

舉例