一：前言

當(dāng)我們考慮用鄰接表儲(chǔ)存數(shù)據(jù)的時(shí)候，一定會(huì)拿鄰接矩陣和其進(jìn)行比較。鄰接矩陣在儲(chǔ)存數(shù)量較小的數(shù)據(jù)是耗費(fèi)的內(nèi)存是要高于鄰接表的。那么我們?cè)谧鲱}的時(shí)候如果出現(xiàn)內(nèi)存超限，那就要注意了，可以考慮換用鄰接表來(lái)儲(chǔ)存數(shù)據(jù)了

二：相關(guān)描述

1.問(wèn)題：利用鄰接表來(lái)儲(chǔ)存有向圖的數(shù)據(jù)

2.測(cè)試數(shù)據(jù):
輸入： 5 8
1 2 5
1 3 8
1 5 3
2 5 6
2 3 2
3 4 10
3 5 4
4 5 11

輸出：為每個(gè)頂點(diǎn)和其相連邊的頂點(diǎn)以及權(quán)值
1 5 3 3 8 2 5
2 3 2 5 6
3 5 4 4 10
4 5 11
5
輸出的解釋說(shuō)明:1 5 3 3 8 2 5 頂點(diǎn)1和5相連權(quán)值為3，頂點(diǎn)1和3相連權(quán)值為8，頂點(diǎn)1和2相連權(quán)值為5

3.分析如何建立鄰接表使其輸出上述數(shù)據(jù)
1>:首先指出，我們采取用數(shù)組模擬指針來(lái)建立鏈表，采用結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)每個(gè)結(jié)點(diǎn)的信息
2>:結(jié)構(gòu)體數(shù)組中的值為{頂點(diǎn)下標(biāo)，邊的權(quán)值，指向下一個(gè)結(jié)點(diǎn)的下標(biāo)}
注意指向下一個(gè)結(jié)點(diǎn)的下標(biāo)，因?yàn)槲覀儾捎玫氖菙?shù)組來(lái)模擬指針，所以我們的head 和 next
都是記錄結(jié)構(gòu)體的數(shù)組下標(biāo)，而head[i] 中的 i才是真正的頂點(diǎn)下標(biāo)
3>:模擬指針為空的狀況我們采用 當(dāng) next的值為0是表示為空
4>:建立鏈表和遍歷鏈表請(qǐng)看代碼

4.圖示鄰接表

5.示例當(dāng)中的鄰接表和

代碼中鏈表插入的過(guò)程

三：上碼

/**1.問(wèn)題：利用鄰接表來(lái)儲(chǔ)存有向圖的數(shù)據(jù)2.測(cè)試數(shù)據(jù): 輸入： 5 81 2 51 3 81 5 32 5 62 3 23 4 103 5 44 5 11輸出：為每個(gè)頂點(diǎn)和其相連邊的頂點(diǎn)以及權(quán)值1 5 3 3 8 2 5 2 3 2 5 63 5 4 4 104 5 115 輸出的解釋說(shuō)明:1 5 3 3 8 2 5 頂點(diǎn)1和5相連權(quán)值為3，頂點(diǎn)1和3相連權(quán)值為8，頂點(diǎn)1和2相連權(quán)值為5 3.分析如何建立鄰接表使其輸出上述數(shù)據(jù)1>:首先指出，我們采取用數(shù)組模擬指針來(lái)建立鏈表，采用結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)每個(gè)結(jié)點(diǎn)的信息2>:結(jié)構(gòu)體數(shù)組中的值為{頂點(diǎn)下標(biāo)，邊的權(quán)值，指向下一個(gè)結(jié)點(diǎn)的下標(biāo)} 注意指向下一個(gè)結(jié)點(diǎn)的下標(biāo)，因?yàn)槲覀儾捎玫氖菙?shù)組來(lái)模擬指針，所以我們的head 和 next都是記錄結(jié)構(gòu)體的數(shù)組下標(biāo)，而head[i] 中的 i才是真正的頂點(diǎn)下標(biāo)3>:模擬指針為空的狀況我們采用 當(dāng) next的值為0是表示為空4>:建立鏈表和遍歷鏈表請(qǐng)看代碼 **/#include<bits/stdc++.h> using namespace std; #define max 20000struct Node{int to;//到達(dá)某個(gè)點(diǎn) int val;//邊的權(quán)值 int next;//指向下一個(gè)結(jié)點(diǎn)下標(biāo) } node[max];int head[max] = {0},n,m,num = 0;//head為記錄結(jié)構(gòu)體下標(biāo)，num為結(jié)構(gòu)體的下標(biāo) //建立鏈表 這個(gè)過(guò)程類(lèi)似于頭插法，每次插入都插入到上一個(gè)結(jié)點(diǎn)的前面 void add(int from,int to,int val){num++; node[num].to = to; node[num].val = val;node[num].next = head[from];//指向下一個(gè)結(jié)點(diǎn)的下標(biāo) head[from] = num;//記錄結(jié)構(gòu)體數(shù)組的下標(biāo)，下次插入的時(shí)候指向其 } int main(){cin >> n >> m;for(int i = 0; i < m; i++){int from,to,val;cin >> from >> to >> val;add(from,to,val);//add(to,from,val); 這里表示的是無(wú)向圖中鄰接表 } //遍歷鄰接表for(int i = 1; i <= n; i++){//因?yàn)轫旤c(diǎn)是從1開(kāi)始的cout << i << ' ';for(int j = head[i]; j != 0; j = node[j].next){ //遍歷頂點(diǎn)為i的鏈表 直到結(jié)構(gòu)體的下標(biāo)為0 cout << node[j].to << ' '<< node[j].val << ' '; } cout << endl;} } //5 8 //1 2 5 //1 3 8 //1 5 3 //2 5 6 //2 3 2 //3 4 10 //3 5 4 //4 5 11

