图的存储结构——十字链表

这篇具有很好参考价值的文章主要介绍了图的存储结构——十字链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

引入(为何存在?)

数据结构分析

十字链表的示意图:

代码实现(以有向网为例,创建十字链表)

        数据结构部分:

       算法实现部分:

        测试部分:(以图8.14为例)

时间与空间复杂度分析分析:


引入(为何存在?)

        回忆邻接矩阵与邻接表的存储结构,它们都不便于求顶点的出度与入度(对于每个顶点而言,欲求其出入度,邻接矩阵需要扫描2*n次,而邻接表只易在求解其出度,欲求入度还需重新扫面整张图)。为了解决上述两者求出入度的局限性,在此引入十字链表,它可以看成邻接表与逆邻接表的结合,方便求解顶点出入度获取顶点的出入度边

数据结构分析

        十字链表的存储结构包含表头结点表弧表,与邻接表类似,是一种顺序结合链式的存储结构,因此需要有两个指针域分别指向以顶点为弧尾和以顶点为弧头的弧结点

        表头结点表是一个顺序存储结构的数组,其结点数据类型如下图所示:

十字链表,数据结构与算法,C++,链表,数据结构,算法

         分析:在表头结点中,顶点数据域存储与顶点有关的信息,本例指定为 char类型;指针域firstin指向以顶点为弧头的第一条弧,指针域firstout指向以顶点为弧尾的第一条弧。这也告诉我们,待会在创建弧<v1,v2>时,不仅需要处理v1的firstout,还需要处理v2的firstin。

        弧结点的数据类型如下图所示:

十字链表,数据结构与算法,C++,链表,数据结构,算法

         分析:弧尾结点存储该弧尾结点所在图中的位置,弧头结点同理;弧上信息指示权值等弧数据;hlink指向与该弧有相同弧头的弧结点,tlink指向与该弧有相同弧尾的弧结点。

十字链表的示意图:

十字链表,数据结构与算法,C++,链表,数据结构,算法

代码实现(以有向网为例,创建十字链表)

        数据结构部分:

//文件名尾:OLGraph.h
#pragma once
#include<iostream>
using namespace std;

#define Maxvex 100    //最大顶点数

//定义权值与顶点的信息类型
typedef int OtherInfo;
typedef char vexType;

//定义弧结点的数据结构
typedef struct ArcBox {
	int tvex, hvex;  //指向该弧的弧尾与弧头
	struct ArcBox* tlink, * hlink;    //指向与该弧有相同弧尾与弧头的弧结点
	OtherInfo w;  //弧上信息
}ArcBox;

//定义表头结点的数据结构
typedef struct VexNode {
	vexType data; //数据域
	struct ArcBox* firstin, * firstout;  //该顶点的第一条入度弧结点与出度弧结点
}VexNode;

//定义十字链表的数据结构
typedef struct OLGraph {
	VexNode xlist[Maxvex];  //表头结点表的最大容量为maxvex
	int vexnum, arcnum;    //顶点与弧的个数
}OLGraph;


//创建十字链表
void CreateUDNol(OLGraph& G);

       算法实现部分:

        注意:顶点编号从0开始

文件名为:OLGraph.cpp
#include"OLGraph.h"

void CreateUDNol(OLGraph& G)
{
	//常规操作,确定顶点数与弧数
	cout << "输入顶点个数以及弧数:>" << endl;
	cin >> G.vexnum >> G.arcnum;
	if (G.vexnum > Maxvex || G.arcnum > (G.vexnum - 1) * G.vexnum|| G.vexnum<1)
	{
		cout << "数据有误" << endl;
		return;
	}
	//将顶点数据初始化,输入顶点数据
	cout << "请输入" << G.vexnum << "个顶点的数据域:>";
	for (int i = 0;i < G.vexnum;i++)
	{
		cin >> G.xlist[i].data;
		//指针域需要初始化
		G.xlist[i].firstin = G.xlist[i].firstout = NULL;
	}
	//输入边的数据,出入度结点以及权值并连接结点
	for (int i = 0;i < G.arcnum;i++)
	{
		/*
			还有一种输入顶点数据域再找该顶点编号的输入方式,这里直接输入顶点
			编号
		*/
		cout << "请输入<v1,v2>中的顶点v1、v2编号以及该弧的权值w:>" << endl;
		//创建<v1,v2>
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		//判断合法性
		if (v1 >= G.vexnum || v2 >= G.vexnum||v2<0||v1<0||v1==v2)
		{
			i--;
			cout << "数据有误,请重新输入!" << endl;
			continue;
		}
		ArcBox* p = new ArcBox;
		p->hvex = v2;   //v2是该弧的头结点
		p->tvex = v1;   //v1是该弧的尾结点
		p->w = w;
		//连接p与其有相同出度点的弧结点
		p->tlink = G.xlist[v1].firstout;
		G.xlist[v1].firstout = p;
		//连接p与其有相同入度点的弧结点
		p->hlink = G.xlist[v2].firstin;
		G.xlist[v2].firstin = p;
	}
}

        测试部分:(以图8.14为例)

         输出各个顶点的出度与入度点:

