美文网首页
十字链表图的建立

十字链表图的建立

作者: MisakaMikotoSAM | 来源:发表于2016-05-05 22:17 被阅读608次

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

    十字链表图是可以记录每一个顶点的出度与入度的,其实一开始我学习这个结构的时候,我发现不是特别能理解其中的逻辑,后来才发现,十字链表图就是两张邻接链表的集合体,每当我们新建边<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);
        }
    }
    

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

    相关文章

      网友评论

          本文标题:十字链表图的建立

          本文链接:https://www.haomeiwen.com/subject/nxfdrttx.html