广东工业大学数据结构Aniview系统第三章参考答案.pdf

《广东工业大学数据结构Aniview系统第三章参考答案.pdf》由会员分享，可在线阅读，更多相关《广东工业大学数据结构Aniview系统第三章参考答案.pdf（12页珍藏版）》请在装配图网上搜索。

1、广东工业大学数据结构Aniview第三章参考答案3 .1 7试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1 /*若str是属该模式的字符序列，*/*则返回TRUE，否则返回FALSE */ Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; /栈Stack的元素类型Status InitStack(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType Status match(c

2、har *str)/*若str是属该模式的字符序列，*/*则返回TRUE，否则返回FALSE */ Stack S; int i;SElemType e;InitStack(S);for(i=0 ;stri!=i+) Push(S,stri); for(i=i+1 ;!StackEmpty(S)i+) Pop(S,e);if(e!=stri) return FALSE;if(StackEmpty(S) 3 .1 8试写一个判别表达式中开、闭括号是否配对出现的算法。实现下列函数：Status MatchCheck(SqList exp);/*顺序表exp表示表达式；*/*若exp中的括号配对，则

3、返回TRUE，否则返回FALSE */*注：本函数不使用栈*/顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; 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

4、FALSE;/有左，没右else return TRUE; 3 .1 9假设一个算术表达式中可以包含三种括号：圆括号(和)，方括号和和花括号和，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。实现下列函数：Status MatchCheck(SqList exp);/*顺序表exp表示表达式；*/*若exp中的括号配对，则返回TRUE，否则返回FALSE */顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; SqList

5、; /顺序表Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; /栈Stack的元素类型Status InitStack(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType Status MatchCheck(SqList exp)/*顺序表exp表示表达式；*/*若exp中的括号配对，则返回TRUE，否则返回FALSE */ int i;Stack S;ElemType l;InitStack(S

6、);for(i=0 ;iexp.length;i+) if(exp.elemi=(|exp.elemi=|exp.elemi=) Push(S,exp.elemi);if(exp.elemi=)|exp.elemi=|exp.elemi=) if(StackEmpty(S) return FALSE; /无左括号匹配else Pop(S,l);switch(l) /有左括号匹配，但是括号不匹配case (:if(exp.elemi!=) return FALSE;break;case :if(exp.elemi!=) return FALSE;break;case :if(exp.elemi!

7、=) return FALSE; if(StackEmpty(S) return TRUE;else return FALSE;/左括号多余3 .2 0假设以二维数组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中，将元素gi0 j0 */*所在的同色区

8、域的颜色置换为颜色c */表示图像区域的类型定义如下：typedef char GTYPEm+1 n+1 ;Stack是一个已实现的栈。可使用的相关类型和函数：typedef int SElemType; /栈Stack的元素类型Status StackInit(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType void ChangeColor(GTYPE g, int m, int n,char c, int i0 , int j0 )/*在

9、g1 .m1 .n中，将元素gi0 j0 */*所在的同色区域的颜色置换为颜色c */ Stack S;int x,y,di=1 ;/di代表东北西南四个方向char color;StackInit(S,(m+1 )*(n+1 );x=i0 ;y=j0 ;if(xn) exit(OVERFLOW);color=gxy; /总体的思路是，从gi0 j0 开始/对每个符合所求的元素的依次找东北西南，/即先找当前元素的东边，没有找北边，若北有，向北走一步，/再找（走到的那个元素）的东边，依次类推/直到最后一个元素东北西南都被找过了，就回退/用Pop(S,di)为指导方向，找一些（因在某些元素北西南方

10、）而被遗漏了的元素/此时，因为原来遍历的元素已经被标记成c，即某些元素的（东北西）已不再是所找元素/因此，可以如愿走（某些元素的（北西南）方向do /如果是所找的那个符号需要进行的操作if(x0 gxy=c;y+;Push(S,di);else /如果不是所找的那个符号需要进行的操作 Pop(S,di); /第一步，先退一步回到原来位置switch(di) case 1 :y-;break;case 2 :x-; break;case 3 :y+; break;case 4 : x+;break;di+; /第二步，换一个方向走下一个位置 if(di=a/* if m0 or n0 then

11、return -1 . */ int G(int m, int n)/* if m0 or n0 then return -1 . */ if(m0 |n0 实现下列函数：int F(int n);/* if n0 then return -1 . */int F(int n)/* if ndata=x;p-next=rear-next;/先让p新开的节点指向头结点 rear-next=p;rear=p;return OK;Status DeCLQueue(CLQueue CLQueue p=front-next;if(front=rear) return ERROR;x=p-data;fro

12、nt-next=p-next;free(p); return OK;3 .2 9如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（比如，当循环队列容量较小而队列中每个元素占的空间较多时，那一种方法 较好？）。实现下列函数：Status EnCQueue(CTagQueue Status DeCQueue(CTagQueue 本题的循环队列CTagQueue的类型定义如下：typedef char QElem

13、Type;typedef struct QElemType elemMAXQSIZE;int tag;int front;int rear; CTagQueue;Status EnCQueue(CTagQueue else Q.elemQ.rear=x;Q.rear=(Q.rear+1 )%MAXQSIZE;return OK;Status DeCQueue(CTagQueue else x=Q.elemQ.front;Q.front=(Q.front+1 )%MAXQSIZE; /当指针前移时，原来的front位置就空了return OK; /不需其他操作3 .3 0假设将循环队列定义为：以

14、域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并 写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。实现下列函数：Status EnCQueue(CLenQueue Status DeCQueue(CLenQueue 本题的循环队列CLenQueue的类型定义如下：typedef char QElemType;typedef struct QElemType elemMAXQSIZE;int length;int rear; CLenQueue;Status EnCQueue(CLenQueue else Q.elem

15、(Q.rear+1 )%MAXQSIZE=x;Q.rear=(Q.rear+1 )%MAXQSIZE; /有可能加到MAXQSIZEQ.length+;return OK;Status DeCQueue(CLenQueue if(Q.length=0 ) return ERROR;else if(front=Q.rear-Q.length+1 )0 ) front=MAXQSIZE+front; x=Q.elemfront;front=(front+1 )%MAXQSIZE;/有可能加到MAXQSIZEQ.length-; /当指针前移时，原来的front位置就空了return OK; /不需

16、其他操作3 .3 1假设称正读和反读都相同的字符序列为回文，例如，abba和abcba是回文，abcde 和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是回文。实现下列函数：Status Palindrome(char *word);/*利用栈和队列判定字符序列word是否是回文*/可使用栈Stack和队列Queue及其下列操作：Status InitStack(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack S); Status InitQueue(Queue Status EnQueue(Queue Status DeQueue(Queue Status QueueEmpty(Queue Q); Status Palindrome(char *word)/*利用栈和队列判定字符序列word是否是回文*/ Stack S;Queue Q;char s,q;InitStack(S);InitQueue(Q);while(*word!=) Push(S,*word);EnQueue(Q,*word);word+; while(!StackEmpty(S) Pop(S,s);DeQueue(Q,q);if(s!=q) return FALSE;return TRUE;