您好,登录后才能下订单哦!
本篇内容主要讲解“数据库十字链表有什么优点”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“数据库十字链表有什么优点”吧!
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; } }
到此,相信大家对“数据库十字链表有什么优点”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。