圖的存儲(chǔ)方式很多，常用的有鄰接矩陣、鄰接表、逆鄰接表、十字鏈表、鏈?zhǔn)角跋蛐堑龋徑颖砗湍驵徑颖聿捎脭?shù)組和鏈表方式存儲(chǔ)，程序代碼相對(duì)容易，鄰接表求某頂點(diǎn)的出度容易但求入度較麻煩，逆鄰接表求某頂點(diǎn)的入度容易但求出度較麻煩，為了達(dá)到魚(yú)和熊掌兼得的效果，人們發(fā)明了十字鏈表的存儲(chǔ)方式。
在十字鏈表中，頂點(diǎn)設(shè)計(jì)為一種結(jié)構(gòu)體，并采用一維數(shù)組存儲(chǔ)頂點(diǎn)。頂點(diǎn)結(jié)構(gòu)體含有三個(gè)域，data存儲(chǔ)頂點(diǎn)名稱（序號(hào)），firstin存儲(chǔ)以該頂點(diǎn)為頭的第一個(gè)邊的結(jié)點(diǎn)，firstout存儲(chǔ)以該頂點(diǎn)為尾的第一個(gè)邊的結(jié)點(diǎn)。
邊設(shè)計(jì)為一種結(jié)構(gòu)體，采用鏈表方式存儲(chǔ)。邊的結(jié)構(gòu)體含有五個(gè)域，tailvex存儲(chǔ)該邊的尾頂點(diǎn)的名稱（序號(hào)），headvex存儲(chǔ)該邊的頭頂點(diǎn)的名稱（序號(hào)），hlink存儲(chǔ)頭相同的下一條邊的結(jié)點(diǎn)，tlink存儲(chǔ)尾相同的下一條邊的結(jié)點(diǎn)，info存儲(chǔ)邊的信息（如權(quán)值）。
下面以一個(gè)有向圖為例來(lái)編寫(xiě)代碼：
首先定義邊結(jié)構(gòu)體和頂點(diǎn)結(jié)構(gòu)體：
struct EdgeNode{
int tail;
int head;
EdgeNode* hlink;
EdgeNode* tlink;
int info;
};
struct VerNode{
int num;
EdgeNode* firstin;
EdgeNode* firstout;
};
在main程序中開(kāi)兩個(gè)數(shù)組，一個(gè)存儲(chǔ)頂點(diǎn)結(jié)點(diǎn)，一個(gè)存儲(chǔ)邊結(jié)點(diǎn)：
VerNode vn[4];
EdgeNode en[7];
初始化頂點(diǎn)：
for(int i=0;i<4;i++){
vn[i].num=i;
vn[i].firstin=NULL;
vn[i].firstout=NULL;
}
輸入邊的信息（增加新的邊結(jié)點(diǎn)時(shí)，鏈表前用前插方式，這樣比較方便）：
for(int i=0;i<7;i++){
int tv,hv,val;
cin>>tv>>hv>>val;
en[i].tail=tv;
en[i].head=hv;
en[i].info=val;
en[i].tlink=vn[tv].firstout;
vn[tv].firstout=&en[i];
en[i].hlink=vn[hv].firstin;
vn[hv].firstin=&en[i];
}
對(duì)于上圖，輸入邊的數(shù)據(jù)（尾、頭、權(quán)值）：
0 1 1
0 2 1
2 0 1
2 3 1
3 0 1
3 1 1
3 2 1
輸出各個(gè)頂點(diǎn)出度、入度信息：
for(int i=0;i<4;i++){
cout<<"從"<<i<<"出發(fā)的邊："<<endl;
EdgeNode* p=vn[i].firstout;
while(p!=NULL){
cout<<i<<"-->"<<p->head<<endl;
p=p->tlink;
}
cout<<"到達(dá)"<<i<<"的邊："<<endl;
EdgeNode* q=vn[i].firstin;
while(q!=NULL)
cout<<q->tail<<"-->"<<i<<endl;
q=q->hlink;
}
}
十字鏈表存儲(chǔ)圖示如下：
從上圖中可以看出，邊結(jié)點(diǎn)tailvex值相同的為以該頂點(diǎn)為尾的邊的集合，以鏈表方式存儲(chǔ)；headvex相同的為以該頂點(diǎn)為頭的邊的集合，以鏈表方式存儲(chǔ)。
其實(shí)，我們也可以根據(jù)自己需要靈活設(shè)計(jì)頂點(diǎn)和邊的結(jié)構(gòu)體來(lái)存儲(chǔ)圖，以達(dá)到解決某特定問(wèn)題的目的。所以，數(shù)據(jù)結(jié)構(gòu)決定了算法，選擇好的數(shù)據(jù)結(jié)構(gòu)可以減輕算法的壓力。
