1. 引言：
对于有向图来说，邻接表是有缺陷的：
邻接表：关心了出度问题，想了解入度就必须要遍历整个图才知道。
逆邻接表：解决了入度，却不了解出度的情况。
能否把邻接表和逆邻接表结合起来呢？答案就是：使用十字链表。
2.十字链表存储结构：
顶点表结点结构：
firstin：表示入边表头指针，指向该顶点的入边表中第一个结点。//新加入的
firstout：表示出边表头指针，指向该顶点的出边表中的第一个结点。//跟 邻接表中的 顶点一样
边表结点结构：
tailvex：指弧起点在顶点表的下标。
headvex：指弧终点在顶点表中的下标。//跟邻接表中的 adjvex 一样
headlink：指入边表指针域。
taillink：指边表指针域。//跟邻接表中的next 一样；
如果是网，还可以再增加一个weight域来存储权值。
蓝线表示出度，红线表示入度
3.十字链表的优点：
1.）十字链表是把邻接表和逆邻接表整合在一起，这样既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧，
因而容易求的顶点的出度和入度。
2.）十字链表创建图算法的时间复杂度和邻接表是相同的。
十字链表
typedef char Vtype //顶点类型
typedef int Etype //权值类型
#definde MAXV 100;
typedef struct edgeNode //边表节点
{
int tailvex; //新加入的
int headvex; //邻接点 存储该顶点对应的下标
Etype weight;//边 权值
struct edgeNode *headllink; //新加入的
struct edgeNode *taillink;
}EdgeNode;
typedef struct Vnode //顶点表 节点
{
Vtype data;
EdgeNode* firstInEdge; // 入度
EdgeNode* firstOutEdge;// 出度
}VNODE; //
typedef struct
{
VNODE adjlist[MAXV];
int numV;//当前顶点数
int numE;//当前边数
}GraphAdjList;
void CreateALGraph(GraphAdjList* G)
{
int i,j,k;
EdgeNode* e= NULL;
cout<<输入顶点数";
cin>>G->numV;
cout<<输入边数";
cin>>G->numE;
for(i=0;i<G->numV;i++)//建立顶点信息
{
cin >> G->adjlist[i].data; //输入顶点信息
G->adjlist[i].firstOutEdge = NULL; //边表节点 为空
G->adjlist[i].firstInEdge = NULL; //边表节点 为空
}
for(k=0;k<numE;k++)//建立边信息
{
cout<<"输入边的开始";
cin>>i;
cout<<"输入边的结尾";
cin>>j;
e = new EdgeNode; //
e->tailvex = i; //新加入的 弧的起点 入度
e->headlink = G->adjlist[j].firstInEdge; //新的
G->adjlist[j].firstInEdge = e;//新的
e->headvex = j; // 原来的 e->adjvex
e->taillink = G->adjlist[i].firstOutEdge; //原来的
G->adjlist[i].firstOutEdge = e;
}
}