有向图十字链表c语言（有向图的十字链表怎么画）

今天给各位分享有向图十字链表c语言的知识，其中也会对有向图的十字链表怎么画进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

1、面试准备之【数据结构】1——图2、十字链表表示稀疏矩阵,并求矩阵的加法,减法,乘法,运算要求用C语言3、数据结构(C语言)

面试准备之【数据结构】1——图

共有：邻接表，邻接矩阵

有向图独有：十字链表，边集数组  

无向图独有：邻接多重表  

一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：Arc[i][j]=1,若vi,vj∈E或vi,vj∈E,反之等于0。

可以看出，无向图的邻接矩阵是对称矩阵，要想知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。

在有向图的邻接矩阵中，某个顶点的出（入）度是这个顶点vi在邻接矩阵中第i 行（列）的元素之和；

        我们发现，当图中的边数相对于顶点较少时，邻接矩阵是对存储空间的极大浪费。我们可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。回忆树结构的孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。

邻接表的创建过程如下：

1）  图中顶点用一个一维数组存储，当然也可以用单链表来存储，不过用数组可以较容易的读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2）  图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为以vi为弧尾的出边表。

从图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息。

firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。

边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指

向边表中下一个结点的指针，比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2.

如果想知道某个顶点的度，就去查找这个顶点的边表中结点的各数。

若要判断顶点vi和vj是否存在边，只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了。

若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。

有向图的邻接表中顶点vi的边表是指以vi 为弧尾 的弧来存储的，这样很容易就可以得到每个顶点的出度。

有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立

一个链接为vi为弧头的表。如下图所示：

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道。反之，逆邻接表解决了入度

却不了解出度的情况。有没有可能把邻接表和逆邻接表结合起来呢？

答案是肯定的，就是把它们整合在一起。这种存储有向图的方法是：十字链表（Orthogonal List）.

我们重新定义顶点表结点结构为：   

|    data    |     firstin   |    firstout    |

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义的 边表 结点结构如下表：

|    tailvex    |    headvex    |    headlink    |    taillink    |

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点（弧头）相同的

下一条边，taillink是指出边表指针域，指向起点（弧尾）相同的下一条边。如果是带权值的网，还可以再增加一个weight域来存储权值。

如下图表示的十字链表：

顶点表依然是存入一个一维数组{v0,v1,v2,v3},以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以v0边表结点的headvex=3,

而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所以headlink和taillink都是空。

这里虚线箭头的含义，其实就是逆邻接表的表示。对于v0来说，它有两条入边，分别来自顶点v1和v2。因此v0的firstin指向顶点v1的边表

结点中headvex为0的结点，虚线（1），接着由入边结点的headlink指向下一个入边顶点v2，虚线（2）。

对于顶点v1,它有一个入边顶点v2，2个出边顶点v0和v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，虚线（3）.

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得

顶点的出度和入度。除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表是相同的，因此很好的应用在有向图中。

十字链表主要是针对有向图的存储结构进行了优化，那么对于无向图的邻接表，有没有问题呢？如果我们在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作。如下图，若要删除(v0,v2)这条边，需要对邻接表结构中右边表的两个结点进行删除，显然这是比较繁琐的。

因此，我们也仿照十字链表的方式，对边表结点的结构进行一些改造，重新定义的边表结点结构如下表：

|    ivex    |     ilink    |     jvex    |     jlink    |

其中ivex和jvex是指某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。

这就是邻接多重表结构。如上图有4个顶点和5条边，先将边表结点画出来。由于是无向图，所以ivex，jvex正反过来都可以，为了绘图

方便，都将ivex值设置的与一旁的顶点下标相同。

下面开始连线，首先连线的（1）（2）（3）（4）是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同。接着，由于顶点v0的(v0,v1)边的

邻边有(v0,v3)和(v0,v2)。因此（5）（6）的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex（ivex）一定要与它本身

的jvex（ivex）的值相同。同理，连线（7）就是指（v1,v0）这条边，它是相当于顶点v1指向（v1,v2）边后的下一条。v2有三条边依附，所以（3）之后就有

了（8）（9）。连线（10）就是顶点v3在连线（4）之后的下一条边。左图一共有5条边，所以右图有10条连线，完全符合预期。

