相關定義

• 十字鏈表適用于有向圖。
• 十字鏈表時有向圖的另一種鏈式存儲結構。（鄰接表也是鏈式）
• 十字鏈表中：
  對應于有向圖中每個頂點都有一個結點，稱此類結點為頂點結點。
  對應于有向圖中每一條弧都有一個結點，稱此類結點為弧結點。

• 頂點結點
  由 3 個域組成
  1、data域 ：存儲和頂點相關的信息，如頂點的名稱。
  2、firstin域 ：指向以該頂點為弧頭的第一個弧結點。
  3、firstout域 ：指向以該頂點為弧尾的第一個弧結點。

• 弧結點
  由5個域組成
  1、尾域 / tailvex域 ：表示弧尾所在頂點在圖中的位置。
  2、頭域 / headvex域 ： 表示弧頭所在頂點在圖中的位置。
  3、鏈域 hlink域 ： 指向弧頭相同的下一條弧。
  4、鏈域 tlink域 ： 指向弧尾相同的下一條弧。
  5、info域 ： 指向該弧的相關信息。

• 十字鏈表示例（僅限有向圖）
  

十字鏈表存儲表示

#define MAX_VERTEX_NUM 20//弧結點 typedef struct ArcBox {int tailvex, headvex; //該弧的尾和頭頂點的位置struct ArcBox *hlink, *tlink; //分別為弧頭相同和弧尾相同的弧的鏈域InfoType *info; } ArcBox; //頂點結點 typedef struct VexNode {VertexType data;// 分別指向該頂點的第一條入弧和出弧ArcBox *firstin, *firstout; } VexNode;// 表示一個有向圖整體 typedef struct {VexNode xlist[MAX_VERTEX_NUM]; // 表頭向量，各個頂點int vexnum, arcnum; // 有向圖的當前頂點數和弧數 } OLGraph;

代碼實現：建立十字鏈表（ n 個頂點和 e 條弧）

Status CreateDG(OLGraph &G) {// 采用十字鏈表存儲表示，構造有向圖 G（G.kind = DG）scanf(&G.vexnum, &G.arcnum, &IncInfo);// 初始化各個表頭頂點for(i=0; i<G.vexnum; ++i){scanf(&G.xlist[i].data);G.xlist[i].firstin = NULL;G.xlist[i].firstout = NULL;}for(k=0; k<G.arcnum; k++){scanf(&v1, &v2); // v1 和 v2 分別是一條弧的起點和終點i = LocateVex(G, v1); // 確定 v1 和 v2 在 G 中的位置j = LocateVex(G, v2);p = (ArcBox *)malloc(sizeof(ArcBox));*p = {i, j, G.xlist[j].firstin, G.xlist[i].firstout, NULL}; // 對弧結點的賦值G.xlist[j].firstin = G.xlist[i].firstout = p; // 完成入弧和出弧鏈頭的插入if(IncInfo){Input(*p->info);}} }

• 十字鏈表的特點
  1、僅適用于 有向圖
  2、即容易找到以 v_i 為尾的弧，也容易找到以 v_i 為頭的弧，因而容易求得頂點的出度和入度。
  3、若 輸入的頂點信息 即為 頂點的編號，則建立鄰接表的時間復雜度為 O( n+e )
  否則，需要通過查找才能得到頂點在圖中位置，則時間復雜度為 O( n*e )

總結

以上是生活随笔為你收集整理的7.2.3 十字链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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