2. 计算机
  3. 阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。 [说明] 函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点

阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。 [说明] 函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点

admin2009-02-15  115
问题 阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。
    [说明]
   函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下。
   typedef struct Gnode{               /* 邻接表的表节点类型 */
       int adjvex;                     /* 邻接顶点编号 */
       int weight;                     /* 弧上的权值 */
        struct Gonde*nextare;        /* 指示下一个弧的节点 */
   } Gnode;
   typedef struct Adjlist {         /* 邻接表的头节点类型 */
       char vdata;                  /* 顶点的数据信息 */
       struct Gnode*Firstadj;       /* 指向邻接表的第一个表节点 */
   }Adjlist;
   typedef struct LinkedWDigraph{   /* 图的类型 */
       struct Adjlist head;         /* 指向图中第一个顶点的邻接表的头节点 */
   } LinkedWDigraph;
   例如，某AOE-网如图4-14所示，其邻接表存储结构如图4-15所示。
  
  [函数]
   int Toplogical(LinkedWDigraph G)
   {    Gnode *p;
        int j, w, top=0;
        int Stack,*ve, *indegree;
        ve=(int *)mallloc(G.n+1)*sizeof(int));
        indegree=(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]=j;
         while (top＞O) {
            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 */
选项
答案这是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE-网(Activity On Edge network，边表示活动的网)是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可以用来估算工程的完成时间。 在AOE-网中，入度为0的顶点为源点，出度为0的顶点为汇点。由于有些活动可以并行地执行，因此从源点到汇点的路径中，长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。 设顶点巧的最早发生时间用ve(j)表示，则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为： [*] 其中，T是所有到达顶点j的弧的集合；dut(＜i,j＞)是弧＜i,j＞上的权值；n是网中的顶点数(即汇点的序号)。 显然，上式是一个从源点开始的递推公式。ve(j)的计算必须在Vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE-网进行拓扑排序，然后按拓扑有序序列逐个求出各项点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在顶点Vj之前。可见，拓扑排序序列是由有向图中的所有顶点构成的一个线性序列，在这个序列中体现了所有顶点之间的优先关系。 对AOE-网进行拓扑排序的步骤如下： 1) 首先在-AOE网中选择—个入度为0(没有前驱)的顶点且输出它。 2) 然后从网中删除该顶点，并且删除以该顶点为始点的所有引出边。 3) 重复上述两个步骤，直至网中不存在入度为0的顶点为止。 在拓扑排序过程中，有可能同时存在多个入度为0的顶点，函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间，分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号，它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环，即for(j=1;j＜=G.n;j++) {ve[j]=0； indegree[j]=0;}，主要完成数组初始化的功能。 进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组indegree[]中，从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号，顶点Vi的编号为i，第2个for循环代码主要完成求网中各个顶点的入度的功能。 For(j=1; j＜=G.n; j++) { /* 求网中各顶点的入度 */ p=G.head[j].Firstadj; while(p) { (1)； p=p—＞nexcarc； } /* while */ } /* for */ 在有向图中，若以V2为尾的弧有＜V2，V4＞且权值为30，＜V2,V6＞且权值为50，则其的邻接表表示形式是：V2→4，30→6，50^。 因此，扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1，即(1)空缺处应填入“indegree[p-＞adjvex]++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 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 */ 由于入度为0的顶点由栈中弹出，根据变量w在后续代码中所起的作用—存放网中没有直接前驱的顶点，并通过printf语句输出，可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后，在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边，并通过内嵌的while循环语句把这些引出边对应的终点的入度减1，即将邻接到顶点w的各个顶点(p-＞adjvex)的入度减1，再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p-＞adjvex]--”或其等价形式。 同时，对于顶点p-＞adjvex而言，当删除其所有引入边之后，从源点出发到达它的最长路径长度也就计算出来了，所以每删除一条到达顶点p-＞adjvex的引入边，都要查看一下最长路径长度是否需要更新。因此，(4)空缺处填入“ve[w]+p-＞weight＞ve[p-＞adjvex]”或其等价形式。 算法程序的最后部分，通过return语句返回该图的关键路径长度，即汇点的最早发生时间(该AOE-网的关键路径长度)。由于AOE-网中汇点未必是编号最大的顶点，但它必然是从栈中弹出的最后一个顶点，因此(5)空缺处填入“ve[w]”或其等价形式。
解析
转载请注明原文地址:https://kaotiyun.com/show/tEjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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