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

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

    【函数代码】
int Toplogical(LinkedWDigraph G)
{
Gnode *p；
int j，w，top=0；
int *Stack，*ve，*indegree；
ve=(int*)malloc((G．n+1)*sizeof(int))；
indegree=(int*)malloc((G．n+1)*si zeof(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]=j；
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->adjvex]--。 (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的Firstadj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有：
    indegree=(int*)malloc(  (G．n+1)*sizeof(int)  )；／*存储网中各顶点的入度*／
    所以第(1)空应填indegree[p->adjvex]++。
    接下来看第(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的边a1=30和到V2的边a2=10，当V1结点选出以后，a1，a2也要随之消失。这时V3和V2的入度要更新，也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p->adjvex]--。第(4)空看起来比较棘手，因为前面没有说明ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定
    if (4)
    ve[p->adjve]=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[w]+p->weigh()>Ve[p->adjvex]。所以第(4)空应该填“(ve[w]+p->weight)>ve[p->adjvex]”。
    第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢?这一点可以从关键路径的定义着手：“称从开始顶点到结束顶点的最长路径为关键路径”，所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。
转载请注明原文地址:https://kaotiyun.com/show/GdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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