广东工业大学数据结构Aniview系统第三章参考答案.docx
《广东工业大学数据结构Aniview系统第三章参考答案.docx》由会员分享,可在线阅读,更多相关《广东工业大学数据结构Aniview系统第三章参考答案.docx(12页珍藏版)》请在三一文库上搜索。
1、广东工业大学数据结构 Aniview 第三章参考答案3.17 试写一个算法,识别依次读入的一个以为结束符的字符序列是否为形如序列 1&序列 2模式的字符序列。其中序列 1 和序列 2 中都不含字符&,且序列 2 是序列 1 的逆序列。例如,a+b&b+a是属该模式的字符序列,而1+3&3-1则不是。实现下列函数:Status match(char *str);/* 若 str 是属该模式的字符序列,*/* 则返回 TRUE,否则返回 FALSE*/Stack 是一个已实现的栈。可使用的相关类型和函数:typedef char SElemType; / 栈 Stack 的元素类型Status I
2、nitStack(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 match(char *str)/* 若 str 是属该模式的字符序列,*/* 则返回 TRUE,否则返回 FALSE*/ Stack S; int i; SElemType e; InitStack(S); for(i=0;stri!=&;i+) Push(S,stri); f
3、or(i=i+1;!StackEmpty(S)&stri!=;i+)Pop(S,e);if(e!=stri) return FALSE;if(StackEmpty(S)&stri=) return TRUE;3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。实现下列函数:Status MatchCheck(SqList exp);/* 顺序表 exp 表示表达式;*/* 若 exp 中的括号配对,则返回 TRUE,否则返回 FALSE */*注:本函数不使用栈*/顺序表类型定义如下:typedef struct ElemType *elem;intlength;intlistsize
4、; SqList;/ 顺序表Status MatchCheck(SqList exp)/* 顺序表 exp 表示表达式;*/* 若 exp 中的括号配对,则返回 TRUE,否则返回 FALSE */* 注:本函数不使用栈/exp 里面是纯括号,纯小括号int l=0,i;*/for(i=0;iexp.length;i+)if(exp.elemi=() l+;if(exp.elemi=)l-;if(l0) return FALSE;/有左,没右else return TRUE;3.19 假设一个算术表达式中可以包含三种括号:圆括号( 和),方括号和和花括号和,且这三种括号可按任意的次序嵌套使用(
5、如:())。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。实现下列函数:Status MatchCheck(SqList exp);/* 顺序表 exp 表示表达式;*/* 若 exp 中的括号配对,则返回 TRUE,否则返回 FALSE */顺序表类型定义如下:typedef struct ElemType *elem;intlength;intlistsize; SqList;/ 顺序表Stack 是一个已实现的栈。可使用的相关类型和函数:typedef char SElemType; / 栈 Stack 的元素类型Status InitS
6、tack(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 */ int i; Stack S; ElemType l; InitStack(S); for(i=0;iexp.length;
7、i+)if(exp.elemi=(|exp.elemi=|exp.elemi=) Push(S,exp.elemi); if(exp.elemi=)|exp.elemi=|exp.elemi=)if(StackEmpty(S) return FALSE; /无左括号匹配 elsePop(S,l);switch(l) /有左括号匹配,但是括号不匹配 case (:if(exp.elemi!=) return FALSE; break;case :if(exp.elemi!=) return FALSE;break;case :if(exp.elemi!=) return FALSE;if(Sta
8、ckEmpty(S) return TRUE;else return FALSE;/左括号多余3.20 假设以二维数组 g(1.m,1.n)表示一个图像区域,gi,j表示该区域中点(i,j)所具颜色,其值为从 0 到 k 的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。实现下列函数:void ChangeColor(GTYPE g, int m, int n,char c, int i0, int j0);/* 在 g1.m1.n中,将元素 gi0j0 */* 所在的同色区域的颜色置换为颜色 c*/表示图像区域的类型定义如下:
9、typedef char GTYPEm+1n+1;Stack 是一个已实现的栈。可使用的相关类型和函数:typedef int 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, in
10、t n,char c, int i0, int j0)/* 在 g1.m1.n中,将元素 gi0j0 */* 所在的同色区域的颜色置换为颜色 c*/Stack S;int x,y,di=1;/di 代表东北西南四个方向char color;StackInit(S,(m+1)*(n+1);x=i0;y=j0;if(x=0|ym|yn) exit(OVERFLOW);color=gxy;/总体的思路是,从 gi0j0开始/对每个符合所求的元素的依次找东北西南,/即先找当前元素的东边,没有找北边,若北有,向北走一步,/再找(走到的那个元素)的东边,依次类推/直到最后一个元素东北西南都被找过了,就回退
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广东工业大学 数据结构 Aniview 系统 第三 参考答案
链接地址:https://www.31doc.com/p-7196048.html