【数据结构】十字链表

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

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

十字链表

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

基本概念

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

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

【数据结构】十字链表

其中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)


相关推荐

  • Centos 安装图形界面与远程使用「建议收藏」

    Centos 安装图形界面与远程使用「建议收藏」Centos安装图形界面与远程登录使用(1)图形界面安装在联网的情况下使用yum命令安装即可需要安装xwindow服务与desktop桌面,不分先后,命令如下:yumgroupinstall”Desktop”yumgroupinstall”XWindowSystem”最后启动输入命令startXvnc

  • struts2拦截器详解_拦截和修改tcp数据

    struts2拦截器详解_拦截和修改tcp数据Struts2中的拦截器和servelt中的过滤器是非常的相似的。如果学过过滤器的话,肯定能够感觉的到,尽管有些微的不同。可是struts2的拦截器到底如何使用呢,为什么会有这些配置呢?接下来一一来看。 过滤器和拦截器是非常相似的,过滤器publicinterfaceFilter接口里面有三个方法: init(FilterConfigfilterConfig),des

  • 移动端开发规范

    移动端开发规范移动端开发规范引言:最近得空,整理一些平时工作中要求的开发规范,浅薄之处还请大家多指教。目录移动端开发规范代码规范基本原则代码清晰一致性通用规范类命名方法命名变量命名常量命名枚举类型命名图片命名通用规范通用设计规范开屏页版本号版本检查开屏页广告推送通用测试用例及处理规范规范用例数据埋点规范…

  • isnotempty和isnotnull_isannotationpresent()用法

    isnotempty和isnotnull_isannotationpresent()用法转自:http://www.zhenhua.org/article.asp?id=625 isNotEmpty将空格也作为参数,isNotBlank则排除空格参数参考QuoteStringUtils方法的操作对象是java.lang.String类型的对象,是JDK提供的String类型操作方法的补充,并且是null安全的(即如果输入参数String为null则

  • python用冒泡法排序_数组冒泡排序c语言函数

    python用冒泡法排序_数组冒泡排序c语言函数arr=[7,4,3,67,34,1,8].defbubble_sort:最近在学习Python,下面是我的一些笔记冒泡排序实现思路:使用双重for循环,内层变量为i,外层为j,在内层循环中不断的比较相邻的两个值(i,i+1)的大小,如果i+1的值大于i的值,交换两者位置,每循环一次,外层的j增加1,等到j等于n-1的时候,结束循环第一次看不懂很正常,不要灰心,下面是使用代码的实现arr=…

    2022年10月16日
  • c语言opencv读取图像_matlab读取一幅图像并显示

    c语言opencv读取图像_matlab读取一幅图像并显示函数cv2.imread()用于从指定的文件读取图像OpenCV完整例程200篇01.图像的读取(cv2.imread)02.图像的保存(cv2.imwrite)03.图像的显示(cv2.imshow)07.图像的创建(np.zeros)08.图像的复制(np.copy)09.图像的裁剪(cv2.selectROI)10.图像的拼接(np.hstack)……………

发表回复

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

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