在图的邻接链表之后,我们对一个有向图,想建立完全的关系逻辑,我们就需要生成两份邻接链表,一份记录每个顶点的出度,一份记录每个顶点的入度,这无疑是产生了一定的浪费,所以十字链表图就出现了。
十字链表图是可以记录每一个顶点的出度与入度的,其实一开始我学习这个结构的时候,我发现不是特别能理解其中的逻辑,后来才发现,十字链表图就是两张邻接链表的集合体,每当我们新建边<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);
}
}
其实十字链表图的建立过程就是一条边,两次插入邻接表的过程,在理解了这个之后,十字链表图的建立就很简单了。
网友评论