圖的存儲(chǔ)結(jié)構(gòu)：十字鏈表法

• 思維導(dǎo)圖：
• 產(chǎn)生條件：
• 十字鏈表法的定義：
• 十字鏈表法的代碼定義:
• 性能分析：

思維導(dǎo)圖：

產(chǎn)生條件：

當(dāng)用鄰接矩陣存儲(chǔ)時(shí)：空間復(fù)雜度為O(|v|^2),太大
當(dāng)用鄰接表法存儲(chǔ)時(shí)：在進(jìn)行入度查詢時(shí)只能進(jìn)行全部節(jié)點(diǎn)遍歷，很不方便

十字鏈表法的定義：

**PS:**只能存儲(chǔ)有向圖

找指定頂點(diǎn)的所有出邊：順著綠色指針找
找指定頂點(diǎn)的所有入邊：順著橙色指針找

頂點(diǎn)表節(jié)點(diǎn)：

1、data:頂點(diǎn)數(shù)據(jù)域 2、firstin:入邊單鏈表頭指針 3、firstout:出邊單鏈表頭指針

邊表節(jié)點(diǎn)：

1、tailvex:尾域，存放弧尾節(jié)點(diǎn) 2、headvex:頭域，存放弧頭節(jié)點(diǎn) 3、hlink:弧頭相同的下一條邊，即指向下一個(gè)邊表節(jié)點(diǎn)的指針 4、tlink:弧尾相同的下一條邊 5、info:權(quán)值

十字鏈表法的代碼定義:

#define MaxVertexTypeNum 100 typedef char VertexType; typedef int EdgeType; typedef struct ArcNode{ //邊表節(jié)點(diǎn) int tailvex,headvex; //尾域和頭域 struct ArcNode *hlink , *think; //出單鏈表和入單鏈表 //InfoType info; //權(quán)值 }ArcNode; //邊表節(jié)點(diǎn)的類型 typedef struct VNode{ //頂點(diǎn)表節(jié)點(diǎn) VertexType data; //頂點(diǎn)的數(shù)據(jù) ArcNode *firstin,*firstout; //入單鏈表的頭指針和入單鏈表的頭指針 }VNode; // 鄰接表類型 typedef struct{ //十字鏈表 VNode xlist[MaxVertexTypeNum]; //所有結(jié)點(diǎn)的數(shù)據(jù) int vexnum,arcnum; //節(jié)點(diǎn)數(shù)和邊數(shù) }ALGraph; //十字鏈表的類型

性能分析：

空間復(fù)雜度：O(|v| + |E|)

總結(jié)

以上是生活随笔為你收集整理的数据结构之图的存储结构：十字链表法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。