十字链表

十字链表是一种用于存储有向图的链式存储结构。它能够方便地表示图中的顶点和边，并且支持对边的快速访问和操作。邻接多重表存无向图。

存储结构

1. 表头结点即顶点结点，与邻接表一样是顺序存储。

2. 对于每个顶点结点之后是与之相关联的弧结点（该弧结点中存有弧头、弧尾），而邻接表则是一些与顶点结点相连接的点。

3. 从每个顶点结点开始有两条链表，一条是以该顶点结点为弧头的链表，一条是以该顶点结点为弧尾的链表。

4. 对于其中的每一条链表必然是从顶点结点开始，直到与之相关的弧结点链域headlink和taillink为空是结束，构成一条完整的链表。

Example

代码

typedef struct ArcBox   // 弧的结构表示
{
    int tailvex, headvex;
    InfoType  *info;
    struct ArcBox  *hlink, *tlink;
} VexNode;
typedef struct VexNode   // 顶点的结构表示
{
    VertexType  data;
    ArcBox  *firstin, *firstout;
} VexNode;
typedef struct
{
    VexNode  xlist[MAX_VERTEX_NUM];// 顶点结点(表头向量)
    int   vexnum, arcnum;//有向图的当前顶点数和弧数
} OLGraph;