数据结构——图——存储结构——十字链表

古城微笑少年丶 2023-01-10 14:52 112阅读 0赞

## 数据结构——图——存储结构——十字链表 ##

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

我们重新定义顶点表结点结构如表7-4-1所示。  
![在这里插入图片描述][20210125114852269.png]  
其中 firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义的边表结点结构如表7-4-2所示。  
![在这里插入图片描述][2021012511493226.png]  
其中 tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

比如图7-4-10，顶点依然是存入一个一维数组\{vo,VV2V3\}，实线箭头指针的图示完全与图7-4-7的邻接表相同。就以顶点vo来说，firstout 指向的是出边表中的第一个结点 v3。所以vo边表结点的headvex=3，而tailvex其实就是当前顶点vo的下标0，由于vo只有一个出边顶点，所以headlink和 taillink都是空。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此v0的 firstin 指向顶点v的边表结点中headvex为0的结点，如图7-4-10右图中的①。接着由入边结点的 headlink指向下一个入边顶点v2，如图中的②。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中 headvex为1的结点，如图中的③。顶点v2和v3也是同样有一个入边顶点，如图中④和⑤。

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

[20210125114852269.png]: /images/20221119/3280199b97f4493f9c3e6b173d62d7fa.png
[2021012511493226.png]: /images/20221119/55b26fbf07f24dee8f2d3ad801adfff4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210125115026353.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70