数据结构习题集答案（C语言版严蔚敏）(10)

}

void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor) {

if(CurPos.x

Push(s,g[CurPos.x][CurPos.y+1]); !g[CurPos.x][CurPos.y-1].Visited && g[CurPos.x][CurPos.y-1].Color==OldColor if(CurPos.y>0 &&

Push(s,g[CurPos.x-1][CurPos.y]); !g[CurPos.x][CurPos.y+1].Visited && g[CurPos.x][CurPos.y+1].Color==OldColor if(CurPos.y

Push(s,g[CurPos.x+1][CurPos.y]); !g[CurPos.x-1][CurPos.y].Visited && g[CurPos.x-1][CurPos.y].Color==OldColor if(CurPos.x>0 &&

!g[CurPos.x+1][CurPos.y].Visited && g[CurPos.x+1][CurPos.y].Color==OldColor

Stack s; InitStack(s); ElemType e;

int OldColor=g[CurPos.x][CurPos.y].Color;

Push(s,g[CurPos.x][CurPos.y]); while(!StackEmpty(s)){

Pop(s,e); CurPos=e.seat;

g[CurPos.x][CurPos.y].Color=FillColor; g[CurPos.x][CurPos.y].Visited=1; PosType StartPos; StartPos.x=5; StartPos.y=5; int FillColor=6;

RegionFilling(g,StartPos,FillColor); cout<

ShowGraphArray(g);

}

void CreateGDS(ElemType g[M][N]) { }

void ShowGraphArray(ElemType g[M][N]) { }

3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。

解：

// 输入的表达式串必须为#...#格式

void InversePolandExpression(char Buffer[]) {

Push(s,Buffer[i]); Stack s; InitStack(s); int i=0,j=0; ElemType e; int i,j;

for(i=0;i

for(j=0;j

cout<

for(i=0;i

for(j=0;j

for(j=2;j<4;j++)

g[i][j].Color=3; g[i][j].seat.x=i; g[i][j].seat.y=j; g[i][j].Visited=0; g[i][j].Color=0;

}

)

Push(s,g[CurPos.x][CurPos.y-1]);

for(i=2;i<5;i++)

for(i=5;i

for(j=3;j<6;j++)

g[i][j].Color=3;

}

Status IsOpertor(char c) { }

Status Prior(char c1,char c2) {

char ch[]=\int i=0,j=0;

while(ch[i] && ch[i]!=c1) i++; if(i==2) i--;

// 加和减可认为是同级别的运算符

char *p=\while(*p){ }

return FALSE;

if(*p==c)

return TRUE; p++; i++;

while(Buffer[i]!='#'){ }

while(!StackEmpty(s)){ }

Pop(s,e); Buffer[j]=e; j++;

if(!IsOperator(Buffer[i])){ // 是操作数 }

else{ // 是操作符 }

GetTop(s,e);

if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退栈 } else{ }

Push(s,Buffer[i]); i++; Pop(s,e); Buffer[j]=e; j++;

Buffer[j]=Buffer[i]; i++; j++;

}

3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。

解：

char CalVal_InverPoland(char Buffer[]) { }

char Cal(char c1,char op,char c2) {

ch[0]=c2; ch[1]='\\0'; x2=atoi(ch);

int x,x1,x2; char ch[10]; ch[0]=c1; ch[1]='\\0'; x1=atoi(ch); while(Buffer[i]!='#'){ } return c;

if(!IsOperator(Buffer[i])){ } else{ } i++;

Pop(Opnd,e2); Pop(Opnd,e1); c=Cal(e1,Buffer[i],e2); Push(Opnd,c); Push(Opnd,Buffer[i]);

Stack Opnd; InitStack(Opnd); int i=0; char c;

ElemType e1,e2; if(i==4) i--; if(j==2) j--; if(j==4) j--;

if(i>=j) return TRUE; else return FALSE;

// 乘和除可认为是同级别的运算符

while(ch[j] && ch[j]!=c2) j++;

}

3.23 如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。

解：

#include #include #include

#include \

typedef char ARRAY[30]; typedef ARRAY ElemType; typedef struct NodeType{

ElemType data; NodeType *next; switch(op){ case '+': }

itoa(x,ch,10); return ch[0];

x=x1+x2; break; x=x1-x2; break; x=x1*x2; break; x=x1/x2; break; break;

case '-':

case '*':

case '/':

default:

}NodeType,*LinkType; typedef struct{

void InitStack(Stack &s);

Status Push(Stack &s,ElemType e); Status Pop(Stack &s,ElemType e); Status IsOperator(char c); Status StackEmpty(Stack s);

LinkType top; int size;

}Stack;