【数据结构】十字链表

【数据结构】十字链表介绍了有向图的链式存储结构:十字链。

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

十字链表

上篇文章讲解了图的邻接表的链式存储方式,这篇文章讲解图的十字链存储方式。

基本概念

十字链表是为了便于求得图中顶点的度(出度和入度)而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。

在十字链表存储结构中,有向图中的顶点的结构如下所示:

【数据结构】十字链表

其中data表示顶点的具体数据信息,而firstIn则表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该顶点为弧尾的第一个弧节点。为了表示有向图中所有的顶点,采用一个顶点数组存储每一个结点,如下图所示。

【数据结构】十字链表

另外,在十字链表存储结构中,有向图中的每一条弧都有一个弧结点与之对应,具体的弧结点结构如下所示:

【数据结构】十字链表

其中的tailVex表示该弧的弧尾顶点在顶点数组xList中的位置,headVex表示该弧的弧头顶点在顶点数组中的位置。hLink则表示指向弧头相同的下一条弧,tLink则表示指向弧尾相同的下一条弧。

从十字链表的数据结构来看,每一个顶点对应两个链表:以该顶点为弧尾的弧结点所组成的链表以及以该顶点为弧头的弧结点所组成的链表。

如下图所示的一个有向图:

【数据结构】十字链表

其对应的顶点以及弧结点如下所示。拿结点A说明,该结点对应两个链表(绿色和黄色标记的)。绿色链表表示以结点A为弧头的弧组成的链表。黄色链表表示以结点A为弧尾的弧组成的链表。

【数据结构】十字链表

基本操作

1、创建图的十字链表

Status createDG(OLGraph &G, int vexNum, int arcNum){
	G.vexNum = vexNum;
	G.arcNum = arcNum;

	for(int i = 0; i<G.vexNum; i++){
		cin>>G.xList[i].data;
		G.xList[i].firstIn = NULL;
		G.xList[i].firstOut = NULL;
	}//初始化

	for(int i = 0; i<G.arcNum; i++){
		vexNode node1, node2;
		cout<<"please input two nodes of "<<i+1<<"-th arc"<<endl;
		cin>>node1.data>>node2.data;

		insertArc(G, node1, node2); 
	}
	return 1;
}

测试结果:

如下图所示首先输入四个顶点:A、B、C、D,然后输入7条弧。

【数据结构】十字链表

既可以构建如下的有向图。

【数据结构】十字链表

2、按照十字链表形式打印图

Status printDG(OLGraph &G){
	for(int i = 0; i<G.vexNum; i++){
		arcBox *ptail = G.xList[i].firstOut;
		arcBox *phead = G.xList[i].firstIn;

		//打印以结点i为弧尾的链
		cout<<"以结点"<<i<<"为弧尾的链 "<<G.xList[i].data;
		while(ptail){
			cout<<"-->"<<"|"<<ptail->tailVex<<"|"<<ptail->headVex;
			ptail = ptail-> tLink;
		}
		cout<<"-->NULL"<<endl;

		//打印以结点i为弧头的链

		cout<<"以结点"<<i<<"为弧头的链 "<<G.xList[i].data;
		while(phead){
			cout<<"-->"<<"|"<<phead->tailVex<<"|"<<phead->headVex;
			phead = phead->hLink;
		}
		cout<<"-->NULL"<<endl;
	}
	return 1;
}

测试结果:

每一个顶点对应两个链表(以该结点为弧头的链表和以该结点位弧尾的链表),分别将其打印出来。

【数据结构】十字链表

3、向图中插入一个结点

Status insertNode(OLGraph &G, vexNode node){

	G.xList[G.vexNum].data = node.data;
	G.xList[G.vexNum].firstIn = NULL;
	G.xList[G.vexNum].firstOut = NULL;
	G.vexNum = G.vexNum + 1;
	return 1;
}

测试结果:

向原来的有向图插入一个新的结点E。新插入的节点没有与之前图中的顶点建立弧,因此其打印结果如下所示。

【数据结构】十字链表

此时有向图变成了:

【数据结构】十字链表

4、向图中结点之间插入一条弧

void insertArcAction(OLGraph &G, int index1, int index2){

	arcBox* pArc = new arcBox[1];
	pArc->tailVex = index1;
	pArc->headVex = index2;
	pArc->info = NULL;

	arcBox *ptail = G.xList[index1].firstOut;
	arcBox *phead = G.xList[index2].firstIn;

	if(!ptail){pArc->tLink = NULL;}
	else{pArc->tLink = ptail;}

	if(!phead){pArc->hLink = NULL;}
	else{pArc->hLink = phead;}

	G.xList[index1].firstOut = pArc;//链头部插入弧结点
	G.xList[index2].firstIn = pArc;
}

