C语言程序编制度量精解
高级程序员级C语言编程试题有一定的浓度和难度。根据新的考试大纲，每年有两道必考的C语言编程试题，考试试题更注重于算法理解和实现方面，在解答试题的过程中，一定要记住要严格按照试题说明提供的算法展开思路，而不是在了解了程序的功能后按照自己推断的算法去理解程序。这一点有必要在复习备考过程中加以重视，具体的方法就是在阅读试题说明过程中不产生自己的算法中，以理解并接受试题说明的内容为目标。
试题1（2000年试题5）
阅读下列程序说明和C代码，就填入（n）处的字句在答卷的对应栏内。
［程序说明］
下列文法可用来描述化学分子式的书写规则（例如，AL2（CO3）3、Cｕ（OH）2）：
λ→β|βλ
β→δ|δn
δ→ξ|ξθ|(λ)
其中λ是一个分子式；δ或是一个元素，或是一个带括号的（子）分子式；元素或是一个大写字母（记为ξ），或是一个大写字母和一个小写字母（记为ξθ）；β或是一个δ，或是在δ之后接上一个整数n；δn表示β有n个δ的元素或（子）分子式。一个完整的分子式由若干个β组成。
当然一个正确的分子式除符合上述文法规则外，还应满足分子式 本身的语义要求。
下面的程序输入分子式，按上述文法分析分子式，并计算出分子式的分子量。例如：元素H的原子量是1，元素O的原子量是16。输入分子式H2O，计算出它的分子量为18（1＊2＋16）。程序中各元素的名及它的原子量从文件atom.dat中读入。
［程序］
#include <stdio.h>
#include <string.h>
#define MAXN 300
#define CMLEN 30
struct elem {char name[3]; /* 元素名
*/
Double v; /* 原子量
*/
}nTbl [MAXN];
char cmStr [CMLEN], *pos;
int c; FILE *fp;
double factor();
double atom() /* 处理文法符号
*/
{ char W[3];int i; double num;
while ((c=*pos++)= =''||c= ='\t'; /*
掠过空白字符 */
if (c= ='\n')
return 0.0;
if(c>='A'&& c<='z') { /* 将元素名存入W */
w[i=0]=c; c=*pos++;
If (c>='a'&& c<='Z') w[++i]=c;
Else pos--;
W[++i]='\0';
For (I=0;nTbl[i],v>0.0;i++)
If(strcmp(w,nTbl[i],name)= =0)
return nTbl[i],v;
Prinft("元素表中没有所输入的元素：\t%s\n",w);
return -1.0;
} else if (c= = '(') {
if((num= (1) )<0.0)
return -1.0; /* 包括可能为空的情况
*/
if(*pos++!=')')
{ printf ("分子式中括号不匹配！\n");
return -1.0
return num;
}
prinft("分子式中存在非法字符：\t%c\n",c);
return -1.0;
}
double mAtom() /* 处理文法符号β
*/
{
double num; int n=1;
if((num= (2) )<0.0)
return -1.0;
c=*pos++;
if(c>='0'&& c<='0')
n=0;
while 9c>='0'&& c<='9')
{
n= (3) ;
c=*pos++;
}
}
pos--;
return num *n
}
double factor() /* 处理文法符号λ
*/
{
double num=0.0,d;
if((num=mATom())<0.0)
return -1.0;
while)*pos>='A'&& pos<='Z'||pos= ='(')
{
if((d= (4) )<0.0)
return -1.0;
(5) ;
}
}
void main()
{
char fname[ ]="stom.dat"; /* 元素名及原子量文件*/
int i;double num;
if((fp=fopen(fname,"r"))= =NULL) /*
以读方式打开正文文件 */
{
prinft("Can not open %s file.\n",fname);
return; /* 程序非正常结束
*/
}
i=0;
while (i<MAXN && fscanf (fp,"%s%1f",nTb1[i].name,& nTb1[i].v= =2)
i++;
fclose(fp);
nTb1[i].v=-1.0;
while(1)
{ /* 输入分子式和计算分子量循环，直至输入空行结束 */
prinft("\n输入分子式！（空行结束）\n";gets(cmStr);
pos=cmStr;
if(cmStr[0]= ='\0')
break;
if(num=factor())>0.0)
if(*pos!='\0')
printf("分子式不完整！\n");
else
printf("分子式的分子量为f\n",num);
}
}
[解析]
首先要仔细阅读并理解程序说明中所提供的文法规则。只有充分掌握这些规则，解答才会有规律可循。在下面的解析中我们将始终结合方法规则来解答试题。
粗读程序，不难发现程序中对3个函数的调用都很简单，由于字符串指针pos是全局变量，各函数在进行处理时直接对pos进行处理，然后返回自己所计算的那一部分分子式的分子量。
对程序的阅读要从主函数main()开始。从第51行到第64行都很好理解，一直到第65行才能看到对函数factor()的调用。很显然，在调用函数factor()后，返回值num即是分子式，当然，在分子式不合乎文法规则时，
num是一个负数。那么我们就开始研读函数factor()。
我们先看关于的文法规则：λ→β\βλ。这就是说，λ或者是由β构成，或者是由构成。处理的时候应该区分这两种情况，即处理完了β之后应该判断其后是否有λ，如果有λ，应对其进行处理。
那么程序中是如何表述的呢？很明显，第45行处理了λ起始部分的β。在没有涉及到函数
mStom() 更多内容时，我们只要知道mAtom()的返回值（分子量或者是表示分子式有问题的－1.0）赋给
num就可以了。第46行的 while循环条件如何理解？结合以上对文法规则：、的分析，我们不难判断，这是判断其后是否还有一个λ或β。第47行显然应该是一个函数调用语句（比较第65行和45行，不难发现本程序中调用函数的常用语句形式）。这里应该调用什么函数？处理λ和β的过程基本相似，这里可以调用函数
factor()，也可以调用函数 mAtom()。
基于以上的理解，在函数调用成功的情况下，整型变量d的值应该是函数调用返回的分子量。从第49行我们可以判定，函数factor()中整型变量num是用来存储分子量的。那么第47行的函数调用返回值就应该累加到num中，这是一个简单的操作，其C语言实现也很容易。
在研读函数mAtom()之前，我们先看看关于β的文法规则：β→δ|δn。这就是说，β或者由δ构成，或者由δ和一个整数n构成。这样，在处理完了δ后，一定要确认其后是否跟着一个整数n。
不难判断，第32行的填空（3）处需要填写的是对某个函数的调用（与第47行的判断文法相同）。但是这个函数是谁呢？如果我们注意文法的相同之处，结合函数factor()的结构，不难判断这里是调用处理δ的函数，即函数atom()。将δ的分子量计算出来赋给num。注意，这里的判断还需要在以后进行确认，目前我们暂且这样认定。
从第34行开始，熟悉C语言的程序员都能够看出这是在判断c是否为一个数字字符。显然，如果是一个数字字符，就应该把它转换成数字。从第41行可以看出，转换以后的数字存储在变量n中。这样，第36行的语句就是完成字符到数字的转换的。而且从此处使用一个循环结构可以看出这里可以处理若干位的数字。从数字字符向数字的转换应该是很容易的，在这里，就应该描述为"n*10+c-'0'"。
回过头来仔细阅读这个函数，在实现程序功能方面没有潜在的逻辑错误，我们能够确认这样填写是符合要求的。
现在看函数atom()。该函数是处理文法符号δ的。文法符号δ的文法规则是δ→ζ|ζθ|(λ)。不妨借助解读上两个函数的文法来解读该函数。从第15行到第21行处理了前两种情况，即ζ是一个大写字母或一个大写字母和一个小写字母。到第22行，从判断c是否为'（'，可以看出这是处理第3种情况了。如何处理呢？第23行是一个函数调用（判断文法同上），由于在'（'之后是一个λ，显然，此后的函数调用应该是处理λ的函数，即函数factor()。
这里的解题过程非常简单，即将程序与文法规则紧密结合，通过文法符号的处理来解题。首先要将程序中的语句与文法规则对应起来，然后就能够理解程序中的处理流程了。
［答案］
(1) factor()
(2) atom()
(3) n*10+c-'0'
(4) mAtom()或factor()
(5) num+=d
试题2
（2000年试题6）
阅读下列程序说明和C代码，将就填入（）处的字句在答卷的对应栏内。
［程序说明］
某城市有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 <studio.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;
prinft("输入公交线路数\n");
scanf("%d%d",&m,&n);
for(i=0;i<n;j++) /* 邻接矩阵清0
*/
for(j=0;j<n;j++)
g[i][j]=0;
for(i=0;i<m;i++)
{
prinft ("沿第条公交线路并进方向的各站编号
(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++)/*调整经过站能达到的其余各站的上车次数*/
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）有向图G中的数据是如何说明两站之间有无公交线路的，"若有某条公交线路经i站能达到j站，就在顶点i到顶点j之间设置一条权为1的有向边<i,j>"；（2）如何确定最少换车次数，"从站点x至y站点的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1"。
综合程序结构，可以看到程序由4各部分组成：（1）文件包含和全局数据定义；（2）用于建立有向图G的函数buildG()；（3）用于求出从站点0到站点n-1最少换车次数的函数minLen()；（4）主函数main()。
结合注释，我们可以从第1部分中明确3个数组的含义，由此确定他们在程序中的应用。数组a[N+1]用于存放一条公交线路上的个站编号；数组g[N][N]存储对应的邻接矩阵；dist[N]用于存储站点0到各站点的最短路径。下面我们来分析函数buildG()。
在函数中用到的变量有m、n、i、j、k、sc、dd等。由第10行和第11行可以看出，m表示公交线路数，n表示公交站数；由第17行可以看出，sc为当前线路站点计数器；其余i、j、k的不过用作循环变量而已。至于dd的用途，一时还难以确定。
结合注释部分阅读程序，从第10行到第13行都是很好理解的。从14行起的for循环，结束于第27行，构成本函数的主体，而且此后即是函数的结束，由此可以判定该循环完成输入各条线路并建立有向图的任务。
建立有向图，应该包括两个步骤，一是输入一条路径上的各个顶点，二是将输入路径的信息反映到邻接矩阵中去。将以上两个步骤套在一个循环中，反复执行即可完成有向图的建立。
研读第14行至第27行的for循环，可知在处理完m条公交线路后结束循环。分析循环体，这部分的结构是清晰的，除第15、16、17和23行外，由两个内层循环构成，即第18行至第22行的while循环和第24行到26行的for循环。
先研究while循环。由第15、16和17行与输入语句可知该循环完成一条公交线路上各个站点的输入。从第19行可知，dd表示的是一个公交站点的编号。跳过第20行，我们看到这里有的"dd>=0
&& dd<n"条件，这进一步印证了上面我们关于dd的判断。那么，既然dd是一个站点编号，在输入站点编号之后，我们首先要将其记入公交线路a[
]中，这里只有填空（1），别无语句，我们只好在这里填写完成该任务。同时还要注意到，作为当前线路站计数器，在while循环中没有对其进行修改的语句，所以在记入一个公交站点时，应相应的修改sc。鉴sc的初值是0，我们必须在这里填写"a[sc++]=dd"，如果使用"++sc"将会使a[0]无值，也就是说公交线路的第一个站点将被遗漏。
借助注释，不难确定从第24行到26行的for循环完成将该条公交线路站点信息反映到邻接矩阵中的任务。考虑到公交线路是单向运行的，所以这里的操作也就是使公交线路上任意站点到其后任意站点之间存在一条权值为1的有向边。这样就需要使用一个二重循环，通过外层循环依次处理公交线路上的各个站点，通过内层循环将在站点前各站点与该站点之间设置一条为权1的有向边。
很明显，第26行就是完成上述内层循环任务的核心语句，这里应该怎样表述呢？从试题中我们可以看到填空（2）需要填写的应该是数组g[
] [ ]的下标。结合上面的分析，我们在这里填写"[a[j]] [a[k]]"是很自然的。这里一定要注意公交线路是单向运行的。
可能有的读者要对第24行的"k=1"表示困惑，因为这样便失去了处理公交线路的第一个站点a[0]的机会了。这里仍旧要强调公交线路的单向运行。因为在单向运行的公交线路上，通过该线路上的任何站点都不能到达该线路的第一个站点，所以在循环中就直接从"k=1"开始，跳过线路的第一个站点。
下面我们来研读函数minLen()。该函数中包含了3个填空，值得我们投入更多的精力来解答。
关于求有向图顶点到顶点之间最短路径，Dijkstra有一个标准的算法，我们先在这里描述这个算法，然后结合这个算法来理解程序。
设指定的顶点为v，把图中顶点集合分成两组，已求出最短路径的顶点集合为第一组，设为S，其余的尚未最短路径的顶点集合为第二组。按最短路径长度递增次序逐个把第二组中的顶点移入S中，直至从顶点v出发可以到达的顶点都在S中。在这个过程中，需要始终保持从v到S中各个顶点的最短路径都不大于从v到第二组中任何顶点的最短路径长度。另外，为了便于程序处理，要为每个顶点保存一个距离。S中的顶点距离就是从v到此顶点的最短路径长度，第二组中的顶点的距离就是从v到此顶点的只包括以S中的顶点为中间顶点的那部分还不完整的最短路径长度。
根据以上描述，结合对程序的理解，就不难理解第38行到第40行的循环所处理的内容了，即调整经过站能到达的其余各站的上车次数。具体分两种情况：1、当存在从站k到站j的直通公交线路时，如果已经暂时确定了从站0到站j的最少上车次数(dist[j]>0)，在这种情况下，如果从站0经站k换车到站j的上车次数小于已经确定的从站0到站j的最少上车次数,则应该将经过站k到站j的上车次数(-dist[k]+1)确定为目前从站0到站j的最少上车次数。2。当存在从站k到站j的直通公交线路时，如果从站0到站j没有直通公交线路(dist[j]=
=0)，应该取经过站k到站j的上车次数(-dist[k]+1)为目前从0站到站j的最少上车次数。
将以上的分析翻译为C语言语句，那么填写（3）和填空（4）的解答就非常明显了，它们分别为"(dist[j]>=0
&& g[k][j]= =1"和"-dist[k]+1"。细心的读者要问，在第39行中已经给出"dist[j]=0"的判断了，在填空（3）中还有必要再反映这一点吗？这是有必要的，如果我们在填空时不反映这一点，那么当dist[j]==0时将不进行调整处理，显然是不符合要求的。既然有了要填空的"dist[j]==0"，第39行中已经有的那个"dist[j]==0"还有存在的必要吗？答案是肯定的，这里就不再详细解释了，读者可以自己理解。
至于填空（5），不过是函数最后的回送返回值的语句而已。结合第48行和第49行，发现返回值有两种情况：1、无解（t<0）；2、有解（t>0）。显然在填空（5）中要处理好这两种情况。
要处理好这两种情况，必须从k的值入手。我们看第36行，可知在循环结束时k的值有两种情况，一是k<0，二是k=n-1。显然，k<0是程序无解的标志。那么我们在这里就应该在k<0让函数返回一个负数，否则就返回从站0到站n-1的0最少换车次数（dist[n-1]-1）。因为在第42行中已经将dist[n-1]赋给j，所以我们可以构造填空（5）的答案为"k<0?-1:j-1"。
解答完本题，我们应该吸取的经验就是要切实掌握各种算法，同时要掌握各种算法在实际中的应用，通过程序语句与算法来解答题目。在过去几年中，最后一道C语言程序填空试题几乎都是关于回溯法的程序，其实也是关系到算法的掌握和应用。切实掌握了算法的实现，就可以非常容易地将程序（或函数）划分为几个部分，各部分都实现算法中的某一步骤。这样，结合试题的具体情况就能够快速写出正确的答案。
［答案］
（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
|
