解：

BOOL Symmetry(char a[]) {

int i=0; Stack s;

InitStack(s); ElemType x;

while(a[i]!='&' && a[i]){ Push(s,a[i]); i++; }

if(a[i]) return FALSE; i++;

while(a[i]){ Pop(s,x); if(x!=a[i]){

DestroyStack(s); return FALSE; } i++; }

return TRUE; }

3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。

解：

BOOL BracketCorrespondency(char a[]) {

int i=0; Stack s;

InitStack(s); ElemType x; while(a[i]){

switch(a[i]){ case '(':

Push(s,a[i]); break; case '[':

Push(s,a[i]); break; case ')':

GetTop(s,x);

if(x=='(') Pop(s,x); else return FALSE; break;

精选

case ']':

GetTop(s,x);

if(x=='[') Pop(s,x); else return FALSE; break; default: break; } i++; }

if(s.size!=0) return FALSE; return TRUE; }

3.20 假设以二维数组g(1…m, 1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。

解：

#include #include

typedef struct{ int x; int y; }PosType;

typedef struct{ int Color; int Visited; PosType seat; }ElemType;

#include \

#define M 8 #define N 8

ElemType g[M][N];

void CreateGDS(ElemType g[M][N]);

void ShowGraphArray(ElemType g[M][N]);

void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);

int main() {

CreateGDS(g);

精选

ShowGraphArray(g);

PosType StartPos; StartPos.x=5; StartPos.y=5; int FillColor=6;

RegionFilling(g,StartPos,FillColor); cout<

ShowGraphArray(g); return 0; }

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

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;

if(CurPos.x

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

Push(s,g[CurPos.x+1][CurPos.y]); if(CurPos.x>0 &&

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

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

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

Push(s,g[CurPos.x][CurPos.y+1]); if(CurPos.y>0 &&

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

精选

)

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

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

int i,j;

for(i=0;i

for(j=0;j

for(i=2;i<5;i++) for(j=2;j<4;j++) g[i][j].Color=3; for(i=5;i

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

int i,j;

for(i=0;i

cout<

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

解：

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

void InversePolandExpression(char Buffer[]) {

Stack s;

InitStack(s); int i=0,j=0; ElemType e;

Push(s,Buffer[i]);

精选

i++;

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

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

else{ // 是操作符 GetTop(s,e);

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

Push(s,Buffer[i]); i++; } } }

while(!StackEmpty(s)){ Pop(s,e); Buffer[j]=e; j++; } }

Status IsOpertor(char c) {

char *p=\ while(*p){ if(*p==c)

return TRUE; p++; }

return FALSE; }

Status Prior(char c1,char c2) {

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

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

if(i==2) i--; // 加和减可认为是同级别的运算符

精选