数据结构 第三章 栈与队列

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 (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); 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

if(g[x+1][y]==old) {

g[x+1][y]=color;

EnQueue(Q,{x+1,y}); //修改右邻点的颜色 } if(y

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 {