第三章 严蔚敏《数据结构_c语言版_习题集》 栈及队列.pdf

第三章 栈与队列 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!=() r