有向图的十字链表表示 在十字链表中,对应于有向图中每一条弧有 个结点,对应每个顶点也有一个结点 结 顶点结点 tailvex headvex h Datal firstin firstout 十字链表可以看成邻接矩阵的链式存储 000 >用C语言描述的十字链表 #define MAX VERTEX NUM 20 sx typedef struct ArcBox( 据 int tailvex, headvex;∥该弧的尾和头顶点的位置 构 struct Are Box *hlink,tink;/弧头及弧尾相同的弧的链域 info ∥该弧相关信息的指针 r Typedef stuct VexNodel Are Box * firstin, *firstout;/分别指向该顶点第一条入弧和出弧 24 Typedef struct Ⅴ exNode xlist MAX VERTEX NUM;表头向量 Int vexnum. arenum: 有向图的当前顶点数和弧数 ALGraph12 数 据 结 构 之 图 23 ¾ 有向图的十字链表表示 ¾ 在十字链表中，对应于有向图中每一条弧有一 个结点，对应每个顶点也有一个结点。 ¾ 十字链表可以看成邻接矩阵的链式存储 tailvex headvex hlink tlink 弧结点 Data firstin firstout 顶点结点 V1 V2 V3 V4 V1 V2 ^ V3 V4 0 1 ^ 0 2 ^ ^ 2 3 ^ ^ 3 0 ^ ^ 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 数 据 结 构 之 图 24 ¾ 用C语言描述的十字链表： #define MAX_VERTEX_NUM 20 typdef struct ArcBox{ int tailvex, headvex; //该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; //弧头及弧尾相同的弧的链域 InfoType *info; //该弧相关信息的指针 }ArcBox; Typedef stuct VexNode{ VertexType data; ArcBox *firstin, *firstout; //分别指向该顶点第一条入弧和出弧 }VexNode; Typedef struct{ VexNode xlist[MAX_VERTEX_NUM]; //表头向量 int vexnum, arcnum; //有向图的当前顶点数和弧数 }ALGraph;