数据结构课件chp3.ppt

数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 控制符：-退格 结束符：# 输入例子：ABCDF-EH# 栈的应用：表达式求值 (1)表达式的表示方法 在计算机中，表达式可以有三种不同的表示方法。 设exp（表达式）=S1（第一操作数） OP（运算符） S2（第二操作数），则称 OP S1 S2为表达式的前缀表示法(P121 (3)) S1 OP S2为表达式的中缀表示法； S1 S2 OP为表达式的后缀表示法。 例 已知中缀表达式=5+（4-3）*2 则前缀表达式（波兰式）为： +5*-432 后缀表达式（逆波兰式）为：543-2*+ 说明： （1）中缀式的运算规则：先乘除，后加减；从左算到右；先括号内，后括号外。 （2）前缀式的运算规则：从右至左按运算符出现的顺序作运算，且取紧靠运算符之后的两个相邻的数作运算。 （3）后缀式的运算规则：从左至右按运算符出现的顺序作运算，且取紧靠运算符之前的两个相邻的数作运算。 结论： （1）在三种表示法中，操作数的相对次序不变。 （2）中缀式中须有括号，而前、后缀式不需括号。 （3）后缀式运算符出现的顺序与表达式的运算顺序相同。 后缀表达式求值 任何表达式都可分解为下列形式： (子表达式E1)(运算符OP)(子表达式E2) 它的后缀表示法应写成： (E1的后缀表示)(E2的后缀表示)OP 只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。 例如： 2*(6+3) ? 2(6+3)* ? 263+*。 (注意：转化为后缀式后括号去掉) 中缀式虽然容易理解，但在求值的时候利用前缀式或后缀式更为简单。用后缀式求值的算法为： 首先设立一个堆栈，依此读取后缀式中的字符，若字符是数字，则进栈并继续读取，若字符是运算符（记为OP），则连续出栈两次得到数字S1和S2，计算表达式S1OPS2并将结果入栈，继续读取后缀式。当读到结束符时停止读操作，这时堆栈中只应该有一个数据，即结果数据。 例如后缀式263+*的计算过程为2、6、3依次入栈，读+号则令3和6依次出栈，计算6+3后将结果9入栈，读*号则令9和2依次出栈，计算2*9后将结果18入栈。这时18就是最终结果。 【图3.16】P118 输入3，2，4，并进栈 3 2 4 输入运算符+，弹出两个数据运算2+4 运算结果6压入栈中 6 输入运算符*，弹出两个数据运算3*6 运算结果18压入栈中 18 输入6，并压入栈中 6 输入运算符-，弹出两个数据运算18-6 结果12压入栈中 12 栈的运行过程 栈顶 栈底 利用栈计算后缀表达式过程： 后缀表达式324+*6- 中缀表达式变成等价的后缀表达式 将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是： 1）给中缀表达式中每步计算加上括号 2）移动所有操作符，替换它们对应的右括号 3）删除剩余的所有括号 P119 例 ((((A/B)-C)+(D*E))-(A*C)) 设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。 程序思路 完成中缀表达式A+(B-C/D)*E转换成后缀表达式的过程如下： 步骤 栈中元