数据库十字链表有什么优点

发布时间:2021-12-08 13:58:17 作者:iii
来源:亿速云 阅读:291

本篇内容主要讲解“数据库十字链表有什么优点”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“数据库十字链表有什么优点”吧!

1. 引言:

对于有向图来说,邻接表是有缺陷的:

邻接表:关心了出度问题,想了解入度就必须要遍历整个图才知道。

逆邻接表:解决了入度,却不了解出度的情况。

能否把邻接表和逆邻接表结合起来呢?答案就是:使用十字链表。


2.十字链表存储结构:

顶点表结点结构:

数据库十字链表有什么优点

firstin:表示入边表头指针,指向该顶点的入边表中第一个结点。//新加入的

firstout:表示出边表头指针,指向该顶点的出边表中的第一个结点。//跟 邻接表中的 顶点一样


边表结点结构:

数据库十字链表有什么优点

tailvex:指弧起点在顶点表的下标。

headvex:指弧终点在顶点表中的下标。//跟邻接表中的 adjvex 一样

headlink:指入边表指针域。

taillink:指边表指针域。//跟邻接表中的next 一样;

如果是网,还可以再增加一个weight域来存储权值。   

数据库十字链表有什么优点

蓝线表示出度,红线表示入度 


3.十字链表的优点:

1.)十字链表是把邻接表和逆邻接表整合在一起,这样既容易找到以Vi为尾的弧,也容易找到以Vi为头的弧,

因而容易求的顶点的出度和入度。

2.)十字链表创建图算法的时间复杂度和邻接表是相同的。

十字链表

typedef char Vtype //顶点类型  
typedef int Etype //权值类型  
#definde MAXV 100;  
typedef struct edgeNode //边表节点  
{ 
    int tailvex; //新加入的 
    int headvex; //邻接点 存储该顶点对应的下标
    Etype weight;//边 权值  
    struct edgeNode *headllink; //新加入的 
    struct edgeNode *taillink;  
}EdgeNode;  
  
typedef struct Vnode //顶点表 节点  
{  
    Vtype data;  
    EdgeNode* firstInEdge; // 入度
    EdgeNode* firstOutEdge;// 出度
}VNODE; //  
  
typedef struct  
{  
    VNODE adjlist[MAXV];  
    int numV;//当前顶点数  
    int numE;//当前边数  
}GraphAdjList;    
  
void CreateALGraph(GraphAdjList* G)  
{  
    int i,j,k;  
    EdgeNode* e= NULL;  
    cout<<输入顶点数";  
    cin>>G->numV;  
    cout<<输入边数";  
    cin>>G->numE;  
    for(i=0;i<G->numV;i++)//建立顶点信息  
    {  
	cin >> G->adjlist[i].data; //输入顶点信息  
	G->adjlist[i].firstOutEdge = NULL; //边表节点 为空
	G->adjlist[i].firstInEdge = NULL; //边表节点 为空
    }  
    for(k=0;k<numE;k++)//建立边信息  
    {  
	cout<<"输入边的开始";    
	cin>>i;    
	cout<<"输入边的结尾";    
	cin>>j;  
          
	e = new EdgeNode; // 
	
	e->tailvex = i; //新加入的 弧的起点  入度
	e->headlink = G->adjlist[j].firstInEdge; //新的
	G->adjlist[j].firstInEdge = e;//新的
	
	e->headvex = j;  // 原来的 e->adjvex
	e->taillink = G->adjlist[i].firstOutEdge; //原来的
	G->adjlist[i].firstOutEdge = e;    
  
    }  
}

到此,相信大家对“数据库十字链表有什么优点”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. 多重链表 十字链表存储稀疏矩阵,中缀表达式
  2. bootstrap有什么优点

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

数据库

上一篇:数据库怎么实现临接矩阵

下一篇:Java怎么实现最小生成树MST

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》