hosteons中文网

前面介绍了图的邻接表存储法，本节继续讲解图的另一种链式存储结构——十字链表法。

与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。

十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。

其中，建立个各个链表中用于存储顶点的首元节点结构如图 1 所示：

图 1 十字链表中首元节点结构示意图