广东工业大学数据结构aniview系统第三章参考答案.docxVIP

广东工业大学数据结构 Aniview 第三章参考答案 ◆3.17③ 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如序列 1序列 2模式的字符序列。其中序列 1 和序列 2 中都不含字符，且序列 2 是序列 1 的逆序列。例如，a+bb+a是属该模式的字符序列，而1+33-1则不是。 实现下列函数: Status match(char *str); /* 若 str 是属该模式的字符序列，*/ /* 则返回 TRUE，否则返回 FALSE */ Stack 是一个已实现的栈。 可使用的相关类型和函数： typedef char SElemType; // 栈 Stack 的元素类型 Status InitStack(Stack s); Status Push(Stack s, SElemType e); Status Pop(Stack s, SElemType e); Status StackEmpty(Stack s); Status GetTop(Stack s, SElemType e); Status match(char *str) /* 若 str 是属该模式的字符序列，*/ /* 则返回 TRUE，否则返回 FALSE */ { Stack S; int i; SElemType e; InitStack(S); for(i=0;str[i]!=;i++) { Push(S,str[i]); } for(i=i+1;!StackEmpty(S)str[i]!=@;i++) { Pop(S,e); if(e!=str[i]) { return FALSE;} } if(StackEmpty(S)str[i]==@) { return TRUE;} } 3.18② 试写一个判别表达式中开、闭括号是否配对出现的算法。 实现下列函数： Status MatchCheck(SqList exp); /* 顺序表 exp 表示表达式； */ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ /*  注：本函数不使用栈  */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表 Status MatchCheck(SqList exp) /* 顺序表 exp 表示表达式；  */ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ /* 注：本函数不使用栈 //exp 里面是纯括号，纯小括号 { int l=0,i;  */ for(i=0;iexp.length;i++) { if(exp.elem[i]==() { l++;} if(exp.elem[i]==)) {l--; if(l0) return FALSE;//没左，先右 } } if(l0) return FALSE;//有左，没右 else return TRUE; } ◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号( 和 )，方括号[和]和花括号{和}，且这三种括号可按任意的 次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。 实现下列函数： Status MatchCheck(SqList exp); /* 顺序表 exp 表示表达式； */ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表 Stack 是一个已实现的栈。 可使用的相关类型和函数： typedef char SElemType; // 栈 Stack 的元素类型 Status InitStack(Stack s); Status Push(Stack s, SElemType e); Status Pop(Stack s, SElemType e); Status StackEmpty(Stack s); Status GetTop(Stack s, SElemType e); Status MatchCheck(SqList exp) /* 顺序表 exp 表示表达式； */ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ { int i; Stack S; ElemType l; InitStack(S); for(i=0;iexp.