邻接多重表与邻接表的差别， 仅仅是在于同一条边在邻接表中用两个边表结点表示，而在邻接多重表中只有一个结点 。这样对边的操作就方便

多了，若要删除左图的(v0,v2)这条边，只需要将右图的（6）（9）的链接指向改为^即可。

—- 边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

如上图所示，边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次

进行处理的操作，而不适合对顶点相关的操作

路径长度：路径上各活动持续时间的总和（即路径上所有权之和）。

完成工程的最短时间：从工程开始点（源点）到完成点（汇点）的最长路径称为完成工程的最短时间。

关键路径：路径长度最长的路径称为关键路径。

二分图是一类特殊的图，又称为双分图、二部图、偶图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。可以将 U 和 V 当做一个着色：U 中所有顶点为蓝色，V 中所有顶点着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分图无法被二着色

完全二分图 是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。欧拉证明了如下定理： 一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数。 由此可得如下结论：一个连通图有欧拉迹当它至多有两个度数是奇数的顶点。

AOE网Activity On Edge Network：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

图的存储结构-邻接助阵和邻接表  

图的存储结构-十字链表和邻接多重表

十字链表表示稀疏矩阵,并求矩阵的加法,减法,乘法,运算要求用C语言

十字链的原理很简单啊。实现也比较简单。i,here, give you the defination of the node.and you can build a cross_linkList by yourself or you can take a look at what the above writing.

定义一个表头结点数据类型，实现的时候定义一个数组即可。

typedef struct node{

int vex;//顶点

struct *node *first;//指向第一个与其有联系的结点

}ListNode；

然后再定义一个结点的类型，

typedef struct node{

int vexNum;//顶点编号

int vexData;//顶点数据

struct *node *next;//指向其它与表头结点有联系的结点

}Node；

矩阵的加法是对应项相加，那么你只需要把用十字链表示的两个矩阵中，对应项相加即可。具体来说，对每个顶点，在表头表中查找，然后再查找与其有联系的结点。指针后移，比较两个十字链表中是否存在两个相同的结点，有，则相加，将结果保存到其中一个十字链表中。否则，不变。依次查找其他的顶点。就可以得到结果。

ListNode head1,head2;

Node *p,*q;

p=head1-frist;

q=head2-first;

while(!p)

{

while(!q)

{

if(p-vexNum==q-vexNum)

{

p-vexData+=q-vexData;//put the result into the first cross_linkList;

break;//

}

q=q-next;

}

p=p-next;

}

the implement of adding is just like what i writing above.

And the others are similar .you can do it by yourself.trust youself.

数据结构(C语言)

1. B

原因：

A：无向图的邻接矩阵一定是对称的，但是对称的不都是无向图，因为有向图也有可能对称

B：显然。。。。最容易，因为看任意两个点可以从行或者列任意挑一个，然后看相交点是否为1就行了

C：邻接表相当的不好看

D：十字链表也不容易

2. top – base + 1

3.返回值为-1，说明linklist为空，同时把函数的参数x插入linklist

返回值为0，说明linklist中有内容为x的元素

返回值为1，说明linklist不为空，但是没有内容为x的元素，同时把函数的参数x插入linklist

r-data*=x 的意思是 r-data = r-data*x

S1就是做了一个判断linklist是否为空，如果为空把x插入到linklist里面的工作

S2就是遍历linklist的所有内容，查找是否有内容为x的元素，如果有把data里面存放的数乘以x，然后再放回到data里面。

最后的if就是对S2做最后的补充，因为在执行S2的时候，把原来的数据换成原来的数据乘以x了，所以就再添加进去。

我觉得编写这个程序的人，有点绕路了，既然后来填进去，当初何必改呢。。。。。。

4.用冒泡排序的算法，虽然算法的复杂度高（指的是算法效率不高），但是算法简单易懂，基本上所有的新手书上都有。

（1）让初始值为1，步长为2，做一次冒泡排序就行了

（2）让初始值为2，步长为2，做一次冒泡排序就行了

（3）count = 0;

for (i = 0; i lengthof(a); i++) {

for (j = 0; j lengthof(a); j+ {

if (a[i]==a[j]) count++;

};

};

这是一段伪代码，可以作为参考

有向图十字链表c语言的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于有向图的十字链表怎么画、有向图十字链表c语言的信息别忘了在本站进行查找喔。