在圖的鄰接鏈表之后，我們對(duì)一個(gè)有向圖，想建立完全的關(guān)系邏輯，我們就需要生成兩份鄰接鏈表，一份記錄每個(gè)頂點(diǎn)的出度，一份記錄每個(gè)頂點(diǎn)的入度，這無(wú)疑是產(chǎn)生了一定的浪費(fèi)，所以十字鏈表圖就出現(xiàn)了。

十字鏈表圖是可以記錄每一個(gè)頂點(diǎn)的出度與入度的，其實(shí)一開(kāi)始我學(xué)習(xí)這個(gè)結(jié)構(gòu)的時(shí)候，我發(fā)現(xiàn)不是特別能理解其中的邏輯，后來(lái)才發(fā)現(xiàn)，十字鏈表圖就是兩張鄰接鏈表的集合體，每當(dāng)我們新建邊<Vi,Vj>的時(shí)候，便對(duì)這個(gè)邊進(jìn)行兩次頭插（將該邊插入頂點(diǎn)的出度鏈表與入度鏈表），就可以得到一個(gè)以Vi為弧尾的出度，一個(gè)以Vj為弧頭的入度。

具體代碼實(shí)現(xiàn)：

//定義邊鏈表結(jié)構(gòu)
struct crossShapedMapSide
{
    crossShapedMapSide* firstIn,*firstOut;    
    int indexHead,indexTail;    //表明這條邊的弧頭弧尾
};

//定義表頭數(shù)據(jù)結(jié)構(gòu)
struct crossShapedMapHead
{
    char value;  
//指向兩張不同的鄰接表，一個(gè)是以該頂點(diǎn)為弧尾的出度，一個(gè)是以該頂點(diǎn)為弧頭的入度
    crossShapedMapSide* firstIn,*firtstOut;
};

//初始化邊
crossShapedMapSide* initMapSide(int indexTail,int indexHead)
{
    crossShapedMapSide* mapSide = new crossShapedMapSide;
    mapSide->firstIn = NULL;
    mapSide->firstOut = NULL;
    mapSide->indexHead = indexHead;
    mapSide->indexTail = indexTail;
    return mapSide;
}

//頭插法，兩次插入邊
void insertMapSide(crossShapedMapHead (&mapHead) [SIZE],crossShapedMapSide* side)
{
//將該邊插入以該邊的弧尾為頂點(diǎn)的出度鏈表
    side->firstOut = mapHead[side->indexTail].firtstOut;
    mapHead[side->indexTail].firtstOut = side;

//將該邊插入以該邊的弧頭為頂點(diǎn)的入度鏈表
    side->firstIn = mapHead[side->indexHead].firstIn;
    mapHead[side->indexHead].firstIn = side;
}

//初始化表頭數(shù)據(jù)
void initMapHead(crossShapedMapHead (&mapHead)[SIZE])
{
    char ch;
    for(int i=0;i<SIZE;i++)
    {
        cin >> ch;
        mapHead[i].value = ch;
        mapHead[i].firstIn = NULL;
        mapHead[i].firtstOut = NULL;
    }
}

//輸入邊集，生成十字鏈表圖
void creataCrossShapedMap(crossShapedMapHead (&mapHead)[SIZE])
{
    int sideCount,i,j;
    cout << "請(qǐng)輸入邊集大小" << endl;
    cin >> sideCount;
    for(int k=0;k<sideCount;k++)
    {
        cout << "請(qǐng)輸入邊<Vi,Vj>" << endl;
        cin >> i >> j;
        crossShapedMapSide* side = initMapSide(i,j);
        insertMapSide(mapHead);
    }
}

其實(shí)十字鏈表圖的建立過(guò)程就是一條邊，兩次插入鄰接表的過(guò)程，在理解了這個(gè)之后，十字鏈表圖的建立就很簡(jiǎn)單了。