第三章 栈与队列
typedef struct{
Elemtype *base[];
Elemtype *top[];
}BDStacktype; //双向栈类型
Status Init_Stack(BDStacktype &twsint m)//初始化一个大小为m的双向栈tws
{
twsbase[]=(Elemtype*)malloc(sizeof(Elemtype));
twsbase[]=twsbase[]+m;
twstop[]=twsbase[];
twstop[]=twsbase[];
return OK;
}//Init_Stack
Status push(BDStacktype &twsint iElemtype x)//x入栈i=表示低端栈i=表示高端栈
{
if(twstop[]>twstop[]) return OVERFLOW; //注意此时的栈满条件
if(i==) *twstop[]++=x;
else if(i==) *twstop[]=x;
else return ERROR;
return OK;
}//push
Status pop(BDStacktype &twsint iElemtype &x)//x出栈i=表示低端栈i=表示高端栈
{
if(i==)
{
if(twstop[]==twsbase[]) return OVERFLOW;
x=*twstop[];
}
else if(i==)
{
if(twstop[]==twsbase[]) return OVERFLOW;
x=*++twstop[];
}
else return ERROR;
return OK;
}//pop
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(sc);
*(q++)=c; //把H接在后部
}
}//Train_arrange
int IsReverse()//判断输入的字符串中&前和&后部分是否为逆串是则返回否则返回
{
InitStack(s);
while((e=getchar())!=&)
push(se);
while((e=getchar())!=@)
{
if(StackEmpty(s)) return ;
pop(sc);
if(e!=c) return ;
}
if(!StackEmpty(s)) return ;
return ;
}//IsReverse
Status Bracket_Test(char *str)//判别表达式中小括号是否匹配
{
count=;
for(p=str;*p;p++)
{
if(*p==() count++;
else if(*p==)) count;
if (count<) return ERROR;
}
if(count) return ERROR; //注意括号不匹配的两种情况
return OK;
}//Bracket_Test
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(sc);
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
typedef struct {
int x;
int y;
} coordinate;
void Repaint_Color(int g[m][n]int iint jint color)//把点(ij)相邻区域的颜色置换为color
{
old=g[i][j];
InitQueue(Q);
EnQueue(Q{Ij});
while(!QueueEmpty(Q))
{
DeQueue(Qa);
x=ax;y=ay;
if(x>)
if(g[x][y]==old)
{
g[x][y]=color;
EnQueue(Q{xy}); //修改左邻点的颜色
}
if(y>)
if(g[x][y]==old)
{
g[x][y]=color;
EnQueue(Q{xy}); //修改上邻点的颜色
}
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
{
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;
pop(s,b);
c=link(link(*p,b),a);
push(s,c);
}//else
p++;
}//while
pop(s,new);
if(!StackEmpty(s)) return ERROR;
return OK;
}//NiBoLan_to_BoLan
分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).
3.24
Status g(int m,int n,int &s)//求递归函数g的值s
{
if(m==0&&n>=0) s=0;
else if(m>0&&n>=0) s=n+g(m-1,2*n);
else return ERROR;
return OK;
}//g
3.25
Status F_recursive(int n,int &s)//递归算法
{
if(n<0) return ERROR;
if(n==0) s=n+1;
else
{
F_recurve(n/2,r);
s=n*r;
}
return OK;
}//F_recursive
Status F_nonrecursive(int n,int s)//非递归算法
{
if(n<0) return ERROR;
if(n==0) s=n+1;
else
{
InitStack(s); //s的元素类型为struct {int a;int b;}
while(n!=0)
{
a=n;b=n/2;
push(s,{a,b});
n=b;
}//while
s=1;
while(!StackEmpty(s))
{
pop(s,t);
s*=t.a;
}//while
}
return OK;
}//F_nonrecursive
3.26
float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法
{
if(abs(p^2-A)<=e) return p;
else return sqrt_recurve(A,(p+A/p)/2,e);
}//Sqrt_recurve
float Sqrt_nonrecursive(float A,f