Status insertArc(OLGraph &G, vexNode node1, vexNode node2){

	int index1 = locateVertex(G, node1);
	int index2 = locateVertex(G, node2);

	insertArcAction(G, index1, index2);
	return 1;
}

测试结果:

插入一条结点B到结点C的弧。再次打印该有向图时,结果如下所示。

【数据结构】十字链表

此时有向图变成了:

【数据结构】十字链表

5、删除一条弧

void deleteOutArcAction(OLGraph &G, int index1, int index2){
	arcBox *cur = G.xList[index1].firstOut;
	arcBox *pre = cur;

	int count = 0;
	if(!cur)
		return;
	else{
		while(cur){
			count++;
			if(cur->headVex == index2)
				break;
			pre = cur;
			cur = cur->tLink;
		}
	}
	if(!cur)
		return;//该结点没有对应的弧
	else if(count <=1)
		G.xList[index1].firstOut = pre->tLink;//删除第一个弧结点
	else
		pre->tLink = cur->tLink;//删除非第一个弧结点
}

void deleteInArcAction(OLGraph &G, int index1, int index2){
	arcBox *cur = G.xList[index2].firstIn;
	arcBox *pre = cur;

	int count = 0;
	if(!cur)
		return;
	else{
		while(cur){
			count++;
			if(cur->tailVex == index1)
				break;
			pre = cur;
			cur = cur->hLink;
		}
	}
	if(!cur)
		return;//该结点没有对应的弧
	else if(count <=1)
		G.xList[index2].firstIn = pre->hLink;
	else
		pre->hLink = cur->hLink;
}

Status deleteArc(OLGraph &G, vexNode node1, vexNode node2){
	//删除从结点1到结点2的弧(有方向)
	int index1 = locateVertex(G, node1);
	int index2 = locateVertex(G, node2);

	deleteOutArcAction(G, index1, index2);//删除两条链表里面的值
	deleteInArcAction(G, index1, index2);

	return 1;
}

测试结果:

删除从结点A到结点B的弧。重新打印该有向图,结果如下所示:

【数据结构】十字链表

此时有向图变成了:

【数据结构】十字链表

6、删除一个顶点

Status deleteNode(OLGraph &G, vexNode node){
	//删除结点后,该xList顶点数组中该结点后面的结点不前移,而只是将该被删除的结点的data设置成为一个较大的值
	int index = locateVertex(G, node);

	for(int i = 0; i<G.vexNum; i++){
		if(i == index)
			continue;
		else{
			deleteArc(G, G.xList[index], G.xList[i]);//删除以该结点为弧尾的弧
			deleteArc(G, G.xList[i], G.xList[index]);//删除以该结点为弧头的弧
		}
	}
	G.xList[index].data = '0';//置'0'表示该结点被删除
	G.xList[index].firstIn = NULL;
	G.xList[index].firstOut = NULL;

	return 1;
}

测试结果:

删除结点D,重新打印该有向图,其结果如下所示(只剩下3条弧,4个有效结点,结点D被删除后,该结点的内容变从‘D’变为‘0’):

【数据结构】十字链表

测试有向图变成了:

【数据结构】十字链表

7、全部代码

// 十字链表.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int infoType;
typedef char vertexType;

typedef struct arcBox{
	int tailVex, headVex;
	struct arcBox *hLink, *tLink;
	infoType *info;
}arcBox;//弧结点

typedef struct vexNode{
	vertexType data;
	arcBox *firstIn, *firstOut;
}vexNode;//顶点节点

typedef struct{
	vexNode xList[MAX_VERTEX_NUM];
	int vexNum, arcNum;
}OLGraph;//十字链

int locateVertex(OLGraph &G, vexNode node){
	int index = -1;
	for(int i = 0; i<G.vexNum; i++){
		if(node.data == G.xList[i].data){
			index = i;
			break;
		}
	}
	return index;
}

void insertArcAction(OLGraph &G, int index1, int index2);
Status insertArc(OLGraph &G, vexNode node1, vexNode node2);

Status createDG(OLGraph &G, int vexNum, int arcNum){
	G.vexNum = vexNum;
	G.arcNum = arcNum;

	for(int i = 0; i<G.vexNum; i++){
		cin>>G.xList[i].data;
		G.xList[i].firstIn = NULL;
		G.xList[i].firstOut = NULL;
	}//初始化

	for(int i = 0; i<G.arcNum; i++){
		vexNode node1, node2;
		cout<<"please input two nodes of "<<i+1<<"-th arc"<<endl;
		cin>>node1.data>>node2.data;

		insertArc(G, node1, node2); 
	}
	return 1;
}

