阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。【说明】 设某城市有n个车站,并有m条公
阅读下列程序说明和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。
【函数5-9】
include <stdio.h>
define M 20
define N 50
int a[N+1]; /*用于存放一条线路上的各站编号*/
iht 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[i][j] = 0;
for(i=0; i<m; i++){
printf("沿第%d条公交车线路前进方向的各站编号(O<=编号<=%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 pdnff("从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) k0 ?-1:j-1 解析:本题考查图的应用——求最少换车次数。
函数buildG的功能是输入车站数、公交线路数,以及各公交线路的车站等信息,然后构建有向图的邻接矩阵。对每一条线路,按从始发站至终点站的顺序输入线路上的车站编号。空 (1)所在while循环正是用来顺序读入某一条线路上的车站编号。为了实现输入-1表示结束,先将输入值保存在临时变量dd中,若dd不为-1,则将dd的值保存到数组a中,sc是当前线路站计数器,注意到while循环体中并没有类似sc++的语句,故空(1)应填a[sc++]=dd。
某条新路输入完毕后,用for循环来构建有向图G中关于该条线路的邻接矩阵。根据邻接矩阵的定义易得,空(2)应填“[a[j]][a[k]]”。
函数minLen的功能是根据图G的邻接矩阵求从站0到站n-1的最少换车次数。函数中采用求两点间最短路径的算法。先将邻接矩阵的第0行内容复制到数组dist[],并置dist[0]为1。这样,就在dist[]中预置了能从站0出发直接到达的车站。接着是一个循环,每次循环做以下事情:利用数组dist[],找出下一个最少上车次数的站号。如果没有这样的站号(站0不可达站n-1),或下一个最少上车次数的站就是n-1(找到解),则结束循环。若找到下一个最少上车次数的车站但还不是n-1号站,则设置该站已求得站0到达该站所需最少上车次数dist[k];将dist[k]的值变为负值。值为负就表示已为站k求得解,到达站k的最少上车次数为-dist[k]。由于已求得站k最少上车次数,那些还未求得的最少上车次数、经过k站可以达到的车站的上车次数应做相应调整。顺序考查各站j(站0除外),若站j还未求得解(dist[j]>0),并且经站 k能直接到达站j(g[k][j]=1),并且或从站0不能到达站j,或到达站j的上车次数比经过站k到达的次数要多(dits[j]==0|| -dist[k]+1dist[j]),则到达站j的最少上车次数改为-dist[k]+1。故空(3)应为“dist[j]>=0&& g[k][j]==1”,空(4)应填“-dist[k]+1”。
求解循环结束有两种情况,一是没有找到下一个最少上车次数的站(k0),二是下一个最少上车次数的站就是n-1号站。若是前者,函数因未找到解而返回-1(任意负值均可);若是后一种情况,从站0到站n-1上车次数为dist[n-1],即换车次数是dist[n-1]-1。故空
(5)应填“k0 ?-1:j-1”。
全集U=R,集合M={x|(x+4)(1-2x)>0},N={x|x2>=16,x属于R-}则集合 数学 2020-04-05 …
1.2项式定理和概率有啥关系呢?2.(a+b)^n,这个n应该是属于自然数吧?那应该包括0吧?那万 数学 2020-05-20 …
一条粗细均匀的导线的电阻为48Ω,若把它切成n段,再把n段并联起来,导线电阻变为3Ω,那么n应等于( 职业技能鉴定 2020-05-30 …
已知集合M={x|-3小于x小于等于5}N={x|x小于-5或x大于5}M并N怎已知集合M={x| 数学 2020-06-20 …
选出下列各组中加粗词注音有错误的一项[]A.教诲(huì)狭隘(ài)淳朴(chún)处置(chǔ 语文 2020-07-06 …
阅读下列材料:《汉穆拉比法典》(片段)19、倘藏匿此奴隶于其家而后来奴隶被破获,则此自由民应处死。 历史 2020-07-08 …
1.在等差数列{an}中,a1+a2+a3=15,an+a(n-1)+a(n-2)=78,sn=1 数学 2020-07-18 …
设集合M={(x,y)|y=x,x,y属于R},M={(x,y)|x2+y2=0,x,y属于R}, 数学 2020-08-02 …
若√2m+2n-5与n-1次的√m+n都是最简二次根式,并且是同类二次根式,求m.n应满足的条件. 数学 2020-08-02 …
关于数罪并罚中“先减后并”、“先并后减”的问题某犯罪被判处14年有期徒刑,执行10年后又犯新罪,被判 其他 2020-11-06 …