#include <iostream>

using namespace std;
const int MAXVEX=100;    
typedef struct EdgeNode       /*十字链表边结点*/
{
    int tailvex,headvex;
    EdgeNode *headlink,*taillink;
}EdgeNode;
typedef struct VertexNode   /*十字链表顶点*/
{
    int data;
    EdgeNode *firstin,*firstout;
}VertexNode,AdjList[MAXVEX];
typedef struct Graph       /*十字链表逻辑图的初始状态*/
{
    AdjList adjlist;
    int numEdges,numVertexes;
}Graph;
void CreateGraph(Graph *G)         /*创建十字链表*/
{
    cout<<"请输入边数和顶点数："<<endl;
    cin>>G->numEdges>>G->numVertexes;   //输入十字链表的边、顶点
    for(int i=0;i<G->numVertexes;i++)   //初始化十字链表的顶点
    {
        cout<<"请输入顶点信息:"<<endl;
        cin>>G->adjlist[i].data;
        G->adjlist[i].firstin=NULL;
        G->adjlist[i].firstout=NULL;
    }
    for(int k=0;k<G->numEdges;k++)    /*使用头插法链接顶点的出边表、入边表*/
    {
        int i,j;
        cout<<"请输入边的相关信息."<<endl;
        cout<<"弧尾结点:";
        cin>>i;
        cout<<"弧头结点:";
        cin>>j;
        EdgeNode* e=new EdgeNode;
        e->tailvex=i;
        e->headvex=j;
        e->taillink=G->adjlist[i].firstout;
        G->adjlist[i].firstout=e;
        e->headlink=G->adjlist[j].firstin;
        G->adjlist[j].firstin=e;
    }
}
void PrintGraph(Graph *G)
{
    for(int i=0;i<G->numEdges;i++)
    {
        cout<<"顶点："<<G->adjlist[i].data<<endl;
        EdgeNode *p=G->adjlist[i].firstout;
        while(p!=NULL)
        {
            cout<<"相关边信息弧尾:"<<p->tailvex<<"弧头:"<<p->headvex<<endl;
            p=p->taillink;
        }
        p=G->adjlist[i].firstin;
        while(p!=NULL)
        {
            cout<<"相关边信息弧尾:"<<p->tailvex<<"弧头:"<<p->headvex<<endl;
            p=p->headlink;
        }
    }
}
int main()
{
    Graph* G=new Graph;
    CreateGraph(G);
    PrintGraph(G);
    return 0;
}

实例.png

实例代码验证.png

时间复杂度

O(n+e)

疑问

十字链表顶点在链接它的出边表、入边表时是如何链接的，又如何保证了它的正确性？还有头插法在链接时一定会保证它的正确性么？

解答

十字链表的逻辑结构是由顶点表与边表组成的。顶点表其实表达了这样一个含义：这个顶点所代表的集合里放着它的出边表与入边表。边表中的结构中放置了边的顶点信息，同时也设置了边的方向。边表中的尾指针、头指针均分别会指向与自身尾结点、头结点一致的边表。这确保了弧尾或弧头一致的边会放在一个集合里。而正好顶点表中也有两个这样的集合，只要确保顶点表的出边集合指向它的出边，入边集合指向入边就行。
简而言之，就是每个顶点下都有两个集合，让各自的边放到对应的集合里就行。
头插法的正确性可以采用数学归纳法证明：
假设顶点表存在，给定一个起点，我们设起点时边表结点为0个；
当为0时，进行头插，发现正确插入；
假设为第n个结点时，头插正确插入。
然后你会发现我们如何从第n个边表结点推出第n+1个边表节点使用头插的正确性。
我们可以转换命题为：对于第任何个边表结点，进行头插时，顶点指向它，它指向未插入时的第二个。
当n=0时，符合条件。
假设n=k时符合条件，令n=k+1进行头插，同样符合条件。
因而头插法的正确性被证明。