数据结构课件习题3

题3.17,题3.19,题3.22,题3.28,题3.31,题3.32,题3.19,int matching(SqList exp) / 顺序表exp中存有数据元素为字符的表达式, / 若表达式中三种括弧正确嵌套，则返回 1, / 否则返回 0。 ,state = 1; i = 1; InitStack(S); while (i=exp.length ,switch of exp.elemi case 左括弧: Push(S, exp.elemi); i+; break; case ): if (NOT StackEmpty(S) case : ,识别读入的一个字符序列是否为反对称的字符序列。,例如:abcd abc& 或 abc&abc 或 ab&bac都不是反对称字符序列。,题3.17,则这个算法和“判别括弧是否正确匹配”的算法极其相似。,同样，在算法过程中需要用到一个栈，由于序列中必定出现字符 & ， 则可将在字符&出现之前的所有字符均入栈，滤去字符&之后再读入的字符则应和栈顶的字符相等，当然，首先必须判别此时的“栈”是否为“空栈”。,此题的参数仅为一个字符序列，可以设为元素为字符的数组。,int symmetry() / 若 Ch 为反对称字符序列，则返回 1, / 否则返回 0。 ,scanf(ch); InitStack(S); while (ch!= ,return(StackEmpty(S) & state ),题3.22,int valuation(SqList suffixal) IniStack(S); p=suffixal.elem; ch=*p; while ( ch != # ) if (!IN(ch,OP) Push(S,ch); else Pop(S,b); Pop(S,a); x=value(a,ch,b); e=setvar(x); / e 为其值=x的变量名 Push(S,e); ch=*p+; Pop(S,e); return(val(e); / 返回变量e的值 ,题3.28,typedef QueuePtr CLQueue; / 指向队尾结点的指针,Status InitQueue(CLQueue ,定义循环链队列,初始化操作,Status EnQueue(CLQueue ,入队列操作,Status DeQueue(CLQueue / 释放被删结点 ,出队列操作,判别读入的字符序列是否为“回文”。,例如: abcdedcba 或 abccba 是回文。,由于回文的字符序列中的分界线不明确，因此无法判定字符序列的“中间位置”，即只能按照回文的定义从字符的两头出发进行判别。,题3.31,算法的基本思想是:,将依次读入的字符分别插入栈和队列，然后依次比较“栈顶”和“队头”的字符。,然而，按照题目的要求，这个字符序列是从外部环境输入的。为了在输入结束的时候，同时能得到序列的“头”和“尾”，因此算法中，除了需要用一个栈之外，还需要一个队列。,Status ex331( ) / 若从终端依次输入的字符序列是“回文”，/ 则返回TRUE,否则返回FALSE InitStack(S); InitQueue(Q); scanf(ch); while(ch!=) Push(S, ch); EnQueue(Q, ch); scanf(ch); ,state=1; while(!StackEmpty ,题3.32,k 阶斐波那契函数的定义: f0 = f1 = = fk-2 = 0， fk-1 = 1， fn = fn-1+fn-2+ + fn-k n k,由于题目要求循环队列的容量为 k, 即当前队列中 k 个元素之和为下一个函数值。,利用公式 fn = 2fn-1 - fn-k-1 可以简化计算，但需要队列的容量为 k+1。,void k_Fib(CQueue Q, int k, int max) for (i=0; ik-1; i+) Q.elemi = 0; /赋初值 Q.elemk-1 = 1; Q.rear = 0; f = 1; while ( f = max ) cout Q.elemQ.rear; / 输出队头元素 Q.elemQ.rear = f; / 插入新的队尾元素 Q.rear +; / 队尾指针增1 f = 0; / 计算下一个函数值 for ( i=0; ik; i+) f+= Q.elemi; 继续输出循环队列中的其余函数值; ,void k_Fib( int k, int max) InitQueue(Q); / 附设含k+1个分量的循环队列 for (i=0; ik-1; i+) EnQueue(Q, 0); EnQueue(Q, 1); f = 1; /赋初值 while ( f = max ) DeQueue(Q, e); cout e ,; / 输出队头元素 EnQueue(Q, f ); / 插