//文件名:test.cpp
void test()
{
	OLGraph G;
	CreateUDNol(G);
	//输出每个顶点的出度点与入度点
	for (int i = 0;i < G.vexnum;i++)
	{
		cout << "该顶点的下标为:" << i << "  其数据域:" << G.xlist[i].data;
		cout << "  该顶点的出度弧:";
		ArcBox* p = G.xlist[i].firstout;
		while (p)
		{
			int node = p->hvex;
			cout << node << ": " << G.xlist[node].data << " ";
			p = p->tlink;
		}
		cout << "该顶点的入度弧:";
		p = G.xlist[i].firstin;
		while (p)
		{
			int node = p->tvex;
			cout << node << ": " << G.xlist[node].data << " ";
			p = p->hlink;
		}
		cout << endl;
	}
}


int main()
{
	test();
	return 0;
}

测试结果:

十字链表,数据结构与算法,C++,链表,数据结构,算法

时间与空间复杂度分析分析:

        空间复杂度:由于需要存储n个顶点与e条边,故空间复杂度为:O(n+e);        

        时间复杂度:就创建算法而言,时间花销主要在顶点数据与弧信息的输入,若有向网有n个顶点与e条边,那么时间复杂度为:O(n+e);就查找顶点的出入度的算法而言,由于每个顶点与每个顶点的出入弧只需要扫描一次,故时间复杂度为O(n+e),当图为稀疏图时,相比于邻接矩阵时间复杂度O(n^2)。但是当图为稠密图时,考虑到十字链表指针域的额外花销,邻接矩阵便有使用价值。

        文章来源地址https://www.toymoban.com/news/detail-757135.html

到了这里,关于图的存储结构——十字链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】数组(稀疏矩阵、特殊矩阵压缩、矩阵存储、稀疏矩阵的快速转置、十字链表)

    前几期期链接: 【数据结构】栈与队列的概念和基本操作代码实现 【数据结构】树与二叉树的概念与基本操作代码实现 k维数组的定义: k 维数组 D = { a j 1 , j 2 , . . . , j k } k维数组D={ a_{j_1, j_2, ..., j_k} } k 维数组 D = { a j 1 ​ , j 2 ​ , ... , j k ​ ​ } k 0 称为数组的维数,

    2024年04月09日
    浏览(137)
  • 西工大NOJ数据结构理论——013.以十字链表为存储结构实现矩阵相加(严5.27)

      我第一下拿到这个题目,第一反应就是先 定义好数据结构 ,然后构建好十字链表基础操作的函数,也就是“ 创插遍历 ”这些操作。下面是我的定义和函数操作。 typedef int ElemType; typedef struct OLNode{     int i,j;//行号和列号     ElemType elem;     struct OLNode *right;//右边元素 

    2023年04月26日
    浏览(83)
  • 【数据结构】数组和字符串(十):稀疏矩阵的链接存储:十字链表的矩阵操作(加法、乘法、转置)

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月08日
    浏览(56)
  • 【数据结构】数组和字符串(八):稀疏矩阵的链接存储:十字链表的创建、插入元素、遍历打印(按行、按列、打印矩阵)、销毁

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月06日
    浏览(53)
  • 数据结构——十字链表

    什么是十字链表: 十字链表(Orthogonal List) 是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图,可以达到高效的存取效果。同时,代码的可读性也会得到提升。 了解十字链表:         我们来看下面这

    2024年02月05日
    浏览(39)
  • 【数据结构】十字链表的画法

    有向边又称为弧 假设顶点 v 指向 w,那么 w 称为弧头,v 称为弧尾 顶点节点采用顺序存储 顶点节点 data:存放顶点的信息 firstin:指向以该节点为终点(弧头)的弧节点 firstout:指向以该节点为起点(弧尾)的弧节点 弧节点 tailvex:起点(弧尾)在数组中的索引 headvex:终点(

    2024年02月11日
    浏览(47)
  • 数据结构—图的存储结构

    回顾:数据的逻辑结构 集合——数据元素间除 “同属于一个集合” 外,无其他关系。 线性结构——一个对一个,如线性表、栈、队列 树形结构——一个对多个,如树 图形结构——多个对多个,如图 6.1图的定义和术语 无向图 :每条边都是 无 方向的; 有向图 :每条边都是

    2024年02月14日
    浏览(35)
  • 数据结构--图的存储结构

    第九话  数据结构之图的存储 文章目录 一、了解什么是图 二、图的定义和基本术语 三、存储结构之邻接矩阵 1.邻接矩阵的介绍 2.邻接矩阵的创建 3.主函数中实现 四、存储结构之邻接表 1.邻接表的介绍 2.邻接表的创建 3.在主函数中实现 五、总结 一切尽在图结构 图的应用非

    2024年02月07日
    浏览(52)
  • 16-数据结构-图的存储结构

    简介:主要为图的顺序存储和链式存储。其中顺序存储即邻接矩阵的画法以及代码,邻接矩阵又分为有权图和无权图,区别就是有数据的地方填权值,无数据的地方可以填0或者∞,而有权图和无权图,又细分为有向图和无向图。无向图为对称矩阵,因为没有方向可言,出度入

    2024年02月09日
    浏览(36)
  • 【数据结构】图的定义、存储

    对王道数据结构选择题做错和不清楚的题的简单纠错 一个有n个顶点和n条边的无向图一定是 有环的 一个无向图有n个顶点和n-1条边,可以使它连通单没有环,若再加一条边,则会形成环 若图中顶点数为n,则它的生成树有n-1条边,去掉一条边变成非连通图;加上一条边变成一

    2024年02月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包