大家好，又见面了，我是你们的朋友全栈君。

十字链表

1. 图文解析

在无向图中，两个顶点之间的连接我们称之为边；

而在有向图中，两个顶点之间具有方向的连接称之为弧（英文：Arc）
如下图中弧（A->B）的权值=10，其中A为该弧的头顶点，B为该弧的尾顶点

也可以理解为在无向图中每条边都存在两条弧

十字链表的结构和邻接表的结构较为相似，同样采用了顺序表与链表结构的结合，但在十字链表中存在两个链表，分别用于表示相同头顶点和尾顶点的弧链表。

边结点结构图

顶点结点结构图

图与十字链表

1、在十字链表中，如果仅看相同头顶点的弧链表，其结构和邻接表相同，采用头插法插入弧结点
2、对于相同尾结点的弧链表，实际上就是在已插入的弧结点中，对相同尾顶点的弧结点进行链接，其操作也是链表的头插法。

2. 源代码

#include <stdio.h>
#include <stdlib.h>
#define MaxVex 20
typedef int ArcType;
typedef char VertexType;
// 弧结点结构
typedef struct ArcNode
{ 

ArcType arcData;        // 弧的数据
int headVertex, tailVertex;   // 弧的头顶点和尾顶点
struct ArcNode *nextHeadArc, *nextTailArc;  // 指向相同头、尾顶点的弧指针 
}ArcNode, *ArcList;
// 顶点结点结构
typedef struct VertexNode
{ 

VertexType vertexData;      // 顶点的数据
ArcList headList, tailList; // 相同头、尾顶点的弧链表
}VertexNode, *VertexList;
// 十字链表结构
typedef struct
{ 

VertexList vertexList;
int numVertexs, numArcs;
}OLGraph;
// 初始化十字链表
void InitOLGraph(OLGraph *G)
{ 

// 初始化顶点
G->numVertexs = 0;
G->numArcs = 0;
G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
// 初始化顶点的两个链表头结点（也可不带头结点）
int i;
for (i = 0; i < MaxVex; i++)
{ 

// 相同头顶点的弧链表
G->vertexList[i].headList = (ArcNode *)malloc(sizeof(ArcNode));
G->vertexList[i].headList->nextHeadArc = NULL;
G->vertexList[i].headList->nextTailArc = NULL;
// 相同尾顶点的弧链表
G->vertexList[i].tailList = (ArcNode *)malloc(sizeof(ArcNode));
G->vertexList[i].tailList->nextHeadArc = NULL;
G->vertexList[i].tailList->nextTailArc = NULL;
}
printf("已初始化十字链表!\n");
}
// 创建十字链表
void CreateOLGraph(OLGraph *G)
{ 

printf("请输入顶点数和弧数:");
scanf("%d %d", &G->numVertexs, &G->numArcs);
// 输入顶点数据
int i, j, k;
for (i = 0; i < G->numVertexs; i++)
{ 

fflush(stdin);
printf("请输入第%d个顶点信息:", i + 1);
scanf("%c", &G->vertexList[i].vertexData);
}
// 输入弧结点数据
ArcType w;
for (k = 0; k < G->numArcs; k++)
{ 

printf("请输入弧(Ai, Aj)的头、尾顶点及其权值:");
scanf("%d %d %d", &i, &j, &w);
// 创建新的弧结点，并设置该弧结点的数据和头尾顶点的下标
ArcNode *s;
s = (ArcNode *)malloc(sizeof(ArcNode));
s->arcData = w;
s->headVertex = i - 1;
s->tailVertex = j - 1;
// 头插法插入相同头顶点的弧链表
s->nextHeadArc = G->vertexList[i - 1].headList->nextHeadArc;
G->vertexList[i - 1].headList->nextHeadArc = s;
// 头插法插入相同尾顶点的弧链表
s->nextTailArc = G->vertexList[j - 1].tailList->nextTailArc;
G->vertexList[j - 1].tailList->nextTailArc = s;
}
printf("已完成十字链表的创建!\n");
}
void DisplayOLGraph(OLGraph G)
{ 

int i;
ArcNode *p;
for (i = 0; i < G.numVertexs; i++)
{ 

printf("顶点:%c\n", G.vertexList[i].vertexData);
// 相同头顶点的弧链表
printf("\t相同头顶点的弧:");
p = G.vertexList[i].headList;
while (p->nextHeadArc)
{ 

p = p->nextHeadArc;
printf("(%c)%d(%c) => ", 
G.vertexList[p->headVertex].vertexData,
p->arcData, 
G.vertexList[p->tailVertex].vertexData);
}
printf("NULL\n");
// 相同尾顶点的弧链表
printf("\t相同尾顶点的弧:");
p = G.vertexList[i].tailList;
while (p->nextTailArc)
{ 

p = p->nextTailArc;
printf("(%c)%d(%c) => ", 
G.vertexList[p->headVertex].vertexData,
p->arcData, 
G.vertexList[p->tailVertex].vertexData);
}
printf("NULL\n");
}
}
int main()
{ 

OLGraph G;
InitOLGraph(&G);
CreateOLGraph(&G);
DisplayOLGraph(G);
system("pause");
return 0;
}

3. 测试结果