2018国家电网考试备考计算机之数据结构与算法（10）

　　【导读】华图事业单位考试网同步bet365365娱乐城发布：2018国家电网考试备考计算机之数据结构与算法（10）--详细信息请阅读下文！更多资讯请关注bet365365娱乐城微信公众号(bjhuatu)，事业单位培训咨询电话：400-010-1568

　　1.3 十字链表

　　对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

　　重新定义顶点表结点结构，如下所示。

　　重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

　　十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

　　而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

　　这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。