数据结构考研分类复习真题 第三章 答案[19]

（）A和D是合法序列B和C 是非法序列

（）设被判定的操作序列已存入一维数组A中

int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列如是返回true否则返回false

{i=; //i为下标

j=k=; //j和k分别为I和字母O的的个数

while(A[i]!=\) //当未到字符数组尾就作

{switch(A[i])

{caseI: j++; break; //入栈次数增

caseO: k++; if(k>j){printf(序列非法\n)exit();}

}

i++; //不论A[i]是I或O指针i均后移}

if(j!=k) {printf(序列非法\n)return(false);}

else {printf(序列合法\n)return(true);}

}//算法结束

[算法讨论]在入栈出栈序列（即由I和O组成的字符串）的任一位置入栈次数（I的个数）都必须大于等于出栈次数（即O的个数）否则视作非法序列立即给出信息退出算法整个序列（即读到字符数组中字符串的结束标记\）入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空）否则视为非法序列

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []