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

广东工业大学数据结构 Aniview 第三章参考答案 3.17试写一个算法，识别依次读入的一个以 为结束符的字符序列是否为形如序列 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(char *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.18 试写一个判别表达式中开、闭括号是否配对出现的算法。 实现下列函数： Status MatchCheck(SqList exp); /* 顺序表 exp 表示表达式；*/ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ /* 注：本函数不使用栈*/ 顺序表类型定义如下： typedef struct ElemType *elem; intlength; intlistsize; SqList;/ 顺序表 Status MatchCheck(SqList exp) /* 顺序表 exp 表示表达式；*/ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ /* 注：本函数不使用栈*/ /exp 里面是纯括号，纯小括号 int l=0,i; for(i=0;i0) return FALSE;/有左，没右 else return TRUE; 3.19 假设一个算术表达式中可以包含三种括号：圆括号“(“ 和 “)“，方括号“和“和花括号“和“，且这三种括号可按任意的 次序嵌套使用（如：()） 。编写判别给定表达 式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素 为字符的顺序表中)。 实现下列函数： Status MatchCheck(SqList exp); /* 顺序表 exp 表示表达式；*/ /* 若 exp 中的括号配对，则返回 TRUE，否则返回 FALSE */ 顺序表类型定义如下： typedef struct ElemType *elem; intlength; intlistsize; SqList;/ 顺序表 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); for(i=0;im|yn) exit(OVERFLOW); color=gxy; /总体的思路是，从 gi0j0开始 /对每个符合所求的元素的依次找东北西南， /即先找当前元素的东边，没有找北边，若北有，向北走一步， /再找（走到的那个元素）的东边，依次类推 /直到最后一个元素东北西南都被找过了，就回退 /用 Pop(S,di)为指导方向，找一些（因在某些元素北西南方）而被遗漏了的元素 /此时，因为原来遍历的元素已经被标记成 c，即某些元素的（东北西）已不再是所找元 素 /因此，可以如愿走（某些元素的（北西南）方向 do /如果是所找的那个符号需要进行的操作 if(x0 /* if m0 实现下列函数： int F(int n); /* if nnext=rear; if(!front|!rear) exit(OVERFLOW); return OK;/需要 return OK Status EnCLQueue(CLQueue p=(CLQueue)malloc(sizeof(LNode); p-data=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; front-next=p-next; free(p); return OK; 3.29 如果希望循环队列中的元素都能得到利用， 则需设置一个标志域 tag，并以 tag 的值为 0 或 1 来区 分，尾指针和头指针值相同时的队列状态是“空“还 是“满“。试编写与此结构相应的入队列和出队列的 算法，并从时间和空间角度讨论设标志和不设标志 这两种方法的使用范围（比如，当循环队列容量较 小而队列中每个元素占的空间较多时，那一种方法 较好？） 。 实现下列函数： Status EnCQueue(CTagQueue Status DeCQueue(CTagQueue 本题的循环队列 CTagQueue 的类型定义如下： typedef char QElemType; 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.30假设将循环队列定义为：以域变量 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(Q.rear+1)%MAXQSIZE=x; Q.rear=(Q.rear+1)%MAXQSIZE; /有可能加到 MAXQSIZE Q.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;/有可能加到 MAXQSIZE Q.length-; /当指针前移时，原来的 front 位置就空了 return OK;/不需其他操作 3.31假设称正读和反读都相同的字符序列为 “回文“，例如，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) /* 利用栈和队列判定字符序列 wor