十字链表是有向图的一种链式存储结构。在十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点,这些结点的结构如下:
弧结点
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为头的弧,因而容易求得顶点的入度和出度。
图的十字链表表示不是唯一的,但一个实际链表表示确定一个图。