Status printDG(OLGraph &G){
	for(int i = 0; i<G.vexNum; i++){
		arcBox *ptail = G.xList[i].firstOut;
		arcBox *phead = G.xList[i].firstIn;

		//打印以结点i为弧尾的链
		cout<<"以结点"<<i<<"为弧尾的链 "<<G.xList[i].data;
		while(ptail){
			cout<<"-->"<<"|"<<ptail->tailVex<<"|"<<ptail->headVex;
			ptail = ptail-> tLink;
		}
		cout<<"-->NULL"<<endl;

		//打印以结点i为弧头的链

		cout<<"以结点"<<i<<"为弧头的链 "<<G.xList[i].data;
		while(phead){
			cout<<"-->"<<"|"<<phead->tailVex<<"|"<<phead->headVex;
			phead = phead->hLink;
		}
		cout<<"-->NULL"<<endl;
	}
	return 1;
}

void insertArcAction(OLGraph &G, int index1, int index2){

	arcBox* pArc = new arcBox[1];
	pArc->tailVex = index1;
	pArc->headVex = index2;
	pArc->info = NULL;

	arcBox *ptail = G.xList[index1].firstOut;
	arcBox *phead = G.xList[index2].firstIn;

	if(!ptail){pArc->tLink = NULL;}
	else{pArc->tLink = ptail;}

	if(!phead){pArc->hLink = NULL;}
	else{pArc->hLink = phead;}

	G.xList[index1].firstOut = pArc;//链头部插入弧结点
	G.xList[index2].firstIn = pArc;
}

Status insertArc(OLGraph &G, vexNode node1, vexNode node2){

	int index1 = locateVertex(G, node1);
	int index2 = locateVertex(G, node2);

	insertArcAction(G, index1, index2);
	return 1;
}

Status insertNode(OLGraph &G, vexNode node){

	G.xList[G.vexNum].data = node.data;
	G.xList[G.vexNum].firstIn = NULL;
	G.xList[G.vexNum].firstOut = NULL;
	G.vexNum = G.vexNum + 1;
	return 1;
}

Status deleteArc(OLGraph &G, vexNode node1, vexNode node2);

Status deleteNode(OLGraph &G, vexNode node){
	//删除结点后,该xList顶点数组中该结点后面的结点不前移,而只是将该被删除的结点的data设置成为一个较大的值
	int index = locateVertex(G, node);

	for(int i = 0; i<G.vexNum; i++){
		if(i == index)
			continue;
		else{
			deleteArc(G, G.xList[index], G.xList[i]);//删除以该结点为弧尾的弧
			deleteArc(G, G.xList[i], G.xList[index]);//删除以该结点为弧头的弧
		}
	}
	G.xList[index].data = '0';//置'0'表示该结点被删除
	G.xList[index].firstIn = NULL;
	G.xList[index].firstOut = NULL;

	return 1;
}

void deleteOutArcAction(OLGraph &G, int index1, int index2){
	arcBox *cur = G.xList[index1].firstOut;
	arcBox *pre = cur;

	int count = 0;
	if(!cur)
		return;
	else{
		while(cur){
			count++;
			if(cur->headVex == index2)
				break;
			pre = cur;
			cur = cur->tLink;
		}
	}
	if(!cur)
		return;//该结点没有对应的弧
	else if(count <=1)
		G.xList[index1].firstOut = pre->tLink;//删除第一个弧结点
	else
		pre->tLink = cur->tLink;//删除非第一个弧结点
}

void deleteInArcAction(OLGraph &G, int index1, int index2){
	arcBox *cur = G.xList[index2].firstIn;
	arcBox *pre = cur;

	int count = 0;
	if(!cur)
		return;
	else{
		while(cur){
			count++;
			if(cur->tailVex == index1)
				break;
			pre = cur;
			cur = cur->hLink;
		}
	}
	if(!cur)
		return;//该结点没有对应的弧
	else if(count <=1)
		G.xList[index2].firstIn = pre->hLink;
	else
		pre->hLink = cur->hLink;
}

Status deleteArc(OLGraph &G, vexNode node1, vexNode node2){
	//删除从结点1到结点2的弧(有方向)
	int index1 = locateVertex(G, node1);
	int index2 = locateVertex(G, node2);

	deleteOutArcAction(G, index1, index2);//删除两条链表里面的值
	deleteInArcAction(G, index1, index2);

	return 1;
}

