图的十字链表存储方式解析 _十字链表

图的存储方式很多，常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等，邻接表和逆邻接表采用数组和链表方式存储，程序代码相对容易，邻接表求某顶点的出度容易但求入度较麻烦，逆邻接表求某顶点的入度容易但求出度较麻烦，为了达到鱼和熊掌兼得的效果，人们发明了十字链表的存储方式。
在十字链表中，顶点设计为一种结构体，并采用一维数组存储顶点。顶点结构体含有三个域，data存储顶点名称（序号），firstin存储以该顶点为头的第一个边的结点，firstout存储以该顶点为尾的第一个边的结点。

文章插图

边设计为一种结构体，采用链表方式存储。边的结构体含有五个域，tailvex存储该边的尾顶点的名称（序号），headvex存储该边的头顶点的名称（序号），hlink存储头相同的下一条边的结点，tlink存储尾相同的下一条边的结点，info存储边的信息（如权值）。

文章插图

下面以一个有向图为例来编写代码：

文章插图

首先定义边结构体和顶点结构体：

struct EdgeNode{int tail;int head;EdgeNode* hlink;EdgeNode* tlink;int info;};struct VerNode{int num;EdgeNode* firstin;EdgeNode* firstout;};

在main程序中开两个数组，一个存储顶点结点，一个存储边结点：
VerNode vn[4];EdgeNode en[7];初始化顶点：
【图的十字链表存储方式解析】for(int i=0;i<4;i++){vn[i].num=i;vn[i].firstin=NULL;vn[i].firstout=NULL;}输入边的信息（增加新的边结点时，链表前用前插方式，这样比较方便）：

for(int i=0;i<7;i++){int tv,hv,val;cin>>tv>>hv>>val;en[i].tail=tv;en[i].head=hv;en[i].info=val;en[i].tlink=vn[tv].firstout;vn[tv].firstout=&en[i];en[i].hlink=vn[hv].firstin;vn[hv].firstin=&en[i];}

对于上图，输入边的数据（尾、头、权值）：
0 1 10 2 12 0 12 3 13 0 13 1 13 2 1输出各个顶点出度、入度信息：

for(int i=0;i<4;i++){cout<<"从"<<i<<"出发的边："<<endl;EdgeNode* p=vn[i].firstout;while(p!=NULL){cout<<i<<"-->"<<p->head<<endl;p=p->tlink;}cout<<"到达"<<i<<"的边："<<endl;EdgeNode* q=vn[i].firstin;while(q!=NULL)cout<<q->tail<<"-->"<<i<<endl;q=q->hlink;}}

十字链表存储图示如下：

文章插图

从上图中可以看出，边结点tailvex值相同的为以该顶点为尾的边的集合，以链表方式存储；headvex相同的为以该顶点为头的边的集合，以链表方式存储。
其实，我们也可以根据自己需要灵活设计顶点和边的结构体来存储图，以达到解决某特定问题的目的。所以，数据结构决定了算法，选择好的数据结构可以减轻算法的压力。