<写博客是为了学习理解更深刻>
在学习甲鱼课的十字链表时稍稍有点懵，进C站查找一番后发现也没有比较亲近小白的描述和解释。抱着让自己理解更深刻以及与大家分享的态度写下了这篇博客。如有错误请指出。
十字链表的引入：
邻接表的使用简单方便，但在对有向图的处理上，单邻接表只能表示出度（如图1）
但在特定情况，需要关注点的入度，则需要再建立一个逆邻接表。
（图1）A的邻接表，表示出边表 （图2）A的入边表与出边表
因此，不妨将邻接表和逆邻接表结合起来，由此创造出十字链表，既能表示入度，也能表示出度。（图2，是不是很十字？）
十字链表的构造方法：
①重新定义表头结构
只需对表头结构稍加改动，增加firstIn和firstOut两个指针域，分别指向以A为弧尾和以A为弧头的第一个顶点地址。这样通过对in、out两指针域迭代检索，就能获取入度和出度。（可对比观察图一，图二的头结构帮助理解）
| data | firstIn | firstOut |
文章来源地址https://www.toymoban.com/news/detail-404741.html
data:顶点的数据 firstIn：第一个入边表的指针 firstOut：第一个出边表的指针
②重定义边表的节点结构
（邻接表除去头结点的链表结构，每个结点都表示一条边，因此叫边表）
边表每个结点结构如下：
tailvex：弧起点的下标 headvex：弧终点的下标 headlink:入边指针 taillink:出边指针
| tailVex | headVex | headLink | tailLink |
每个结点都包含一条完整边的信息 tailvex->headvex； 下一条入边的地址headlink；下一条出边的地址taillink。
通过对四个域的填充即可形成十字链表。
有点抽象，举个具体例子帮助理解：
1.图如左下角所示，根据步骤①建立好顶点结构
2.建立如②所示的节点结构，与邻接表建立方式相同，将firstOut指针域指向第一条出边，再依次填充tailLink指针域，完善出边表。
（有点小丑 T_T）
3.与建立逆邻接表方式相同，将firstIn指针域指向第一条入边地址，再依次填充headLink指针域，完善入边表。
（以V0为例）
4.最终形成了其他帖子里那种杂乱的十字链表图
（图截自bilibili鱼C-小甲鱼的《数据结构和算法》）
如此，十字链表建立完成。用一个表，即可得出图内每个顶点的入度和出度。
文章来源：https://www.toymoban.com/news/detail-404741.html
到了这里，关于图论：十字链表的基本概念理解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
