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

图的存储方式很多，常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等，邻接表和逆邻接表采用数组和链表方式存储，程序代码相对容易，邻接表求某顶点的出度容易但求入度较麻烦，逆邻接表求某顶点的入度容易但求出度较麻烦，为了达到鱼和熊掌兼得的效果，人们发明了十字链表的存储方式。

在十字链表中，顶点设计为一种结构体，并采用一维数组存储顶点。顶点结构体含有三个域，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 1
0 2 1
2 0 1
2 3 1
3 0 1
3 1 1
3 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相同的为以该顶点为头的边的集合，以链表方式存储。

其实，我们也可以根据自己需要灵活设计顶点和边的结构体来存储图，以达到解决某特定问题的目的。所以，数据结构决定了算法，选择好的数据结构可以减轻算法的压力。