圖的存儲(chǔ)結(jié)構(gòu)：鄰接表法

• 產(chǎn)生條件：
• 鄰接表法的定義：
• 鄰接表法的特點(diǎn)：
• 鄰接表法的代碼定義：
• 鄰接表法與鄰接矩陣法的對(duì)比：

產(chǎn)生條件：

當(dāng)用鄰接矩陣存儲(chǔ)時(shí)：空間復(fù)雜度為O(|v|^2),太大

鄰接表法的定義：

例：

鄰接表法的特點(diǎn)：

ps：

1、存儲(chǔ)空間 = 節(jié)點(diǎn)占用空間 + 邊占用空間 2、鄰接表的長(zhǎng)度表示該頂點(diǎn)的出度 3、鄰接表出現(xiàn)某一頂點(diǎn)的次數(shù)為該頂點(diǎn)的入度

鄰接表法的代碼定義：

#define MaxVertexTypeNum 100 typedef char VertexType; typedef int EdgeType; typedef struct ArcNode{ //邊表節(jié)點(diǎn) int adjvex; //下一個(gè)節(jié)點(diǎn)的數(shù)據(jù) struct ArcNode *next; // 指向下一個(gè)結(jié)點(diǎn)的指針 // InfoType info; //權(quán)值 }ArcNode; //邊表節(jié)點(diǎn)的類型 typedef struct VNode{ //頂點(diǎn)表節(jié)點(diǎn) VertexType data; //頂點(diǎn)的數(shù)據(jù) ArcNode *first; //指向邊表的頭指針 }VNode,AdjList[MaxVertexTypeNum]; // 鄰接表類型 typedef struct{ //鄰接表 AdjList vetices; //所有結(jié)點(diǎn)的數(shù)據(jù) int vexnum,arcnum; //節(jié)點(diǎn)數(shù)和邊數(shù) }ALGraph; //鄰接表類型

鄰接表法與鄰接矩陣法的對(duì)比：

總結(jié)

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

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