下载文档原格式
计算机专业基础综合数据结构（图）历年真题试卷汇编4(总分58, 做题时间90分钟)6. 综合题1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。
【北京邮电大学2000五(15分)】SSS_TEXT_QUSTI2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。
【南开大学1998二(12分)】SSS_TEXT_QUSTI3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。
【西北大学2000二、8(5分)】SSS_TEXT_QUSTI4.下图是带权的有向图G的邻接表表示法，求：(1)以结点V1出发深度遍历图G 所得的结点序列；(2)以结点V1出发广度遍历图G所得的结点序列；(3)从结点V1到结点V8的最短路径；(4)从结点V1到结点V8的关键路径。
【中国海洋大学1999四(10分)】SSS_TEXT_QUSTI5.下表给出了某工程各工序之间的优先关系和各工序所需时间。
(1)画出相应的AOE网； (2)列出各事件的最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。
【山东大学2002七(15分)】【北京交通大学1995六(15分)】SSS_TEXT_QUSTI6.请写出应填入下列叙述中( )内的正确答案。
某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。
箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。
用事件编号的序列(例如0一2—7—9一11)表示进行作业的路径。
完成此工程的关键路径是(A)，完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。
关键路径上的事件的充裕天数是(E)。
【上海大学2002三(10分)】SSS_TEXT_QUSTI7.求出下面AOE网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。
习题七图一、单项选择题1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（）A．G’为G的子图 B．G’为G的连通分量C．G’为G的极小连通子图且V’=V D．G’是G的无环子图2.任何一个带权的无向连通图的最小生成树（）A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在3．以下说法正确的是（）A．连通分量是无向图中的极小连通子图。
B．强连通分量是有向图中的极大强连通子图。
C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。
D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。
4．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是5．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n26．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2 B．2 C．1 D．48．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图 B．无向图 C．AOV网 D．AOE网9. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程10．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径11. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
计算机专业基础综合数据结构（图）历年真题试卷汇编4(总分：58.00，做题时间：90分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。
【北京邮电大学2000五(15分)】__________________________________________________________________________________________正确答案：(正确答案：关键路径有3条，长17。
各事件允许发生的最早时间和最晚时间略。
V1→V2→V6→V8，V1→V3→V5→V7→V8，V1→V7→V8→V1→V4→V5→V8 (3)V1结点到其他各结点的最短距离为：2，3，6，12，10，15，16。
)2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。
【南开大学1998二(12分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为： 1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。
2)在图中删除该顶点及所有以它为尾的弧。
3)重复1)和2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
(2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。
这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。
)3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。
【西北大学2000二、8(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。
计算机学科专业基础综合数据结构-图(二)(总分100,考试时间90分钟)一、单项选择题(下列每题给出的4个选项中，只有一个最符合试题要求)1. 具有6个顶点的无向图至少应有______条边才能确保是一个连通图。
A.5 B.6 C.7 D.82. 设G是一个非连通无向图，有15条边，则该图至少有______个顶点。
A.5 B.6 C.7 D.83. 下列关于无向连通图特性的叙述中，正确的是______。
①所有顶点的度之和为偶数②边数大于顶点个数减1③至少有一个顶点的度为1A.只有① B.只有② C.①和② D.①和③4. 对于具有n(n＞1)个顶点的强连通图，其有向边的条数至少是______。
A.n+1B.nC.n-1D.n-25. 下列有关图的说法中正确的是______。
A.在图结构中，顶点不可以没有任何前驱和后继 B.具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和6. 对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是______，矩阵中非零元素的个数是2e。
A.n B.(n-1)2 C.n-1 D.n27. 无向图的邻接矩阵是一个______。
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵8. 从邻接矩阵可知，该图共有______个顶点。
如果是有向图，该图共有4条有向边；如果是无向图，则共有2条边。
A.9 B.3 C.6 D.1 E.5 F.4 G.2 H.09. 下列说法中正确的是______。
A.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C.一个图的邻接矩阵表示不唯一，邻接表表示唯一 D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一10. 用邻接表存储图所用的空间大小______。
A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的二次方有关11. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的______，广度优先搜索算法类似于二叉树的层次序遍历。
数据结构课程平时作业1一. 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
①A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象②A. 结构 B. 关系 C. 运算 D. 算法2．数据结构被形式地定义为（K, R）, 其中K是①的有限集合, R是K上的②的有限集合。
①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构3．②A. 操作 B. 映象 C. 存储 D. 关系A．在数据结构中, 从逻辑上可以把数据结构分成( )。
动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构4.线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系5.数据结构中, 与所使用的计算机无关的是数据的结构；A) 存储B) 物理C) 逻辑D) 物理和存储二.填空题（将正确的答案填在相应的空中）1. 在线性结构中, 第一个结点①前驱结点, 其余每个结点有且只有②个前驱结点；最后一个结点③后续结点, 其余每个结点有且只有④个后续结点。
2. 在树形结构中, 树根结点没有①结点, 其余每个结点有且只有②个前驱结点；叶子结点没有③结点, 其余每个结点的后续结点可以④。
3. 在图形结构中, 每个结点的前驱结点数和后续结点数可以①。
4．线性结构中元素之间存在①关系, 树形结构中元素之间存在②关系, 图形结构中元素之间存在③关系。
5.数据结构包括数据的、数据的和数据的这三个方面的内容。
6. 下面程序段的时间复杂度是①。
for（i=0；i＜n；i++）for（j=0；j＜m；j++）A[i][j]=0；7. 下面程序段的时间复杂度是①。
S＝0；for（i=0；i<n；i++）for（j=0; j<n; j++）s+=b[i][j]；sum=s;三、简答题1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.设有数据逻辑结构S=（D,R）, 试按题所给条件画出这些逻辑结构的图示, 并确定相对于关系R, 哪些结点是开始结点, 哪些结点是终端结点？D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4) }部分参考答案一、单选题二、A B 2. B D 3. C 4. D 5. C三、填空题1.无, 1, 无, 12.前驱, 1个, 后继, 多个3.多个4.一对一, 一对多, 多对多5.逻辑结构、物理结构、数据运算6. O(n*m)7. O(n*n)三、简答题1.略见课件2.略3. d1( d2(d3(d4 线性结构数据结构课程平时作业2一. 单项选择题1.线性表L=（a1, a2,…,a n）,下列说法正确的是（）。
2002年哈工大计算机科学与技术专业854考研真题I．数据结构一、填空题1.具有n个顶点的开放树，边的总数有（1）条。
2.由三个结点组成的二元树共有（2）各不同的结构形态。
3.N个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中（3-1）个元素，删除一个元素最坏情况下要移动（3-2）个元素。
4.一个二元树第5层结点最多有（4）个。
5.若在一个表中共有625个元素，且查找每个元素的概率相同，那么在采用分块查找时，每块的最佳长度为（5-1），此时的平均查找长度为（5-2）。
6.具有n个叶结点的哈夫曼（Huffman）树中，其结点总数为（6）。
7.在折半查找中，要求被查找元素必须采用（7-1）存储结构，且（7）。
8.堆分类（heap sort）的时间复杂性为（8-1）。
基数分类的的时间复杂性为（8-2）。
9.一个无向图有n个顶点，e条边，则所有顶点的度数之和为（9）。
10.设F是一个森林，B是由F按自然对应关系转换而得到的二元树，F中有n个非终结结点，则B中右子树为空的结点有（10）个。
二、选择题1.下三角矩阵A m*n按行优先顺序压缩存储在数组Sa[(n+1)*n/2]中，若非零元素a ij(0<=i,j<n)存放在Sa[k]中则i,j和k之间的关系为（1）。
A.k=i*n+jB.k=j*n/2+iC.k=(i+1)*i/2+jD.k=(j-1)*n/2+i-12.将一株有100个结点的完全二元树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（2）。
A.98B.99C.50D.没有右孩子3.数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（3）。
A.逻辑结构B.顺序存储结构C.链式存储结构D.以上都对4.一株非空二元树的所有叶结点在先根、中根和后根遍历序列中的相对顺序（4）。
A.发生改变B.不发生改变C.不能确定D.以上都不对5.对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则表向量（顶点表）的大小为（5-1），所有关于顶点的邻接表（边表）的结点总数为（5-2）。
第七章图习题答案基础知识：7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。
(2)哪些图是连通图?对非连通图给出其连通分量。
(3)哪些图是自由树(或森林)?答:(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图：(a)、(c)、(d)是连通图，(b)不是连通图，因为从1到2没有路径。
具体连通分量为：(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：(a)不是自由树，因为有回路。
(b)是自由森林，其两个连通分量为两棵自由树。
(c)不是自由树。
(d)是自由树。
7.2 在图7.24(下图)所示的有向图中：(1) 该图是强连通的吗? 若不是，则给出其强连通分量。
(2) 请给出所有的简单路径及有向环。
(3) 请给出每个顶点的度，入度和出度。
(4) 请给出其邻接表、邻接矩阵及逆邻接表。
答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。
(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)(3)每个顶点的度、入度和出度：D(v1)=3ID(v1)=1OD(v1)=2D(v2)=2 ID(v2)=1OD(v2)=1D(v3)=3 ID(v3)=2OD(v3)=1D(v4)=2 ID(v4)=1OD(v4)=1(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next┌─┬─┐┌─┬─┐┌─┬─┐0│v1│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘1│v2│─→│ 2│∧│├─┼─┤├─┼─┤2│v3│─→│ 0│∧│├─┼─┤├─┼─┤3│v4│─→│ 2│∧│└─┴─┘└─┴─┘逆邻接表：┌─┬─┐┌─┬─┐0│v1│─→│ 2│∧│├─┼─┤├─┼─┤1│v2│─→│ 0│∧│├─┼─┤├─┼─┤┌─┬─┐2│v3│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘3│v4│─→│ 0│∧│└─┴─┘└─┴─┘邻接矩阵：0 1 0 10 0 1 01 0 0 00 0 1 07.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。
一、应用题1．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
1题图答．深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一（3）这里的遍历，均从顶点1开始2．给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。
（3）宽度优先生成树3.在什么情况下，Prim算法与Kruskual算法生成不同的MST？答．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST4．已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，试画出构造过程）。
答．Prim 算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal 算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）5．G=(V,E)是一个带有权的连通图,则：（1）．请回答什么是G 的最小生成树； （2）．G 为下图所示,请找出G 的所有最小生成树。
28题图答．（1）最小生成树的定义见上面26题 （2）最小生成树有两棵。
（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W ）形式），其中W 代表权值。
V （G ）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）}6．请看下边的无向加权图。
（1）．写出它的邻接矩阵。
（2）．按Prim 算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。
辅助数组各分量值：7．已知世界六大城市为:(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）．画出这六大城市的交通网络图;（2）．画出该图的邻接表表示法;（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树.8．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边的两个端点和其权值，共11行。
1. 首先将如下图所示的无向图给出英存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
答•深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列（2） 在邻接表确泄后，深度优先和宽度优先遍历序列唯一 （3） 这里的遍历，均从顶点1开始 2. 给出图G ：画岀G 的邻接表表示图:3. 在什么情况下，Prim 算法与Kruskual 算法生成不同的MST?答.在有相同权值边时生成不同的MST,在这种情况下，用Prim 或Kruska 1也会生成不 同的应用丿 画出G 的深度优先生成树和广度优先生成树。
(1).HST4・已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树(假设以①为起点，试画出构适过程)。
答.Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法, 构造最小生成树过程如下：(下图也可选(2, 4)代替(3, 4), (5, 6〉代替⑴5))5.G=(V,E)是一个带有权的连通图，则：(1). ifi回答什么是G的最小生成树：(2). G为下图所示,请找出G的所有最小生成树。
答.(1)最小生成树的左义见上而26题(2)最小生成树有两棵。
邙艮于篇幅，下而的生成树只给岀顶点集合和边集合，边以三元组(Vi,Vj,W)形式)，其中 W代表权值。
V (G) ={1, 2, 3, 4, 5} E1(G) = {(4, 5, 2), (2, 5, 4), (2, 3, 5), (1, 2,7) }：E2(G)={(4, 5, 2), (2, 4, 4), (2, 3, 5), (b 2、7) }6.请看下边的无向加权图。
(1).写出它的邻接矩阵。
(2).按Prim算法求其最小生成树, 并给出构造最小生成树过程中辅助数组的各分量值。
辅助数组各分量值：7.已知世界六大城市为：（Pe）、纽约（N）、巴黎（Pa）.伦敦（L）、东京仃）.墨西哥（M）, 下表给泄了这六大城市之间的交通里程：世界六大城市交通里程表（单位:百公里）（1） .画岀这六大城市的交通网络图；（2） .画出该图的邻接表表示法；（3） .画岀该图按权值递增的顺序来构造的最小（代价）生成树.8.已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边的两个端点和貝权值，共11行。
《数据结构》实验报告实验内容：（一）判断一个图有无回路（二）求一个无向图G的连通分量的个数一、目的和要求（需求分析）：1、了解图的定义和图的存储结构。
2、熟悉掌握图的邻接矩阵和邻接表。
3、理解图的遍历算法---深度优先搜索和广度优先搜索。
4、学会编程处理图的连通性问题。
二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）判断一个图有无回路：在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。
在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。
如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。
无向图则可以转化为：如果存在回路，则必然存在一个子图，是一个回路。
因此回路中所有定点的度>=2。
第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。
第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。
如果最后还有未删除的顶点，则存在回路，否则没有。
求一个无向图G的连通分量的个数：用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。
所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。
三、调试和运行程序过程中产生的问题及采取的措施：在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)，而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。
四、源程序及注释：判断一个图有无回路：#include <stdio.h>#include <malloc.h>#include <stdlib.h>// 输出有向图的一个拓扑序列。
// 图的邻接表存储表示#define MAX_NAME 3 // 顶点字符串的最大长度+1#define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量typedef int InfoType; // 存放网的权值typedef char V ertexType[MAX_NAME]; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 网的权值指针）}ArcNode; // 表结点typedef struct VNode{V ertexType data; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点typedef struct{AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志}ALGraph;// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
int LocateV ex(ALGraph G,V ertexType u){int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)return i;return -1;}// 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。
int CreateGraph(ALGraph *G){int i,j,k;int w; // 权值V ertexType va,vb;ArcNode *p;printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");scanf("%d",&(*G).kind);printf("请输入图的顶点数和边数:（空格）\n");scanf("%d%d", &(*G).vexnum, &(*G).arcnum);printf("请输入%d个顶点的值(小于%d个字符):\n",(*G).vexnum,MAX_NAME);for(i = 0; i < (*G).vexnum; ++i) // 构造顶点向量{scanf("%s", (*G).vertices[i].data);(*G).vertices[i].firstarc = NULL;}if((*G).kind == 1 || (*G).kind == 3) // 网printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");else // 图printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");for(k = 0;k < (*G).arcnum; ++k) // 构造表结点链表{if((*G).kind==1||(*G).kind==3) // 网scanf("%d%s%s",&w,va,vb);else // 图scanf("%s%s",va,vb);i = LocateV ex(*G,va); // 弧尾j = LocateV ex(*G,vb); // 弧头p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;if((*G).kind == 1 || (*G).kind == 3) // 网{p->info = (int *)malloc(sizeof(int));*(p->info) = w;}elsep->info = NULL; // 图p->nextarc = (*G).vertices[i].firstarc; // 插在表头(*G).vertices[i].firstarc = p;if((*G).kind >= 2) // 无向图或网,产生第二个表结点{p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = i;if((*G).kind == 3) // 无向网{p->info = (int*)malloc(sizeof(int));*(p->info) = w;}elsep->info = NULL; // 无向图p->nextarc = (*G).vertices[j].firstarc; // 插在表头(*G).vertices[j].firstarc = p;}}return 1;}void Display(ALGraph G) // 输出图的邻接表G。
{int i;ArcNode *p;switch(G.kind){case DG: printf("有向图\n");break;case DN: printf("有向网\n");break;case AG: printf("无向图\n");break;case AN: printf("无向网\n");}printf("%d个顶点：\n",G.vexnum);for(i = 0; i < G.vexnum; ++i)printf("%s ",G.vertices[i].data);printf("\n%d条弧(边):\n", G.arcnum);for(i = 0; i < G.vexnum; i++){p = G.vertices[i].firstarc;while(p){if(G.kind <= 1) // 有向{printf("%s →%s ",G.vertices[i].data,G.vertices[p->adjvex].data);if(G.kind == DN) // 网printf(":%d ", *(p->info));}else // 无向(避免输出两次){if(i < p->adjvex){printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);if(G.kind == AN) // 网printf(":%d ",*(p->info));}}p=p->nextarc;}printf("\n");}}void FindInDegree(ALGraph G,int indegree[]) // 求顶点的入度。
{int i;ArcNode *p;for(i=0;i<G.vexnum;i++)indegree[i]=0; // 赋初值for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}typedef int SElemType; // 栈类型typedef struct SqStack // 栈的顺序存储表示{SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间，以元素为单位}SqStack; // 顺序栈int InitStack(SqStack *S) // 构造一个空栈S{// 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if( !(*S).base )exit(0); // 存储分配失败(*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;}// 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。
