数据结构学习日志之十九--十字链表与邻接多重表

之前我们讲到，对于有向图，它的邻接表有出度和入度之分。为此，重新定义顶点结构和边表结构

顶点结构

data表示顶点数据，firstIn表示入边表，firstOut表示出边表

边表结构

tailVex表示弧起点顶点下标，headVex表示弧终点顶点下标，headLink指向弧头相同的下一条弧，tailLink指向弧尾相同的下一条弧

这就是十字链表，好处就是把邻接表和逆邻接表整合在一起，既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧。

邻接多重表：

对于无向图，邻接表对边的操作不方便，因为我们要删除一条边的话，要删除表的两个结点和修改与之关联的指针域

为此，我们模仿十字链表，对无向图的边表结构进行改装

其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边，jLink指向依附顶点jVex的下一条边。

如上图。以

为例，iLink为依附顶点v1的边，由于在一维数组已经指向（1，2）了，所以在iLink应该指向（1，0）这条边。jLink为依附于v2的边，边表（2，3）指向（1，2），一维数组指向（2，3），所以jLink指向（2，0）。