數據庫十字鏈表有什么優點

本篇內容主要講解“數據庫十字鏈表有什么優點”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“數據庫十字鏈表有什么優點”吧!

1. 引言：

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

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

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

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

2.十字鏈表存儲結構：

頂點表結點結構：

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

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

邊表結點結構：

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

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

headlink：指入邊表指針域。

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

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

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

3.十字鏈表的優點：

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

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

2.）十字鏈表創建圖算法的時間復雜度和鄰接表是相同的。

十字鏈表

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;    
  
    }  
}

到此，相信大家對“數據庫十字鏈表有什么優點”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！