第三章栈与队列 3.15 typedef struct( Ele 2] Elemtype *top[2]: BDStacktype;/双向栈类型 Status Init Stack (BDStacktype&tws,intm)∥/初始化一个大小为m的双向栈tws tws base[0](Elemtype*)malloc(sizeof(Elemtype) tws base[l=tws base[0]+m tws top[O]tws base[o] tws. top[lF=tws base[1] return OK i //nit Stack Status push( BDStacktype& wS, int i, Elemtype x入栈=0表示低端栈=1表示高 端栈 if(tws. top[ oPts. top[ D return OVERFLOW,∥/注意此时的栈满条件 if(i-0)*tws. top[0J++= Ise if(F=1)*tws. top[1]-- else return erROR: turn oK i//push Status pop( BDStacktype& tws, int 1, Elemtype&x/x出栈=0表示低端栈r=1表示 高端栈 if(i==0) if(tws top[O==tws base[od return OVERFLOw =*--tws top[O]: else if(F==1) f(tws top[1ltws base[ld return OVERFLOw x=*++tws. top[1]; else return erROR. eturn oK g//pop
第三章 栈与队列 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这里用字符串tain表示火车,H表示硬席S表示 软席 p= train, q≡tran Init Stack(s) if(*p=H)push(s,*p),把H存入栈中 else*(q++)=*p;/把S'调到前部 p+ while(!Stack Empty(s)) *(q+)=c;∥把H接在后部 i//Train arrange 3.17 int IsReverseo∥判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否 则返回0 Init Stack(s) while((e=getchar)I=&') push(s, e); while((e=getchar)I=@) f(Stack Empty(s) return 0: pop(s, c); if(el=c)retum 0 if(!Stack Empty (s)return 0 eturn 1 i//rEverse 3.18 Status Bracket Test(char*strm判别表达式中小括号是否匹配 count=0 for(p=str; *p p++)
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(count<0)return ERROR if(count) return error;∥注意括号不匹配的两种情况 eturn OK. i//Bracket Test 3.19 Status AllBrackets Test(char*stry判别表达式中三种括号是否匹配 Init Stack(s) for(p=str; *p; p++) if(p=cip=tp==0) push(s, "p); if(Stack Empty(s))return ERROR pop(s, c); if("p==)&&cl=o return ERROR if(p=]&&c!=T) return ERROR; if(*p=}&&c={) return error;∥必须与当前栈顶括号匹配 if(sTack Empty(s)) return ERROR; return OK i//AlIBrackets Test typedef struct i Int x i coordinate void Repaint Color(int gImJ[n), int i,int j, int color)//把点(i)相邻区域的颜色置换为 old=giLl Init Queue(Q) EnQueue(Q, (I,)) while(! QueueEmpty(Q)
if(*p=='(') count++; else if(*p==')') count--; if (count<0) 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; if(*p==']'&&c!='[') return ERROR; if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配 } }//for if(!StackEmpty(s)) return ERROR; return OK; }//AllBrackets_Test 3.20 typedef struct { . int x; int y; } coordinate; void Repaint_Color(int g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为 color { old=g[i][j]; InitQueue(Q); EnQueue(Q,{I,j}); while(!QueueEmpty(Q)) {
DeQueue(Q, a) xa. x,y-a. y X> if(glx-1y==old) glx-lty EnQueue(Q,{x-12y}),∥修改左邻点的颜色 if(glx]=old) glxly-1=color EnQueue(Q,{xy-l}),∥修改上邻点的颜色 f(x<m) if(gIx+1Ly]==old) g[x+1 ]ly=color EnQueue(Q,{x+1,y}),∥修改右邻点的颜色 if(glx]y+1]==old) glxly+1]color; EnQueue(Q,{xy+1}),∥修改下邻点的颜色 ∥whie i//Repaint Color 分析本算法采用了类似于图的广度优先遍历的思想用两个队列保存相邻同色点 的横坐标和纵坐标递归形式的算法该怎么写呢? 3.21 void NiBoLan(char* str char*new)∥/把中缀表达式str转换成逆波兰式new p=strq=new,∥为方便起见设str的两端都加上了优先级最低的特殊符号 InitStack(s,/s为运算符栈 if(*p是字母)*q+=*p,∥直接输出 else c=gettop( f(*p优先级比c高)push(s,*p)
DeQueue(Q,a); x=a.x;y=a.y; if(x>1) if(g[x-1][y]==old) { g[x-1][y]=color; EnQueue(Q,{x-1,y}); //修改左邻点的颜色 } if(y>1) if(g[x][y-1]==old) { g[x][y-1]=color; EnQueue(Q,{x,y-1}); //修改上邻点的颜色 } if(x<m) if(g[x+1][y]==old) { g[x+1][y]=color; EnQueue(Q,{x+1,y}); //修改右邻点的颜色 } if(y<n) if(g[x][y+1]==old) { g[x][y+1]=color; EnQueue(Q,{x,y+1}); //修改下邻点的颜色 } }//while }//Repaint_Color 分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点 的横坐标和纵坐标.递归形式的算法该怎么写呢? 3.21 void NiBoLan(char *str,char *new)//把中缀表达式 str 转换成逆波兰式 new { p=str;q=new; //为方便起见,设 str 的两端都加上了优先级最低的特殊符号 InitStack(s); //s 为运算符栈 while(*p) { if(*p 是字母)) *q++=*p; //直接输出 else { c=gettop(s); if(*p 优先级比 c 高) push(s,*p); else
whie( gettop(s)优先级不比*p低) pop(s,c),*(q++)=C; push(s,*p)∥运算符在栈内遵循越往栈顶优先级越高的原则 i/else p+ //while } NiBoLan∥参见编译原理教材 3.22 int get value nibolan(char*strm对逆波兰式求值 p= str: Init Stack(s),/s为操作数栈 if(*p是数)push(s,*p) els pop(s, a)' pop(s, b); r= compute(b,*p,a,∥假设 compute为执行双目运算的过程 i/else p++ i//while pop(s, r), return i//Get Value NiBoLa 3.23 Status nibolan to bolan(char*st, stringtype&new把逆波兰表达式str转换为 波兰式new p= str Initstack(s),/s的元素为 stringtype类型 while(°p) f*p为字母)push(s*p) if( StackEmpty(s))return ERROR pop(s if(Stack Empty(s))return ERROR
{ while(gettop(s)优先级不比*p 低) { pop(s,c);*(q++)=c; }//while push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while }//NiBoLan //参见编译原理教材 3.22 int GetValue_NiBoLan(char *str)//对逆波兰式求值 { p=str;InitStack(s); //s 为操作数栈 while(*p) { if(*p 是数) push(s,*p); else { pop(s,a);pop(s,b); r=compute(b,*p,a); //假设 compute 为执行双目运算的过程 push(s,r); }//else p++; }//while pop(s,r);return r; }//GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式 str 转换为 波兰式 new { p=str;Initstack(s); //s 的元素为 stringtype 类型 while(*p) { if(*p 为字母) push(s,*p); else { if(StackEmpty(s)) return ERROR; pop(s,a); if(StackEmpty(s)) return ERROR;