您当前位置：北京人事考试网 > 北京事业单位考试 > 备考资料 > 2018国家电网考试备考计算机之数据结构与算法（10）

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

2018-03-09 14:13:28 事业单位考试网 ○加微信领资料 ○交流qq群 ○华图在线app 文章来源：北京华图

　　2018国家电网考试备考计算机之数据结构与算法（10）由北京事业单位考试网提供：更多关于2018国家电网考试,计算机数据结构与算法,事业单位考试网的内容请关注北京事业单位考试网！或关注北京华图微信公众号(bjhuatu)，如有问题也可点击联系各校区。

　　1.3 十字链表

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

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

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

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

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

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

　　点击查看：北京事业单位招聘辅导课程

★事业单位公基高频1000题领取★