图的十字链表存储
使用邻接表可以方便地获取有向图顶点的出度，使用逆邻接表可以方便地获取有向图顶点的入度，那么有没有什么方法可以将这两种存储方式结合起来呢？答案是肯定的。
邻接表的头结点中已经有了指向该结点邻接点的指针，通过这个指针链接起来的顶点的数目，是该顶点的出度。为了方便获取该顶点的入度，可以借鉴逆邻接表，在头结点中新增一个域，这个域中的指针指向以该顶点为弧尾的第一个邻接点；同时在表结点中增加两个域，一个域用来存放邻接边弧头的编号，一个域用来存放邻接边的弧头指针。改良后的结点如图1所示。灰色部分为新增的域。
图1 十字链表的表结点和头结点
以顶点vi为例：
在头结点中，data域仍旧存放顶点的编号；firstin域存放一个指针，该指针指向第一个以vi为弧尾的表结点；firstout域存放一个指针，对应于邻接表中的firstarc域，该指针指向第一个以vi为弧头的表结点。
在表结点中，headvex域对应邻接表中的adjvex域，存放该顶点邻接点（弧尾结点）的编号；hlink域对应邻接表中的nextarc域，将邻接点链接成一个链表；info域依旧存放与边相关的信息；tailvex域和tlink域为新增域，分别存放该边弧头结点的编号和弧尾指针，弧尾指针将所有tailvex域为vi的表结点链接成一个链表。
图2给出了前面小节中有向图G1的十字链表存储示例。其中以虚线①②链接成的链表，是以v3为弧尾的顶点与v3的firstin指针构成的链表，这个链表中表结点的数目，即v3的入度。
图2 十字链表存储示例
这种存储方式类似于稀疏矩阵的十字链表存储，其表结点亦如处于一个十字路口，称为图的十字链表存储，它是一种针对有向图的存储方式。下面给出十字链表存储的数据定义。
//十字链表存储相关结构定义
#define MAX_VERTEX_NUM 100
//表结点
typedef struct EdgeNode
{
int headvex; //弧头编号
int tailvex; //弧尾编号
struct EdgeNode* tlink, *hlink;//弧头指针、弧尾指针
int info; //边相关信息
}EdgeNode;
//头结点
typedef struct
{
int data; //顶点相关信息
EdgeNode *firstin, *firstout;//向第一个邻接点和第一个逆邻接点
}VertexNode, GList[MAX_VERTEX_NUM];
//图的结构定义
typedef struct
{
GList list; //十字链表
int n; //顶点数目
int e; //边的数目
}CGraph;使用十字链表存储，获取出度和入度都很方便，因为很容易遍历以vi为顶点的弧，也很容易遍历以vi为终点的弧。十字链表存储结构虽然复杂，但是创建图的算法并不难，只是在邻接表的基础上多了一些定义和赋值语句。下面给出十字链表存储构建有向网图的代码。
//采用十字链表存储法，构造有向网图G
void CreateCGraph(CGraph *G)
{
int i, j, k;
int info;
EdgeNode *p;
VertexNode v1, v2;
printf("请输入顶点与边的数目，以,分割：");
scanf("%d,%d ", &G->n, &G->e);
//①构造头结点表
printf("请输入%d个顶点的值:\n", G->n, MAX_VERTEX_NUM);
for (i = 0; i<G->n; i++)
{
scanf("%s", &G->list[i].data); //输入顶点值
G->list[i].firstin = NULL; //初始化链表指针
G->list[i].firstout = NULL;
}
//②构造表结点表
printf("请输入%d条弧的弧尾和弧头(空格为间隔)和边信息:\n", G->e);
for (k = 0; k<G->e; k++)
{
scanf("%d%d%d", &i, &j, &info);
p = (EdgeNode*)malloc(sizeof(EdgeNode));//产生表结点
p->tailvex = i; //对表结点赋值
p->headvex = j;
p->info = info;
//完成在入弧和出弧链表表头的插入
p->hlink = G->list[j].firstin;
p->tlink = G->list[i].firstout;
G->list[j].firstin = G->list[i].firstout = p;
}
}十字链表存储构建图与邻接矩阵存储构造图的大致步骤相同，它也分为一个顺序表的构建和一个链表的构建。在构建算法中，①部分的时间复杂度为O(n)，即图中顶点的数目；②部分的时间复杂度为O(e)，即图中边的数目。所以整个算法的时间复杂度为O(n+e)。已知邻接表存储构建图的时间复杂度也为O(n+e)，可见虽然十字链表存储结构较邻接表存储结构略复杂，但是时间消耗是相同的，所以在有些有向图的应用中，十字链表存储是一种很有用的存储方式。
隐藏目录
