十字链表的存储结构

十字链表的存储结构

仅仅又适用有向图。可以，看成是把一个有向图的邻接表存储与其逆邻接表存储结合起来得到的一种链表。图中每条弧形成一个弧结点，每个顶点形成一个顶点结点。其结构分为:顶点结点和弧结点

顶点结点

顶点结点有三个域:data 域存放该顶点点的信息;firstin 域存放指向该顶点的第一条弧结点地址;firstou t 域存放以该顶点为弧尾顶点的第一条弧结点地址。

弧结点

弧结点有五个域:tailvex 域存放该条张瓜的尾顶点下标;headvex 域存放该条弧的头顶点下标; hlink 域存放与该条弧具有相同的头顶点的下一条弧结点地址。tlink 域存放该条弧具有相同的尾顶点的下一条弧结点地址。 info 域存放该条弧上的相关信息。

有向图十字链表存储结构

• 算法

#define MAX VERTEX NUM 20

typedef struct ArcBox{ (弧结点的结构)

int tailvex,headvex;(弧的尾与头顶点位置)

struct ArcBox *hlink,*tlink; (相同弧头、尾弧的指针)

InfoType *info; (该弧的相关信息的指针)

}ArcBox;

typedef struct VexNode{ (顶点结构)

VertexType data;

ArcBox *firstin,*firstout;(第一条入弧与第一条出弧)

}VexNode;

typedef struct {

VexNode xlist[ MAX VERTEX NUM];(表头向量)

int vexnum,arcnum;(顶点数与弧数)

}//OLGraph;

具有 N 个顶点和 E 条边的有向图十字链构造

Status CreatDG(OLGraph &G){

(采用十字链表存储表示,构造有向图 G(G.kind=DG)。)

scanf(&G.vexnum,&G.arcnum,&lncinfo);

(Incinfo 为 0 则各弧不含其他信息)

for(i=0;i<G.vexnum;++i){(构造表头向量)

scanf(&G.xlist[i].data);(输入顶点数据)

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);

(取顶点下标)

p=(ArcBox *)malloc(sizeof(ArcBox));

(假定有足够空间)

*P={i,j,G.xlist[i].firstin,G.xlist[i].firstout,NULL}

(对弧结点赋值 tailvex,headvex, hlink, tlink, info)

G.xlist [j].firstin=G.xlist[i].firstout = p;

(完成入弧和出弧链头行列链表首部插入)

if(Inclnfo) Input( *p->info);(若弧有其他信息，则输入)

}

} // CreatDG

• LocateVex(G,Vi):是一个取下标的函数。其功能就是把图 G 中顶点的下标与顶点上的其他信息分离开来。