阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网

admin2010-01-15  34

问题 阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
   【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
   typedef struct Gnode{             /*邻接表的表结点类型*/
     int adivex;                     /*邻接顶点编号*/
     int weight;                     /*弧上的权值*/
     bstmct Gonde*nextare;           /*指示下一个弧的结点*/
   }Gnode;
   typedef struct Adjlist{           /*邻接表的头结点类型*/
     char vdata;                     /*顶点的数据信息*/
     struct Gnode*Firstadj;          /*指向邻接表的第1个表结点*/
   }Adjlist;
   typedef struct LinkedWDigraph{    /*图的类型*/
     int n, e;                       /*图中顶点个数和边数*/
     struct Adjlist head;            /*指向图中第1个顶点的邻接表的头结点*/
   }LinkedWDigraph;
   【函数】
   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(i=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*/
     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]及其等价形式

解析 (1)indegree[p->adjvex]++及其等价形式
   此填空在for(j=1;j<=G.n;j++)中,求网中各顶点的入度。遍历邻接表G.head[j].Firstadj,将每个结点p->adjvex的入度indegree[p->adjvex]加1。邻接表是j的出度结点表。
(2)Stack[top-]及其等价形式
   栈Stack中存放的是入度为0的结点号,此while循环中,w取栈顶值开始搜索打印这些结点。
(3)indegree[p->adjvex]--及其等价形式
   由于p=G.head[w].Firstadj;因此while循环是遍历这个邻接链表,将每个结点的入度减1。将入度为0的结点号入栈Stack中。
(4)ve[w]+p->weight>ve[p->adjvex]及其等价形式
   若ve[w]+p->weight大于ve[p->adjvex],则ve[w]+p->weight是最长路径,用ve[w]+p->weight取代ve[p->adjvex]。
(5)ve[w]及其等价形式
   最终返回的是w结点的ve[w]值作为整个AOE—网的最长路径值。
转载请注明原文地址:https://jikaoti.com/ti/Qoi7FFFM
0

随机试题
最新回复(0)