数据结构严蔚敏习题册 答案

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())!='&') {

if(e==’@’) return 0;//不允许在’&’之前出现’@’ 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 {

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)//求平方根的递归算法