您当前的位置:首页 > 电脑百科 > 数据库 > 百科

图的十字链表存储方式解析

时间:2020-07-08 09:58:34  来源:  作者:

图的存储方式很多,常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等,邻接表和逆邻接表采用数组和链表方式存储,程序代码相对容易,邻接表求某顶点的出度容易但求入度较麻烦,逆邻接表求某顶点的入度容易但求出度较麻烦,为了达到鱼和熊掌兼得的效果,人们发明了十字链表的存储方式。

在十字链表中,顶点设计为一种结构体,并采用一维数组存储顶点。顶点结构体含有三个域,data存储顶点名称(序号),firstin存储以该顶点为头的第一个边的结点,firstout存储以该顶点为尾的第一个边的结点。

图的十字链表存储方式解析

 

边设计为一种结构体,采用链表方式存储。边的结构体含有五个域,tailvex存储该边的尾顶点的名称(序号),headvex存储该边的头顶点的名称(序号),hlink存储头相同的下一条边的结点,tlink存储尾相同的下一条边的结点,info存储边的信息(如权值)。

图的十字链表存储方式解析

 

下面以一个有向图为例来编写代码:

图的十字链表存储方式解析

 

首先定义边结构体和顶点结构体:

struct EdgeNode{
    int tail;
    int head;
    EdgeNode* hlink;
    EdgeNode* tlink;
    int info;
};

struct VerNode{
    int num;
    EdgeNode* firstin;
    EdgeNode* firstout;
};

在main程序中开两个数组,一个存储顶点结点,一个存储边结点:

VerNode vn[4];
EdgeNode en[7];

初始化顶点:

for(int i=0;i<4;i++){
      vn[i].num=i;
      vn[i].firstin=NULL;
      vn[i].firstout=NULL;
}

输入边的信息(增加新的边结点时,链表前用前插方式,这样比较方便):

for(int i=0;i<7;i++){
      int tv,hv,val;
      cin>>tv>>hv>>val;
      en[i].tail=tv;
      en[i].head=hv;
      en[i].info=val;
      en[i].tlink=vn[tv].firstout;
      vn[tv].firstout=&en[i];
      en[i].hlink=vn[hv].firstin;
      vn[hv].firstin=&en[i];
}

对于上图,输入边的数据(尾、头、权值):

0 1 1
0 2 1
2 0 1
2 3 1
3 0 1
3 1 1
3 2 1

输出各个顶点出度、入度信息:

for(int i=0;i<4;i++){
      cout<<"从"<<i<<"出发的边:"<<endl; 
      EdgeNode* p=vn[i].firstout;
      while(p!=NULL){
        cout<<i<<"-->"<<p->head<<endl;
        p=p->tlink;
      }
      cout<<"到达"<<i<<"的边:"<<endl; 
      EdgeNode* q=vn[i].firstin;
      while(q!=NULL)
        cout<<q->tail<<"-->"<<i<<endl;
        q=q->hlink;
      }
}

十字链表存储图示如下:

图的十字链表存储方式解析

 

从上图中可以看出,边结点tailvex值相同的为以该顶点为尾的边的集合,以链表方式存储;headvex相同的为以该顶点为头的边的集合,以链表方式存储。

其实,我们也可以根据自己需要灵活设计顶点和边的结构体来存储图,以达到解决某特定问题的目的。所以,数据结构决定了算法,选择好的数据结构可以减轻算法的压力。



Tags:十字链表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
图的存储方式很多,常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等,邻接表和逆邻接表采用数组和链表方式存储,程序代码相对容易,邻接表求某顶点的出度容易但求入度...【详细内容】
2020-07-08  Tags: 十字链表  点击:(122)  评论:(0)  加入收藏
▌简易百科推荐
1增1.1【插入单行】insert [into] <表名> (列名) values (列值)例:insert into Strdents (姓名,性别,出生日期) values (&#39;开心朋朋&#39;,&#39;男&#39;,&#39;1980/6/15&#3...【详细内容】
2021-12-27  快乐火车9d3    Tags:SQL   点击:(2)  评论:(0)  加入收藏
最近发现还有不少做开发的小伙伴,在写存储过程的时候,在参考已有的不同的写法时,往往很迷茫, 不知道各种写法孰优孰劣,该选用哪种写法,以及各种写法的优缺点,本文以一个简单的查询...【详细内容】
2021-12-23  linux上的码农    Tags:sql   点击:(9)  评论:(0)  加入收藏
《开源精选》是我们分享Github、Gitee等开源社区中优质项目的栏目,包括技术、学习、实用与各种有趣的内容。本期推荐的HasorDB 是一个全功能数据库访问工具,提供对象映射、丰...【详细内容】
2021-12-22  GitHub精选    Tags:HasorDB   点击:(5)  评论:(0)  加入收藏
作者丨Rafal Grzegorczyk译者丨陈骏策划丨孙淑娟【51CTO.com原创稿件】您是否还在手动对数据库执行各种脚本?您是否还在浪费时间去验证数据库脚本的正确性?您是否还需要将...【详细内容】
2021-12-22    51CTO  Tags:Liquibase   点击:(4)  评论:(0)  加入收藏
场景描述:由于生产环境的表比较复杂,字段很多。这里我们做下简化,只为说明今天要聊的问题。有两张表 tab1,tab2: tab1 数据如下: tab2 数据如下: 然后给你看下,我用来统计 name=&#3...【详细内容】
2021-12-20  Bald    Tags:SQL   点击:(7)  评论:(0)  加入收藏
前言知识无底,学海无涯,知识点虽然简单,但是比较多,所以将MySQL的基础写出来,方便自己以后查找,还有就是分享给大家。一、SQL简述1.SQL的概述Structure Query Language(结构化查...【详细内容】
2021-12-16  谣言止于独立思考    Tags:SQL基础   点击:(13)  评论:(0)  加入收藏
前言作为一名测试工程师,工作中在对测试结果进行数据比对的时候,或多或少要和数据库打交道的,要和数据库打交道,那么一些常用的 SQL 查询语法必须要掌握。最近有部分做测试小伙...【详细内容】
2021-12-14  柠檬班软件测试    Tags:SQL   点击:(15)  评论:(0)  加入收藏
话说C是面向内存的编程语言。数据要能存得进去,取得出来,且要考虑效率。不管是顺序存储还是链式存储,其寻址方式总是很重要。顺序存储是连续存储。同质结构的数组通过其索引表...【详细内容】
2021-12-08  小智雅汇    Tags:数据存储   点击:(18)  评论:(0)  加入收藏
概述DBConvert Studio 是一款强大的跨数据库迁移和同步软件,可在不同数据库格式之间转换数据库结构和数据。它将成熟、稳定、久经考验的 DBConvert 和 DBSync 核心与改进的现...【详细内容】
2021-11-17  雪竹聊运维    Tags:数据库   点击:(26)  评论:(0)  加入收藏
一、前言 大家好,我是小诚,《从0到1-全面深刻理解MySQL系列》已经来到第四章,这一章节的主要从一条SQL执行的开始,由浅入深的解析SQL语句由客户端到服务器的完整执行流程,最...【详细内容】
2021-11-09  woaker    Tags:SQL   点击:(35)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条