数据结构总目录

十字链表

1. 图文解析

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

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

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

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

边结点结构图

顶点结点结构图

图与十字链表

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

2. 源代码

#include <stdio.h> #include <stdlib.h> #define MaxVex 20typedef 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. 测试结果

总结

以上是生活随笔为你收集整理的数据结构_十字链表(C语言)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。