邻接表&十字链表

大家好，又见面了，我是你们的朋友全栈君。

邻接表：

每一行都可以看成一个单链表，第一行中，v0-1-3可以得到，v0的出度为v1和v3。

邻接表完整代码:

#include <iostream>
using namespace std;

const int MAX_V = 15;

//边节点
typedef struct Edge_node {
    char data;
    Edge_node *next;
}Enode,*pEnode;

//表节点
typedef struct List_node {
    char data;
    Edge_node *firstEdge;
}Lnode, *pLnode;


int main()
{
    void AddEdge( char v1, char v2, pLnode list, int V );
    void display( pLnode list, int V );
    void clear( pLnode list, int V);

    int V,E;
    cout << "input vertex number and edge number:\n";//输入顶点数和边数
    cin >> V >> E;

    Lnode list[MAX_V];//建立数组
    for( int i=0; i<V; ++i ){
        list[i].firstEdge = NULL;
    }

    cout << "input vertex:\n";//输入顶点
    for( int i=0; i<V; ++i )
        cin >> list[i].data;

    cout << "input edges, eg: a b \n";
    char v1,v2;
    for( int i=0; i<E; ++i ){

        cin >> v1 >> v2;
        AddEdge( v1, v2, list, V);
    }

    //输出
    cout <<"display:\n";
    display( list, V );

    cout << "clear:\n";
    clear( list, V );

    return 0;
}

void AddEdge( char v1, char v2, pLnode list, int V ) {

    for( int i=0; i<V; ++i ){

        if( v1==list[i].data ){
            //生成新的边节点
            pEnode newEdge = new Enode;
            newEdge->data = v2;
            newEdge->next = NULL;

            newEdge->next = list[i].firstEdge;
            list[i].firstEdge = newEdge;

            break;
        }
    }
}

void display( pLnode list, int V ){

    for( int i=0; i<V; ++i ){
        cout << list[i].data <<": ";
        pEnode p = list[i].firstEdge;
        while( p ){
            cout << p->data << ' ';
            p = p->next;
        }
        cout <<endl;
    }
}

void clear( pLnode list, int V){

    for( int i=0; i<V; ++i ){
        pEnode p = list[i].firstEdge;
        pEnode todel;
        while( NULL!=p ){
            todel = p;
            cout <<"delete is "<< todel->data << ' ';
            p = p->next;
            delete todel;
        }
        cout << endl;
    }

}

但对于有向图来说，邻接表是有缺陷的，关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度的情况。
而十字链表可以同时解决出度和入度的问题。

十字链表

重新定义表节点结构：增加了两个指针firstIn,firstOut。分别用来指向该顶点的入（出）边表中第一个结点。

firstin表示入边表头指针，指向该顶点的入边表中第一个结点；

firstout表示出边表头指针，指向该顶点的出边表中第一个结点；

tailvex是指弧起点在顶点的下标，

headvex是指弧终点在顶点表中的下标，

headlink是指入边表指针域，指向终点相同的一下条边

taillink是指出边表指针域，指向起点相同的下一条边。

对比

与邻接表相比，这里的 tailLink 指针就相当于邻接表里的那个指针，指向出度的下一个节点。而这里的 headLink 就是新增加的用来记录入度的指针。

首先，横着看：每一行都可以看出单链表，把从 firstOut 出来的串起来就是出度（类似邻接表）;
竖着看（不太明显）：从 headLink 出来的指针指向串起来，都是入度节点。

那为什么要重复存储节点信息呢？例如图中的0存了2次，1存了3次等。这是为了方便找入度节点。试想，邻接表用一个指针一个节点信息来存储方便找出度，那么要是出度入度都方便找，自然要给入度也加上一个指针（headLink）和一个数据域（tailVex）。这样当找到入度的边接节点，取出 headLink 就找到入度节点了。

将边节点结构分割：
入度：headLink + tailVex;
出度：tailLink + headVex;

十字链表代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_V = 15;
//边节点
typedef struct Edge_node {
    char tailVex,headVex;           //tailvex是指弧起点在顶点的下标，headvex是指弧终点在顶点表中的下标，
    Edge_node *tailLink, *headLink;//headlink指向弧头相同的下一条弧。taillink指向弧尾相同的下一条弧.
}Enode,*pEnode;

//表节点
typedef struct List_node {
    char data;
    Edge_node *firstIn, *firstOut;//firstin表示入边表头指针，指向该顶点的入边表中第一个结点.
}Lnode, *pLnode;

int main()
{
    void AddEdge( char v1, char v2, pLnode list, int V );
    void display( pLnode list, int V );
    void clear( pLnode list, int V);

    int V,E;
    cout << "input vertex number and edge number:\n";//输入顶点数和边数
    cin >> V >> E;

    Lnode list[MAX_V];//建立数组
    for( int i=0; i<V; ++i ){
        list[i].firstIn = NULL;
        list[i].firstOut = NULL;
    }

    //输入顶点
    cout << "input vertex:\n";
    for( int i=0; i<V; ++i )
        cin >> list[i].data;

    //输入边
    cout << "input edges, eg: a b \n";
    char v1,v2;
    for( int i=0; i<E; ++i ){

        cin >> v1 >> v2;
        AddEdge( v1, v2, list, V);
    }

    //输出
    cout <<"display:\n";
    display( list, V );

    cout << "clear:\n";
    clear( list, V );

    return 0;
}

void AddEdge( char v1, char v2, pLnode list, int V ){

    int getIndex( char x , pLnode list , int V );
    int v1_index = getIndex( v1 , list, V );
    int v2_index = getIndex( v2, list ,V );

    pEnode newEdge = new Enode;
    newEdge->tailVex = v1;
    newEdge->headVex = v2;

    //添加出度
    newEdge->tailLink = list[v1_index].firstOut;
    list[v1_index].firstOut = newEdge;

    //添加入度
    newEdge->headLink = list[v2_index].firstIn;
    list[v2_index].firstIn = newEdge;
}
int getIndex( char x, pLnode list, int V ){

    for( int i=0; i<V; ++i ){
        if( x==list[i].data )
            return i;
    }
}

void display( pLnode list, int V ){

    for( int i=0; i<V; ++i ){
        cout << list[i].data <<" out : ";
        pEnode p = list[i].firstOut;
        while( p ){
            cout << p->headVex << ' ';
            p = p->tailLink;
        }
        cout <<endl;

        cout << list[i].data <<" in : ";
        p = list[i].firstIn;
        while( p ){
            cout << p->tailVex << ' ';
            p = p->headLink;
        }
        cout <<endl;
    }

}

void clear( pLnode list, int V){

    for( int i=0; i<V; ++i ){
        pEnode p = list[i].firstOut;
        pEnode todel;
        while( NULL!=p ){
            todel = p;
            cout <<"delete is "<< todel->headVex << ' ';
            p = p->tailLink;
            delete todel;
        }
        cout << endl;
    }
}