数据结构上机作业1-5章(4)

Status match(char *str)/* 若str是属该模式的字符序列，*/ /* 则返回TRUE，否则返回FALSE */ {

SqStack s; SElemType e; InitStack(s); int i=0;

while(str[i]!='&'&&str[i]!='@') {

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

if(str[i]=='@') return FALSE;

if(str[i]=='&') i++; while(str[i]!='@') {

Pop(s,e); if(e!=str[i]) return FALSE; i++; }

if(StackEmpty(s)&&str[i]=='@') return TRUE; else return FALSE; }

3.18② 试写一个判别表达式中开、闭括号是否配对出现的算法。 Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ { int i=0; int s=0;

while(exp.elem[i]!='\\0') {

if(exp.elem[i]=='(') s++;

if(exp.elem[i]==')') s--; } if(s==0)

return TRUE;

else return FALSE; }

实现下列函数：

Status MatchCheck(SqList exp);

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ 顺序表类型定义如下： typedef struct {

ElemType *elem; int length; int listsize; } SqList; // 顺序表

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号\和\，方括号\和\和花括号\和\，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。 实现下列函数：

Status MatchCheck(SqList exp);

/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ 顺序表类型定义如下： typedef struct {

ElemType *elem; int length; int listsize; } SqList; // 顺序表

Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e); Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ { SqStack Q;

int i=0; SElemType e; while(exp.elem[i]!='\\0') {

if(exp.elem[i]=='('||exp.elem[i]=='['||exp.elem[i]=='{') Push(Q,exp.elem[i]);

else if(exp.elem[i]==')'||exp.elem[i]==']'||exp.elem[i]=='}') { if(!StackEmpty(Q)) Pop(Q,e) ; else return FALSE;

if(e=='('&&exp.elem[i]!=')') return ERROR;

if(e=='['&&exp.elem[i]!=']') return ERROR;

if(e=='{'&&exp.elem[i]!='}') return ERROR; } i++; }

if(StackEmpty(Q)) return TRUE;

else return FALSE; }

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

实现下列函数：

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0); /* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */ 表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1]; Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status StackInit(Stack &s, int initsize); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e); void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0) /* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */ { Stack s;

int row,col;//行，列 InitStack(s); char f;

f = g[i0][j0]; g[i0][j0] = c; Push( s, i0); Push( s, j0);

while( !StackEmpty(s) ){ Pop( s, col ); Pop( s, row );

if( row > 1 && g[row-1][col] == f ){ Push( s, row-1); Push( s, col); g[row-1][col] = c; }

if( row < m && g[row+1][col] ==f ){ Push( s, row+1); Push( s, col);

g[row+1][col] = c; }

if( col > 1&& g[row][col-1] == f ){ Push( s, row); Push( s, col-1); g[row][col-1] = c; }

if( col < n && g[row][col+1] == f ){ Push( s, row ); Push( s, col+1 ); g[row][col+1] = c; } } }

◆3.21③ 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。 实现下列函数：

char *RPExpression(char *e);/* 返回表达式e的逆波兰式 */ Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s); int precede(char op) { int x; switch(op) {

case '*': x=2; break; case '/': x=2; break; case '+': x=1; break; case '-': x=1; break; default : x=0; }

return x; }

char *RPExpression(char *e)

{/* 返回表达式e的逆波兰式 */ char *c;

c=(char*)malloc(sizeof(char)*20); //不能用char c[] Stack s1; InitStack(s1);

int i=0,j=0; char ch; Push(s1,'@'); ch=e[i++]; while(ch …… 此处隐藏：1787字，全部文档内容请下载后查看。喜欢就下载吧 ……