圖的存儲方式很多，常用的有鄰接矩陣、鄰接表、逆鄰接表、十字鏈表、鏈式前向星等，鄰接表和逆鄰接表采用數組和鏈表方式存儲，程序代碼相對容易，鄰接表求某頂點的出度容易但求入度較麻煩，逆鄰接表求某頂點的入度容易但求出度較麻煩，為了達到魚和熊掌兼得的效果，人們發明了十字鏈表的存儲方式。
在十字鏈表中，頂點設計為一種結構體，并采用一維數組存儲頂點。頂點結構體含有三個域，data存儲頂點名稱（序號），firstin存儲以該頂點為頭的第一個邊的結點，firstout存儲以該頂點為尾的第一個邊的結點。
邊設計為一種結構體，采用鏈表方式存儲。邊的結構體含有五個域，tailvex存儲該邊的尾頂點的名稱（序號），headvex存儲該邊的頭頂點的名稱（序號），hlink存儲頭相同的下一條邊的結點，tlink存儲尾相同的下一條邊的結點，info存儲邊的信息（如權值）。
下面以一個有向圖為例來編寫代碼：
首先定義邊結構體和頂點結構體：
struct EdgeNode{
int tail;
int head;
EdgeNode* hlink;
EdgeNode* tlink;
int info;
};
struct VerNode{
int num;
EdgeNode* firstin;
EdgeNode* firstout;
};
在main程序中開兩個數組，一個存儲頂點結點，一個存儲邊結點：
VerNode vn[4];
EdgeNode en[7];
初始化頂點：
for(int i=0;i<4;i++){
vn[i].num=i;
vn[i].firstin=NULL;
vn[i].firstout=NULL;
}
輸入邊的信息（增加新的邊結點時，鏈表前用前插方式，這樣比較方便）：
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];
}
對于上圖，輸入邊的數據（尾、頭、權值）：
0 1 1
0 2 1
2 0 1
2 3 1
3 0 1
3 1 1
3 2 1
輸出各個頂點出度、入度信息：
for(int i=0;i<4;i++){
cout<<"從"<<i<<"出發的邊："<<endl;
EdgeNode* p=vn[i].firstout;
while(p!=NULL){
cout<<i<<"-->"<<p->head<<endl;
p=p->tlink;
}
cout<<"到達"<<i<<"的邊："<<endl;
EdgeNode* q=vn[i].firstin;
while(q!=NULL)
cout<<q->tail<<"-->"<<i<<endl;
q=q->hlink;
}
}
十字鏈表存儲圖示如下：
從上圖中可以看出，邊結點tailvex值相同的為以該頂點為尾的邊的集合，以鏈表方式存儲；headvex相同的為以該頂點為頭的邊的集合，以鏈表方式存儲。
其實，我們也可以根據自己需要靈活設計頂點和邊的結構體來存儲圖，以達到解決某特定問題的目的。所以，數據結構決定了算法，選擇好的數據結構可以減輕算法的壓力。
