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题领取★
手机号: | ||
所属地区: | ||
——推荐阅读——
招考信息--北京事业单位招聘信息汇总|备考咨询
面授课程--事业单位笔试面授课程|面试面授课程
在线课程--事业单位笔试在线课程|面试在线课程
图书教材--事业单位笔试图书教材|面试图书教材
华图在线APP--全年模考|30W+题库|看视频 刷题
(编辑:刘然)贴心微信客服
微信公众号