2. 计算机
  3. 函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下： ty

函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下： ty

admin2017-08-31  108
问题 函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
    typedef struct Gnode{    ／*邻接表的表结点类型*／
    int adj vex；    ／*邻接顶点编号*／
    int weight；    ／*弧上的权值*／
    struct Gnode*nextarc；    ／*指示下一个弧的结点*／
    }Gnode；
    typedef struct Adj list{    ／*邻接表的头结点类型*／
    char vdata；    ／*顶点的数据信息*／
    struct Gnode*Firstadj；    ／*指向邻接表的第一个表结点*／
    }Adjulist；
    typedef struct LinkedWDigraph{／*图的类型*／
    int n，e；    ／*图中顶点个数和边数*／
    struct Adj list*head；    ／*旨向图中第一个顶点的邻接表的头结点*／
    }LinkedWDigraph；
    例如，某AOE网如图15-2所示，其邻接表存储结构如图15-3所示。

【函数代码】
int Toplogical(LinkedWDigraph G)
{
Gnode*p；
int j r W r top=0；
int*Stack，*ve，*indegree；
ve=(int*)malloc((G．n+1)*sizeof(int))；
indeqree=(int*)malloc((G．n+1)*sizeof(int))；／*存储网中各项点的入度*／
Stack：(int*)malloc((G．n+1)*sizeof(int))；    ／*存储入度为0的顶点的编号*／
if(!ve ｜｜!indegree ｜｜!Stack)  exit(0)；
for(J=1；j<=G．n；j++){
    ve[j]=0；  indegree[j]=0；
}／*for*／
for(j=1；j<=G．n；j++){    ／*求网中各项点的入度*／
    P=G．head[j]．Firstadj；
    while(P){
    (1):
P=P一>nextarc；
    }／*while*／
}／*for*／
for(j=1；j<=G．n；j++)  ／*求网中入度为0的顶点并保存其编号*／
    if(!indegree[J])  Stack[++top]=l:
while(top>0){
    W= (2)；
    printf(“％c”，G．head[w]．vdata)；
    P=G．head[w]．Firstadj；
    while(P){
    (3)  ；
    if(!indegree[p一>adjvex])
    Stack[++top]=P一>adjvex；
    if(    (4)    )
    ve[p一>adjvex]=ve[w]+p一>weight；
    p=P一>nextarc；
    }／*while*／
}／*while*／
return  (5)  ；
}／*Toplogical*／
选项
答案(1)indegree[p->adjvex]++。 (2)Stack[top--]。 (3)indegree[p->advex]--。 (4)(Ve[w]+p->weight)>ve[p->adjvex]。 (5)Ve[w]。
解析 此C语言程序题考点为拓扑排序和关键路径。在解题之前，先了解几个概念。
(1)AVO网络。
一个大工程中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络，图15-4所示是一个AOV网络。

(2)拓扑排序。
对AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得如在AOV网络中存在一条弧(i，j)，则活动i排在活动j之前。对图15-4中的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567，01243657，02143657，01243567。
(3)AOE网络。
利用AOV网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为AOE网络。图15—5所示为一个具有8个活动的某个工程的AOE网络。图中，有6个顶点，分别表示事件V1～V6，其中V1是工程的开始状态，V4是工程的结束状态。边上的权表示完成该活动所需的时间。

    (4)关键路径。
    在AOE网络中某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图15-5的AOE网络的关键路径为V1一V2一V6一V4，关键路径长度为80。
    了解了上面的这些概念以后，解题就非常容易了。
    从程序中的注释可知下段程序的作用是求网中各顶点的入度。
    for(  j  =1；  j<=G．n；  j++  }{
    p=G．head[j]．Firstadj；
    while(p){
    (1)
    p=p一>nextarc；
    }
    }
    从已知的代码结合邻接表来看，首先p指向了邻接表弟1个结点V1的Firstadj域，然后用while循环遍历了V1的Firsta，dj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有：
    indegree=(int*)malloc((G．n+1)*sizeof(int)  )；／*存储网中各顶点的入度*／
    所以第(1)空应填indegree[p->adjex]++。
    接下来看第(2)空，第(2)空是给w赋值，接下来是打印第w号结点的数据，这也就意味着w号结点是拓扑排序选出来的结点，所以w必是一个入度为0的结点。然而在此之前已经有程序把所有的入度为0的结点保存在Stack数组中了，而且Stack数组是模拟的一个栈，其控制指针只有top，所以我们应该从Stack中取出栈顶元素赋值给w。所以第(2)空填Stack[top-]。注意这里不能用“Stack[top]”，因为前面有入栈语句“Stack[++top]=j；”。
    接下来看下面的程序段。
    while(p){
   (3)  ；
    if(!indegree[p一>adjvex])
    stack[++top]  =p一>adjvex；
    if  (4)
    ve[p一>adjvex]  =Ve[w]+p一>weight；
    p=p一>nextarc；
    }
    此段程序的作用是：把选出结点所关联的边去掉，即原来V1有到V3的边al=30和到V2的边a2=10，当V1结点选出以后，a1，a2也要随之消失。这时V3和V2的入度要更新，也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p->adjvex]--。第(4)空看起来比较棘手，因为前面没有说明ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定
    if    (4)
    Ve[p一>adjvex]=ve[w]+p一>weight；
的功能是计算关键路径长度。ve的初值最开始都是0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点vx，ve[vx]中存的都是最长路径即可。也就是说，首先选出的是V1，从V1～V2只有一条路径，所以ve[v2]=a2=10，从V1～V3只有一条路径，所以ve[v3]=a1=30。然后选出V2结点,V2选出以后，因为V2～V6有a5=50，所以现在到V6的最长路径为ve[v6]=ve[v2]+a5=60。经过若干步后，当程序选中V3结点时，会产生到V6的另外一条路径V1-V3-V6，这条路径的长度为50，这条路径比现存的路径长度ve[v6]短，所以单纯的更新语句“ve[p一>adjvex]=ve[w]+p->weight”不能正确保存最长路径，为了保证ve中保存的路径最长，应该有判断(ve[wpp->weight)>ve[p->adjvex]。所以第(4)空应该填“(ve[w]+p->weight)>ve
[p->adjvex]”。
    第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢?这一点可以从关键路径的定义着手：“称从开始顶点到结束顶点的最长路径为关键路径”，所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。
转载请注明原文地址:https://www.kaotiyun.com/show/lODZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)