数据结构第六次课-栈和队列B

《数据结构第六次课-栈和队列B》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、每课一贴：原来很简单有一个人去应征工作，随手将走廊上的纸屑捡起来，放进了垃圾桶，被路过的口试官看到了，因此他得到了这份工作。原来获得赏识很简单，养成好习惯就可以了。住在田边的青蛙对住在路边的青蛙说：「你这里太危险，搬来跟我住吧！路边的青蛙说：「我已经习惯了，懒得搬了。」几天后，田边的青蛙去探望路边的青蛙，却发现他已被车子压死，暴尸在马路。原来掌握命运的方法很简单，远离懒惰就可以了。12.逻辑结构与同线性表相同，仍为一对一关系。3.运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。4.出栈顺序

2、：定义限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）上次课内容回顾2讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足入栈顺序i，j，k和出栈顺序k，i，j。例4一个栈的输入序列为12345，若在入栈的过程中允许出栈，则可能得到的出栈序列有多少种，分别是什么？3例1：回文游戏设计思路：用栈暂存回文例2：数制转换（十转N）设计思路：用栈暂存低位值例3：括号匹配的检验设计思路：用栈暂存左括号例4：表达式求值设计思路：用栈暂存运算符简化程序设计问题4回文游戏：顺读与逆读字符串一样

3、（不含空格）dadtop1.读入字符串2.压入栈3.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，则是回文有没有更简洁的办法呢？(读入字符串，压入n/2个字符,n为字符个数)多进制输出：字符串：“madamImadam”“上海自来水来自海上”例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top7325多进制输出：例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732

4、publicclassTest{publicstaticvoidmain(Stringargs[]){inti=159;StringbinStr=Integer.toBinaryString(i);StringotcStr=Integer.toOctalString(i);StringhexStr=Integer.toHexString(i);System.out.println(binStr);}}6多进制输出：importjava.util.*;classT{publicstaticvoidmain(String[]args)

5、{System.out.println(toOctal(159));}publicstaticStringtoOctal(inta){Stringstr="";Stacks=newStack();while(a!=0){s.push(a%8);a=a/8;}while(!s.empty()){str+=s.pop();}returnstr;}}例把十进制数159转换成八进制数7例如：3*（7–2）(1)要正确求值，首先了解算术四则运算的规则：a.从左算到右b.先乘除，后加减c.先括号内，后括号外由此，通常此表达式的计算顺序为：3*

6、（7–2）=3*5=15表达式求值(这是栈应用的典型例子)这里，表达式求值的算法是“算符优先法”。8表达式表示法算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。中缀表示法Syntax:operand1operatoroperand2Example:(A+B)*C-D/(E+F)前缀表示法-波兰表示法（Polishnotation，PN）Syntax:operatoroperand1operand2Example:-*+ABC/D+EF后缀表示法-逆

7、波兰表示法（ReversePolishNotation，RPN）Syntax:operand1operand2operatorExample:AB+C*DEF+/-无操作符优先级问题，求值简单91.中缀表达式到后缀表达式的转换要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。Le

8、ftassociativity:A+B+C=(A+B)+CRightassociativity:A^B^C=A^(B^C)常用表达式求值方法1.中缀表达式转换成后缀表达式2.计算后缀表达式10转换算法：1.读入运算对象（数据），直接输出2.遇到‘(