试题七(共 15 分)
阅读以下说明和C程序,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
现有 n(n < 1000)节火车车厢,顺序编号为 1,2,3,...,n,按编号连续依次从 A方向的铁轨驶入,从 B 方向铁轨驶出,一旦车厢进入车站(Station)就不能再回到 A方向的铁轨上;一旦车厢驶入 B 方向铁轨就不能再回到车站,如图 7-1所示,其中 Station 为栈结构,初始为空且最多能停放 1000 节车厢。
下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列,程序中使用了栈类
STACK,关于栈基本操作的函数原型说明如下:
void InitStack(STACK *s):初始化栈。
void Push(STACK *s,int e): 将一个整数压栈,栈中元素数目增 1。
void Pop(STACK *s):栈顶元素出栈,栈中元素数目减 1。
int Top(STACK s):返回非空栈的栈顶元素值,栈中元素数目不变。
int IsEmpty(STACK s):若是空栈则返回 1,否则返回 0。
【C 程序】
include<stdio.h>
/*此处为栈类型及其基本操作的定义,省略*/
int main( ){
STACK station;
int state[1000];
int n; /*车厢数*/
int begin, i, j, maxNo; /*maxNo 为 A端正待入栈的车厢编号*/
printf("请输入车厢数: ");
scanf("%d",&n);
printf("请输入需要判断的车厢编号序列(以空格分隔) : ");
if (n < 1) return -1;
for (i = 0; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */
scanf("%d",&state[i]);
(1) ; /*初始化栈*/
maxNo = 1;
for(i = 0; i < n; ){/*检查输出序列中的每个车厢号 state[i]是否能从栈中获取*/
if ( (2) ){/*当栈不为空时*/
if (state[i] == Top(station)){ /*栈顶车厢号等于被检查车厢号*/
printf("%d ",Top(station));
Pop(&station); i++;
}
else
if ( (3) ){
printf("error\n");
return 1;
}
else {
begin = (4) ;
for(j = begin+1; j<=state[i]; j++) {
Push(&station, j);
}
}
}
else { /*当栈为空时*/
begin = maxNo;
for(j = begin; j<=state[i]; j++){
Push(&station, j);
}
maxNo = (5) ;
}
}
printf("OK");
return 0;
}