數據結構總目錄

十字鏈表

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语言)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。