阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,

admin2009-02-15  19

问题 阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。
   【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,求得从站0出发乘公交车至站n-1的最少换车次数。
   程序利用输入信息构建一张有向图G(用邻接矩阵g表示),有向图的顶点是车站,若有某条公交线路经i站到达j站,就在顶点i到顶点j之间设置一条权为1的有向边<i,j>。如果这样,从站点x至站点y的最少上车次数便对应图G中从点x到点y的最短路径长度。而程序要求的换车次数就是上车次数减1。
   #include <stdio.h>
   #define    M     20
   #define    N     50
   int a[N+1];    /*用于存放一条线路上的各站编号*/
   int g[N][N];   /*严存储对应的邻接矩阵*/
   int dist[N];   /*严存储站0到各站的最短路径*/
   int m, n;
   void buildG()
   {   int i, j, k, sc, dd
       printf(“输入公交线路数,公交站数\n”);
       scanf("%d%d",&m,&n);
       for (i=0;i<n;i++)     /*邻接矩阵清0*/
        for(j=0;j<n;j++)
           g[j]=0;
   for(i=0;i<m;i++)
   {    printf("沿第%d条公交线路的各站编号(0<=编号<=%d,-1结束):\n)",i+1,n-1);
        sc=0;     /* 当前线路站计数器*/
        while(1)
        {   scanf("%d",&dd);
            if(dd=-1)break;
            if(dd>=0 && dd<n) (1);
        }
        a[sc]=-1;
        for(k=1;a[k]>=0;k++)    /*处理第i+1条公交线路*/
             for(j=0;j<k;j++)
                   g (2)=1;
   }
}
int minLen()
{   int j,k;
   for(j=0;j<n;j++)
         dist[j]=g[0][j];
   dist[0]=1;
   do{
         for(k=-1,j=0;j<n;j++)      /*找下一个最少上车次数的站*/
              if(dist[j]>0 &&(k==-1||dist[j]<dist[k]))
                     k=j;
         if(k<0||k==n-1)
              break;
         dist[k]=-dist[k];       /*设置k站已求得上车次数的标记*/
         for (j=1;j<n;j++)     /*调整经过k站能到达的其余各站的上车次数*/
                if((3)&& (dist[j]=0||-dist[k]+1<dist[j]))
                      dist[j]=(4);
   }while(1);
   j=dist[n-1];
   return  (5);
}
void main()
{   int t;
   buildG();
   if((t=minLen())<0)
         printf("无解!\n");
else
     printf(“从0号站到%d站需换车%d次\n”,n-1,t);
}        

选项

答案(1)a[sc++]=dd (2)[a[J][a[k]] (3)dist[j]>=0 && g[k][j]==1 (4)-dist[k]+1 (5)k<0?-1:j-1

解析 (1)a[sc++]=dd
   将dd赋值给当前线路的a[sc],并同时将当前线路站计数器加1。
(2)[a[J][a[k]]
   将a[j]和a[k]之间置为通路1。
(3)dist[j]>=0 && g[k][j]==1
   若dist[j]并且k和j之间有通路,或-dist[k]+1<dist[j],也就是经过k对于j来说上车次数更少,则调整经过k站能到达的其余各站的上车次数。
(4)-dist[k]+1
   让dist[j]取经过k的更少上车次数-dist[k]+1。
(5)k<0?-1:j-1
   若k小于0,表示无解;否则返回j-1也就是上车次数减1。
转载请注明原文地址:https://kaotiyun.com/show/RrDZ777K
0

最新回复(0)