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

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

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;inumV;i++)//建立顶点信息      {          cin >> G->adjlist[i].data; //输入顶点信息          G->adjlist[i].firstOutEdge = NULL; //边表节点 为空        G->adjlist[i].firstInEdge = NULL; //边表节点 为空    }      for(k=0;k>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;          }  }

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