圖存儲3-十字連結清單

1. 引言：

對于有向圖來說，鄰接表是有缺陷的：

鄰接表：關心了出度問題，想了解入度就必須要周遊整個圖才知道。

逆鄰接表：解決了入度，卻不了解出度的情況。

能否把鄰接表和逆鄰接表結合起來呢？答案就是：使用十字連結清單。

2.十字連結清單存儲結構：

頂點表結點結構：

firstin：表示入邊表頭指針，指向該頂點的入邊表中第一個結點。//新加入的

firstout：表示出邊表頭指針，指向該頂點的出邊表中的第一個結點。//跟 鄰接表中的 頂點一樣

邊表結點結構：

tailvex：指弧起點在頂點表的下标。

headvex：指弧終點在頂點表中的下标。//跟鄰接表中的 adjvex 一樣

headlink：指入邊表指針域。

taillink：指邊表指針域。//跟鄰接表中的next 一樣；

如果是網，還可以再增加一個weight域來存儲權值。   

藍線表示出度，紅線表示入度 

3.十字連結清單的優點：

1.）十字連結清單是把鄰接表和逆鄰接表整合在一起，這樣既容易找到以Vi為尾的弧，也容易找到以Vi為頭的弧，

因而容易求的頂點的出度和入度。

十字連結清單

typedef char Vtype //頂點類型  
typedef int Etype //權值類型  
#definde MAXV 100;  
typedef struct edgeNode //邊表節點  
{ 
    int tailvex; //新加入的 
    int headvex; //鄰接點 存儲該頂點對應的下标
    Etype weight;//邊 權值  
    struct edgeNode *headllink; //新加入的 
    struct edgeNode *taillink;  
}EdgeNode;  
  
typedef struct Vnode //頂點表 節點  
{  
    Vtype data;  
    EdgeNode* firstInEdge; // 入度
    EdgeNode* firstOutEdge;// 出度
}VNODE; //  
  
typedef struct  
{  
    VNODE adjlist[MAXV];  
    int numV;//目前頂點數  
    int numE;//目前邊數  
}GraphAdjList;    
  
void CreateALGraph(GraphAdjList* G)  
{  
    int i,j,k;  
    EdgeNode* e= NULL;  
    cout<<輸入頂點數";  
    cin>>G->numV;  
    cout<<輸入邊數";  
    cin>>G->numE;  
    for(i=0;i<G->numV;i++)//建立頂點資訊  
    {  
	cin >> G->adjlist[i].data; //輸入頂點資訊  
	G->adjlist[i].firstOutEdge = NULL; //邊表節點 為空
	G->adjlist[i].firstInEdge = NULL; //邊表節點 為空
    }  
    for(k=0;k<numE;k++)//建立邊資訊  
    {  
	cout<<"輸入邊的開始";    
	cin>>i;    
	cout<<"輸入邊的結尾";    
	cin>>j;  
          
	e = new EdgeNode; // 
	
	e->tailvex = i; //新加入的 弧的起點  入度
	e->headlink = G->adjlist[j].firstInEdge; //新的
	G->adjlist[j].firstInEdge = e;//新的
	
	e->headvex = j;  // 原來的 e->adjvex
	e->taillink = G->adjlist[i].firstOutEdge; //原來的
	G->adjlist[i].firstOutEdge = e;    
  
    }  
}