十字链表图的建立

在图的邻接链表之后，我们对一个有向图，想建立完全的关系逻辑，我们就需要生成两份邻接链表，一份记录每个顶点的出度，一份记录每个顶点的入度，这无疑是产生了一定的浪费，所以十字链表图就出现了。

十字链表图是可以记录每一个顶点的出度与入度的，其实一开始我学习这个结构的时候，我发现不是特别能理解其中的逻辑，后来才发现，十字链表图就是两张邻接链表的集合体，每当我们新建边<Vi,Vj>的时候，便对这个边进行两次头插（将该边插入顶点的出度链表与入度链表），就可以得到一个以Vi为弧尾的出度，一个以Vj为弧头的入度。

具体代码实现：

//定义边链表结构
struct crossShapedMapSide
{
    crossShapedMapSide* firstIn,*firstOut;    
    int indexHead,indexTail;    //表明这条边的弧头弧尾
};

//定义表头数据结构
struct crossShapedMapHead
{
    char value;  
//指向两张不同的邻接表，一个是以该顶点为弧尾的出度，一个是以该顶点为弧头的入度
    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)
{
//将该边插入以该边的弧尾为顶点的出度链表
    side->firstOut = mapHead[side->indexTail].firtstOut;
    mapHead[side->indexTail].firtstOut = side;

//将该边插入以该边的弧头为顶点的入度链表
    side->firstIn = mapHead[side->indexHead].firstIn;
    mapHead[side->indexHead].firstIn = side;
}

//初始化表头数据
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 << "请输入边集大小" << endl;
    cin >> sideCount;
    for(int k=0;k<sideCount;k++)
    {
        cout << "请输入边<Vi,Vj>" << endl;
        cin >> i >> j;
        crossShapedMapSide* side = initMapSide(i,j);
        insertMapSide(mapHead);
    }
}

其实十字链表图的建立过程就是一条边，两次插入邻接表的过程，在理解了这个之后，十字链表图的建立就很简单了。