5.2.3 十字链表
十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点，这些结点的结构如下：
弧结点
taivex | headvex | hlink | tlink | info |
|---|
顶点结点
data | firstin | firstout |
|---|
弧结点中有5个域：
其中尾域（tailvex）和头域（headVex）分别指示弧尾和弧头这两个顶点在图中的位置，
链域hlink指向弧头相同的弧在同一链表上，弧头相同的弧也在同一链表上。
顶点结点中有3个域：data域中存放顶点相关的数据信息，如顶点名称，firstin和firstout两个域分别指向以该顶点为弧头和弧尾的第一个弧结点。
注意，顶点结点之间是顺序存储。
图的十字链表存储结构定义如下：
#define MaxVertexNum 100//顶点数目的最大值
typedef struct ArcNode{//边表结点
int tailvex,headVex;//该弧的头尾结点
struct ArcNode *hlink,*tlink;//分别指向弧头相同和弧尾相同的结点
InforType info;//网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
VertextType data;//顶点信息
ArcNode *firstin,*firstout;//指向第一条入弧和出弧
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices;//邻接表
int vexnum ,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph 是以邻接表存储的图类型在十字链表中，既容易找到vi为尾的弧，也容易找到vi为头的弧，因而容易求得顶点的入度和出度。
图的十字链表表示不是唯一的，但一个实际链表表示确定一个图。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年09月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。