严蔚敏《数据结构(c语言版)习题集》答案第三章 栈与队列.docVIP

严蔚敏《数据结构(c语言版)习题集》答案第三章 栈与队列 　　　　　　　　第三章 栈与队列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; //双向栈类型 Status Init_Stack(BDStacktype tws,int m)//初始化一个大小为m的双向栈tws { tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈 { if(tws.top[0]tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push Status pop(BDStacktype tws,int i,Elemtype x)//x出栈,i=0表示低端栈,i=1表示高端栈 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop 3.16 void Train_arrange(char *train)//这里用字符串train表示火车,H表示硬席,S表示软席 { p=train;q=train; InitStack(s); while(*p) { if(*p==H) push(s,*p); //把H存入栈中 else *(q++)=*p; //把S调到前部 p++; } while(!StackEmpty(s)) { pop(s,c); *(q++)=c; //把H接在后部 } }//Train_arrange 3.17 int IsReverse()//判断输入的字符串中前和后部分是否为逆串,是则返回1,否则返回0 { InitStack(s); while((e=getchar())!=) push(s,e); while((e=getchar())!=@) { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1; }//IsReverse 3.18 Status Bracket_Test(char *str)//判别表达式中小括号是否匹配 { count=0; for(p=str;*p;p++) { if(*p==() count++; else if(*p==)) count--; if (count0) return ERROR; } if(count) return ERROR; //注意括号不匹配的两种情况 return OK; }//Bracket_Test 3.19 Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配 { InitStack(s); for(p=str;*p;p++) { if(*p==(||*p==[||*p=={) push(s,*p); else if(*p==)||*p==]||*p==}) { if(StackEmpty(s)) return ERROR; pop(s,c); if(*p==)c!=() return ERROR