2. 计算机
  3. 阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include ＜stdio. h＞ #include ＜stdlib. h＞ #define MAXN 30

阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include ＜stdio. h＞ #include ＜stdlib. h＞ #define MAXN 30

admin2009-02-15  41
问题 阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】用克鲁斯卡尔算法求解给定图的最小生成树。
   #include ＜stdio. h＞
   #include ＜stdlib. h＞
   #define MAXN 30
   typedef struct
   {    int v1,v2;     /*一条边依附的两个顶点*/
        int weight;    /*边上的权值*/
   }EDGE;
   typedef struct
   {    int Vnum;      /*图中的顶点数目*/
        EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/
   }Graph;
   typedef struct node{    /*用链表存储同一个连通分量的顶点*/
       int v;
       struct node *next;
   }Alist;
   void heapadjust(EDGE data[], int s, int m)
   {    /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/
    int j;
    EDGE t;
    t=data[s];     /*备份元素data[s], 为其找到适当位置后再插入*/
    for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/
        if(j＜m &&(1)) ++j;
        if(!(t. weight＞data[j]. weight)) break;
        data[s]=data[j];s=j;    /*用s记录待插入元素的位置(下标)*/
    }/*for*/
    data[s]=t;         /*将备份元素插入由s所指出的插入位置*/
   }/*heapadjust*/
   int creat_graph(Graph *p)    /*输入图中的顶点及边, 返回图中边的数目*/
   {    int k=0;     /*记录图中边的数目*/
    int n;
    int v1,v2;
    int w;
    printf("vertex number of the graph:");
    scanf("%d", &n);    /*输入图中的顶点数目*/
    if(n＜1) return 0;
     p-＞Vnum=n;
    do{    printf("edge(vertex1,vertex2,weight):");
            scanf("%d %d %d", &V1, &v2, &w);
            if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){
                p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;
                k++;
            }/*if*/
    }while(!(  (2)  ));
    return k;     /*返回图中边的数目*/
   }/*creat_graph*/
   int kruskal(Graph G, int enumber, int tree[][3])
   {    /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */
        /*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/
          int i, k, m, c=0;
          int v1, v2;
          Alist *p, *q, *a[MAXN];
          for(i=0; i＜G．Vnum; ++i){    /*将每个连通分量中的顶点存放在一个单链表中*/
              a=(Alist*)malloc(sizeof(Alist));
              if(!a) {
                  printf("\n mernory allocation error!");
                      exit(0);
                  }/*if*/
              a-＞v=i; a-＞next=NULL;
          }/*for*/
          for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/
              heapadjust( (3) );
       k=G. Vnum;     /*k用于计算图中的连通分量数目*/
       m=enumber-1;
       i=0;
       do{
           v1=G. e[0]. v1; v2=G. e[0]. v2;
            p=a[v1];
           while(p && p-＞v!=v2){    /*判断当前选择的边的顶点是否在一个连通分量中*/
               q=p; p=p-＞next;
           }
           if(!p){    /*当前边的顶点不在一个连通分量中*/
               p=q;
               p-＞next=a[G. e[0]. v2];
               p=a[G. e[0]. v1); /*加入边(v1,v2), 将两个连通分量合并为一个*/
           while(p){a[p-＞v]=(4); p=p-＞next; }
                   k--;     /*连通分量数目减少一个*/
               tree[0]=v1;     /*记录加入最小生成树的边*/
                   tree[1]=v2;
               tree[2]=G. e[0]. weight;
               c+=G. e[0]. weight;
                   ++i;
           }/*if*/
           G. e[0]=G. e[m];
           m--;
           heapadjust ((5));
       } while(k＞1);     /*当所有顶点不在同一个连通时, 继续*/
       return c;     /*返回最小生成树的代价*/
   } /*kruskal*/
   void main(void)
   {   int i, enumber;
       int tree[MAXN][3];
       int cost=0;
       Graph G;
       enumber=creat_graph(&G);
       cost=-kruskal(G,enumber,tree);
       printf("Minimum-Cost spanning tree(kruskal)：\n");
       printf("edge\t weight\t\n");
       for(i=0; i＜G. Vnum-1; ++i)
           printf("v %d –v %d \t %d\n", tree[0], tree[1], tree[2]);
       printf("Cost：%d\n", cost);
   }
选项
答案(1) data[j].weight＞data[j+1].weight (2) v1==-1 && v2==-1 (3) G.e，i，enumber-1 (4) a[G.e[0].v1] (5) G.e,0,m
解析 (1) data[j].weight＞data[j+1].weight
   沿值较小的子结点向下筛选，建堆，堆顶元素最小；
(2) v1==-1 && v2==-1
   当v1!=-1||v2!=-1时，循环读入，直到v1==-1 && v2==-1为真。
(3) G.e，i，enumber-1
   按照边上的权值建立小顶堆。
(4) a[G.e[0].v1]
   加入边(v1,v2)，将两个连通分量合并为一个。
(5) G.e,0,m
   找出下一条权值最小的边。
转载请注明原文地址:https://kaotiyun.com/show/FgDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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