四：書(shū)上的例子創(chuàng)建鄰接表（有億點(diǎn)麻煩）

//鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表第一個(gè)結(jié)點(diǎn)存放頂點(diǎn)信息，其余存放有關(guān)邊信息。 //鄰接表由表頭結(jié)點(diǎn)表和邊表組成。 // (01) LGraph是鄰接表對(duì)應(yīng)的結(jié)構(gòu)體。 // vexnum是頂點(diǎn)數(shù)，edgnum是邊數(shù)；vexs則是保存頂點(diǎn)信息的一維數(shù)組。// (02) VNode是鄰接表頂點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。 // data是頂點(diǎn)所包含的數(shù)據(jù)，而first_edge是該頂點(diǎn)所包含鏈表的表頭指針。// (03) ENode是鄰接表頂點(diǎn)所包含的鏈表的節(jié)點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。 // ivex是該節(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)在vexs中的索引，而next_edge是指向下一個(gè)節(jié)點(diǎn)的 #include<stdio.h> #include<stdlib.h> #define Max 100 typedef struct Graph* ptrGraph; typedef struct Edgenode* ptrEdgenode; typedef struct Edgenode{//邊結(jié)點(diǎn)int adjvex;//邊結(jié)點(diǎn)位置下標(biāo)struct Edgenode* next; }edgenode; typedef struct Vnode{//頂點(diǎn)int Data;struct Edgenode* firstarc; }vnode; typedef struct Graph{struct Vnode AdjList[Max];int Nv;int Ne; }graph; int locateVex(ptrGraph G,int v){//根據(jù)v點(diǎn)信息，找到相應(yīng)坐標(biāo)int i;for(i=0;i<G->Nv;i++){if(G->AdjList[i].Data==v){return i;}}return -1; } int CreatGraph(ptrGraph G){int i,j;int V1,V2,K1,K2;ptrEdgenode p1,p2;scanf("%d%d",&G->Nv,G->Ne);//輸入頭結(jié)點(diǎn)（即頂點(diǎn)的數(shù)據(jù)）for(i=0;i<G->Nv;i++){scanf("%d",&G->AdjList[i].Data);G->AdjList[i].firstarc=NULL;}//輸入邊的兩個(gè)結(jié)點(diǎn)for(j=0;j<G->Ne;j++){scanf("%d%d",&V1,&V2);K1=locateVex(G,V1);K1=locateVex(G,V2);p1=(ptrEdgenode)malloc(sizeof(struct Edgenode));p1->adjvex=K1;p1->next=G->AdjList[K2].firstarc;//鏈表前插法G->AdjList[K2].firstarc=p1;p2=(ptrEdgenode)malloc(sizeof(struct Edgenode));p2->adjvex=K2;p2->next=G->AdjList[K1].firstarc;G->AdjList[K1].firstarc=p2;}return 0;} void output_AL(ptrGraph G) //輸出 {int i;for( i=0;i<G->Nv;i++){printf("頂點(diǎn)%d",G->AdjList[i].Data);ptrEdgenode p=G->AdjList[i].firstarc;while(p!=NULL){printf("->%d",p->adjvex); //輸出下標(biāo)//printf("->%c",G.AdjList[p->adjvex].data); //輸出頂點(diǎn)元素p=p->next;}printf("\n");} }int main() {ptrGraph G;CreatGraph(G);// output_AL(G);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的临界表储存图的数据（思路+详解+图示）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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