3.2.5 表达式求值表达式求值是编译系统中最基本的一个问题。1）问题的提出如高级语言中都有表达式，例赋值语句：变量=表达式；该语句的执行过程为：先求出表达式的值， 然后将其值赋给赋值号左边的变量。这个表达式的值是如何求出的？下面我们就来设计一个表达式求值算法。2） 表达式的构成 操作数+运算符+界限符（如括号）3） 表达式的求值：例 5+6 (1+2)- 4按照四则运算法则，上述表达式的计算过程为：5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19表达式中运算符的运算顺序为： + ， ， +， - ，如何确定运算符的运算顺序？123412344） 算符优先关系表表达式中任何相邻算符1、2的优先关系有：12：1的优先级高于2由四则运算法则，可得到如下的算符优先关系表：+ 2 1 - */()#+ - * / ( ) # : /新输入的算符c优先级低，即栈顶算符优先权高，Pop(OPTR, theta);Pop(OPND, b); Pop(OPND, a);Push(OPND, Operate(a, theta, b); /出栈并将运算结果入栈OPNDbreak; return GetTop(OPND); OPTROPND表达式求值示意图：5+6(1+2)-4 topbaseOPTR栈#OPND栈topbase5toptop+top6top top(top1top+top2toptoptoptop3toptoptoptoptop18toptop toptop23top -top4toptoptop top 19top toptop5读入表达式过程：+6(1+2)-4#=191+2=3 63=18 5+18=23 23-4=193.3 栈与递归由以上看到：应用中如果数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下面我们将看到可以用栈来实现递归。用(n-1)!定义n!1什么是递归递归是一个很有用的工具，在数学和程序设计等许多 领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念,称为递归定义。例 n!= 1*2*3*4*(n-1)*n n!递归定义 n!= 1 当 n=1时n!= n (n-1)! 当n 1时递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己B间接调用自己2递归算法的编写 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法问题的递归描述（定义）递归定义包括两项基本项（终止项）：描述递归终止时问题的求解；递归项：将问题分解为与原问题性质相同，但规模较小的问题；例 n!的递归定义基本项： n!=1 当 n=1递归项： n!=n (n-1)! 当 n 1例1 编写求解 阶乘n! 的递归算法首先给出阶乘n! 的递归定义n!的递归定义基本项： n!=1 当 n=1递归项： n!=n (n-1)! 当 n 1有了问题的递归定义，很容易写出对应的递归算法 ： int fact (int n) /算法功能是求解并返回n的阶乘If（n=1） return（1）；Else return（n*fact (n-1)）； /fact例2. 编写求解Hanoi塔问题的递归算法有三个各为X，Y，Z的塔座，在X上有n个大小不同，依小到大编号为1，2n的圆盘。 现要求将X上的n个圆盘移至Z上，并仍以同样顺序叠放， 圆盘移动时必须遵守下列原则：1）每次移动一个盘子；2）圆盘可以放在X，Y，Z中的任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；X Y Z321abc321 1121 3121YXZ首先给出求解Hanoi塔问题 的递归描述（定义）基本项： n=1时，将n号圆盘从X移至Z；递归项： n1时，将X上1n-1号圆盘移至Y；将X上的n号圆盘从X移至Z; 将Y上1n-1号圆盘从Y移至Z; 将规模为n的问题 的求解归结为规模 为n-1的问题的求 解有了问题的递归定义，很容易写出对应的递归算法：void hanoi (int n, char x, char y, char z) /将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到/塔座z上，y可用作辅助塔座。/搬动操作move(x, n, z)可定义为(c是初值为0的全局变量，对搬动计数)：/printf(“%d Move disk %di from %c to %cn”, +c, n, x, z);if (n= =1)move(x,1,z); /将编号为1的圆盘从x移动zelse hanoi(n-1, x, z, y); /将x上编号为1至n-1的圆盘移到y, z作辅助塔move(x, n, z); /将编号为 n的圆盘从x移到zhanoi(n-1, y, x, z)； /将y上编号为1至n-1的圆盘移到z，x作辅助塔算法3.5 Hanci塔问题 八皇后问题设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个算法，求解并输出此问题的所有合法布局。背包问题设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w1, w2, , wn。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试设计求解背包问题的算法3 递归函数的实现在递归函数的执行中， 需多次自己调用自己，递归函数是 如何执行的？先看一般函数的调用机制如何实现的。 A( )B( );C( )B( )C( );调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A后调用的函数先返回函数调用机制可通过栈来实现计算机正是利用栈来实现 函数的调用和返回的,函数 之间的信息传递和控制转 移通过“栈”来实现上面看到：栈结构后进先出的特征在程序设计中的应用，栈在实现函数递归调用中的作用；以及如何编写递归算法（递归函数）。在后面的章节中，还将利用递归函数实现树和图的基本操作，这里同学要好好理解如何编写递归算法（递归函数）。小 结 1 栈是限定仅能在表尾一端进行插入、删除操作的线性表；2 栈的元素具有后进先出的特点；3 栈顶元素的位置由一个称为栈顶指针的变量指 示， 进栈、出栈操作要修改栈顶指针； 第三章 习题一1、P21-24 3.1, 3.4, 3.173.17.试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1struct Qnode *next;QNode,*QueuePtr;typedef struct /链队列的类型定义QueuePtr front; / 队头指针，指向链表的头结点QueuePtr rear; / 队尾指针，指向队尾结点 LinkQueue;1）初始化操作 InitQueue(LinkQueue /为链队列的头结点分配空间if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;三 链队列基本操作算法链队列的 头结点Q.rearQ.front 空链队列2) 销毁操作DestroyQueue_L(LinkQueue / 链队列不存在while(Q.front) Q.rear=Q.front-next; free(Q.front);Q.front=Q.rearreturn OK; Q.fronta1 an 销毁前Q.rearQ.front=NULLQ.rear=NULL销毁后3）入队操作EnQueue(LinkQueue /为新元素e分配结点空间 if(!p) exit(OVERFLOW); /存储分配失败p-data=e; p-next=NULL;Q.rear-next=p; /插入新队尾结点Q.rear=p; /修改队尾指针，return OK;Q.frontJ1Q.rearJ1在链队列Q队尾，插入新的元素eeStatus DeQueue(LinkQueue /若队列空，返回ERRORp=Q.front-next; / p指向队头元素结点e=p-data;Q.front-next=p-next; / 修改链队列头结点指针，/ 删除队头元素结点if(Q.rear=p) Q.rear=Q.front; / 对于链队列只有一个元素结点的情况/ 要同时修改队尾指针free(p);return OK;元素J1出队列图示J1Q.frontQ.rearJ2 3.4.2 循环队列队列的顺序表示和实现队列的顺序存储结构称为顺序队列，和顺序栈一样，顺序队列也是用一组地址连续的存储单元依次存放从队列头到队列尾的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针front和rear分别指示队头和队尾元素在队列中的位置。Q.rearQ.frontJ1J2J3队列的顺序存贮结构图示由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。每当插入新的队列尾元素时，“尾指针加1”;初始化建空队列时，令front=rear=0。每当删除队列头元素时，“头指针加1”。j1Q.rear Q.frontj2Q.rearQ.rearj3Q.rearj4Q.rearQ.front43210j5Q.rear从图示中可看出，当J5 入队后, 队尾 指针Q.rear越界，不可能再插入新的队尾元素，但是另一方面，队列的实际可用空 间并未占满。一个巧妙的办法是，将顺序队列设想 为首尾相连的环状空间，如图，当Q.rear值超出队列空间的最大位置时，令 Q.rear= 0