那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢？答案是肯定的，就是把它们整合在一起。这就是我们现在要讲的有向图的一种存储方法：十字链表（Orthogonal List）。

    我们重新定义顶点表结点结构如表7-4-1所示。

    data firstin firstout

    其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

    重新定义的边表结点结构如表7-4-2所示。

    tailvex headvex headlink taillink

    其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

    比如图7-4-10，顶点依然是存入一个一维数组{v 0 ,v 1 ,v 2 ,v 3 }，实线箭头指针的图示完全与图7-4-7的邻接表相同。就以顶点v 0 来说，firstout指向的是出边表中的第一个结点v3 。所以v0 边表结点的headvex=3，而tailvex其实就是当前顶点v0 的下标0，由于v0 只有一个出边顶点，所以headlink和taillink都是空。
    image.png
    我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于v 0 来说，它有两个顶点v 1 和v 2 的入边。因此v 0 的firstin指向顶点v 1 的边表结点中headvex为0的结点，如图7-4-10右图中的①。接着由入边结点的headlink指向下一个入边顶点v 2 ，如图中的②。对于顶点v1，它有一个入边顶点v 2 ，所以它的firstin指向顶点v 2 的边表结点中headvex为1的结点，如图中的③。顶点v 2 和v 3 也是同样有一个入边顶点，如图中④和⑤。

    十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以v i 为尾的弧，也容易找到以v i 为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。