有向图的十字链表数据结构

[c]代码库

#define MAX_VERTEX_NUM 20
typedef struct ArcBox
{
	int tailvex,headvex; /*该弧的尾和头顶点的位置*/
	struct ArcBox * hlink, tlink;
	/分别为弧头相同和弧尾相财的弧的链域*/
	InfoType info; /*该弧相关信息的指针*/
} ArcBox;
typedef struct VexNode
{
VertexType vertex:
	ArcBox fisrin, firstout; /*分别指向该顶点第一条入弧和出弧*/
} VexNode;
typedef struct
{
	VexNode xlist[MAX_VERTEX_NUM]; /*表头向量*/
	int vexnum,arcnum; /*有向图的顶点数和弧数*/
} OLGraph;

void CreateDG ( LOGraph **G )
/*采用十字链表表示，构造有向图G(G.kind=DG)*/
{
	scanf ( & ( *G->brcnum ),& ( *G->arcnum ),&IncInfo ); /*IncInfo 为0 则各弧不含其实信息*/
	for ( i=0; i<*G->vexnum; ++i ) /*构造表头向量*/
	{
		scanf ( & ( G->xlist[i].vertex ) ); /*输入顶点值*/
		*G->xlist[i].firstin=NulL;
		*G->xlist[i].firstout =NULL; /*初始化指针*/
	}
	for ( k=0; k<G.arcnum; ++k ) /*输入各弧并构造十字链表*/
	{
		scanf ( &v1,&v2 ); /*输入一条弧的始点和终点*/
		i=LocateVex ( *G,v1 );
		j=LocateVex ( *G,v2 ); /*确定v1 和v2 在G 中位置*/
		p= ( ArcBox* ) malloc ( sizeof ( ArcBox ) ); /*假定有足够空间*/
		*p={ i,j,*G->xlist[j].fistin,*G->xlist[i].firstout,NULL} /*对弧结点赋值*/
		   /*{tailvex,headvex,hlink,tlink,info}*/
		   *G->xlist[j].fisrtin=*G->xlist[i].firstout=p; /*完成在入弧和出弧链头的插入*/
		if ( IncInfo ) Input ( p->info ); /*若弧含有相关信息，则输入*/
	}
}/*CreateDG*/