int _tmain(int argc, _TCHAR* argv[])
{	
	int vexNum = 4;
	int arcNum = 7;

	OLGraph G;
	
	cout<<"Try to create a Orthogonal List of a graph..."<<endl;
	createDG(G, vexNum, arcNum);
	cout<<"Try to print the Orthogonal List of the very graph..."<<endl;
	printDG(G);
	
	cout<<"Try to insert a node into the graph..."<<endl;
	vexNode node;
	cout<<"   please input the data of the node to insert:"<<endl;
	cin>>node.data;
	insertNode(G, node);
	printDG(G);

	cout<<"Try to insert a arc into the graph..."<<endl;
	vexNode node1, node2;
	cout<<"   please choose two node:"<<endl;
	cin>>node1.data>>node2.data;
	insertArc(G, node1, node2);
	printDG(G);

	cout<<"Try to delete the arc between two nodes..."<<endl;
	vexNode node3, node4;
	cout<<"   please choose a arc with specifing two nodes:"<<endl;
	cin>>node3.data>>node4.data;
	deleteArc(G, node3, node4);
	printDG(G);

	cout<<"Try to delete a node of the graph..."<<endl;
	vexNode node5;
	cout<<"   please choose a node:"<<endl;
	cin>>node5.data;
	deleteNode(G, node5);
	printDG(G);

	system("pause");

	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150305.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 微信小程序跳转到其他网页(外部链接)

    微信小程序跳转到其他网页(外部链接)个人类型和海外类型的小程序不支持web-view标签也就是说个人申请的小程序,就别想跳转了!!!!1.开发的时候,我们难免碰到要跳转到其他网页中去那该怎么实现呢?2.例如我想点击一个按钮,跳转到百度(百度的网页还是在小程序中打开)3.wxml1.index.wxml(按钮页面)&lt;viewclass=’wrapper’&gt;&lt;b…

  • matlab产生高斯白噪声

    matlab产生高斯白噪声函数介绍matlab里和随机数有关的函数:(1)rand:产生均值为0.5、幅度在0~1之间的伪随机数。(2)randn:产生均值为0、方差为1的高斯白噪声。(3)randperm(n):产生1到n的均匀分布随机序列。(4)normrnd(a,b,c,d):产生均值为a、方差为b大小为cXd的随机矩阵。rand:返回一个在区间(0,1)内均匀分布的随机数。rand(n):生成0到1之间的n阶(n×n)随机数方阵。rand(m,n):生成0到1之间的m×n的随机数矩阵。

    2022年10月21日
  • git每次push和pull都要输入密码

    git每次push和pull都要输入密码

  • 查看linux系统版本和内核版本_目前linux最新内核版本

    查看linux系统版本和内核版本_目前linux最新内核版本1.查看内核版本$uname-srLinux4.15.11-1.el7.elrepo.x86_64$uname-aLinuxlocalhost.localdomain4.15.11-1.el7.elrepo.x86_64#1SMPMonMar1911:46:06EDT2018x86_64x86_64x86_64GNU/Linux$cat/pro…

  • 指纹识别模组厂家_指纹识别模块原理

    指纹识别模组厂家_指纹识别模块原理不管指纹识别的流程和传感器原理发展得有多快,如果需要商用到手机及终端设备这种民用产品上,还是有好多问题需要克服。比如我们会看到指纹模块在正面,在背面,在侧面,其原因都是sensor性能、模组结构设计、手机ID设计以及量产工艺的限制多重因素辅助、妥协形成的。一、模组位置正面毋庸置疑,代表作当然是iPhone。其实指纹识别应用在手机上并不是APPLE首次尝的禁果,HTC、Sharp、Samsung都有过

  • siamfc代码解读_SiamFC算法改进思路「建议收藏」

    siamfc代码解读_SiamFC算法改进思路「建议收藏」视频追踪问题中,目标通常是连续可微的。SiamFC利用全卷积孪生网络结构对搜索域和样本图像进行相似度匹配,实现追踪目标。本文分析了SiamFC在vot2015数据集上的追踪结果,总结出以下问题,并提出针对性的改进方案。表现鲁棒小范围晃动运动模糊短时局部遮挡重点问题光照变化视频中白色猫由亮处转入阴影中,跟踪结果开始出现偏差。光照条件较差,而且目标的衣服为黑色,与背景相似。特征不够明显。形变、尺度变换…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号