数据结构C语言描述(耿国华)第3章讲解.ppt

斐波那契数列的递归算法Fib(n)如下， Fib(int n) { if（n= =0||n= =1） return n; /* 递归出口 */ else return Fib(n-1)+Fib(n-2); /* 递归调用 */ } 图3.11 Fib(5)递归调用过程示意 3-12 Fib(5)循环调用过程示意图 图3.5 表达式运算及运算符优先级 图3.6 无括号算术表达式的处理过程 2） 算术表达式处理规则 (1) 规定优先级表。 (2) 设置两个栈： OVS(运算数栈)和OPTR(运算符栈)。 (3) 自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符OPTR栈顶, 当前操作符进OPTR栈当前操作符≤OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。 例： 实现A/B↑C+D*E＃的运算过程时栈区变化情况如图3.7所示。 图3.7 A/B↑C+D*E运算过程的栈区变化情况示意图 3） 带括号算术表达式 假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符， 界限符有左右括号和表达式起始、结束符“＃”，如： ＃（7+15）*（23-28/4）＃。 引入表达式起始、 结束符是为了方便。 要对一个简单的算术表达式求值， 首先要了解算术四则运算的规则， 即：  (1) 从左算到右；  (2) 先乘除， 后加减；  (3) 先括号内， 后括号外。 运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一： θ1θ2， θ1的优先权低于θ2。  θ1=θ2， θ1的优先权等于θ2。  θ1θ2， θ1的优先权高于θ2。 表 3-1 算符之间的优先关系 实现算符优先算法时需要使用两个工作栈： 一个称作operator， 用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。 算法的基本过程如下： 首先初始化操作数栈operand和运算符栈operator， 并将表达式起始符“＃”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand， 若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：  (1) 若栈顶运算符的优先级低于刚读入的运算符， 则让刚读入的运算符进operator栈；  (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、 b进行θ运算后， 将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。 算法具体描述如下： int ExpEvaluation() /*读入一个简单算术表达式并计算其值。 operator和operand分别为运算符栈和运算数栈， OPS为运算符集合*/ { InitStack(operand); InitStack(operator); Push(operator,′＃′); printf(″\n\nPlease input an expression(Ending with ＃) :″); ch=getchar(); while(ch!=′＃′||GetTop(operator)! =′＃′) /* GetTop()通过函数值返回栈顶元素*/ { if(!In(ch,OPS)) {a=GetNumber(ch); /* 用ch逐个读入操作数的各位数码， 并转化为十进制数a */ Push(operand,a);}  else switch(Compare(GetTop(operator),ch)) { case ′′: Push(operator,ch);  ch=getchar(); break; case ′=′: Pop(operator,x);