#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进行头插，同样符合条件。
因而头插法的正确性被证明。
