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

第1页,每课一贴：原来很简单 有一个人去应征工作，随手将走廊上的纸屑捡起来，放进了垃圾桶，被路过的口试官看到了，因此他得到了这份工作。原来获得赏识很简单，养成好习惯就可以了。住在田边的青蛙对住在路边的青蛙说：你这里太危险，搬来跟我住吧！路边的青蛙说：我已经习惯了，懒得搬了。几天后，田边的青蛙去探望路边的青蛙，却发现他已被车子压死，暴尸在马路。原来掌握命运的方法很简单，远离懒惰就可以了。,第2页,2.逻辑结构 与同线性表相同，仍为一对一关系。,3.运算规则 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。4.出栈顺序：,定义 限定只能在表的一端进行插入和删除运算的 线性表（只能在栈顶操作）,上次课内容回顾,第3页,讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足入栈顺序i，j，k 和 出栈顺序k，i，j。,例4 一个栈的输入序列为12345，若在入栈的过程中允许出栈，则可能得到的出栈序列有多少种，分别是什么？,第4页,例1：回文游戏 设计思路：用栈暂存回文例2：数制转换（十转N）设计思路：用栈暂存低位值例3：括号匹配的检验 设计思路：用栈暂存左括号例4：表达式求值 设计思路：用栈暂存运算符,简化程序设计问题,第5页,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.压入栈3.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，则是回文有没有更简洁的办法呢？(读入字符串，压入n/2个字符,n为字符个数),多进制输出：,字符串：“madam I madam”“上海自来水来自海上”,第6页,多进制输出：,public class Test public static void main(String args)int i=159;String binStr=Integer.toBinaryString(i);String otcStr=Integer.toOctalString(i);String hexStr=Integer.toHexString(i);System.out.println(binStr);,第7页,多进制输出：,import java.util.*;class T public static void main(String args)System.out.println(toOctal(159);public static String toOctal(int a)String str=;Stack s=new Stack();while(a!=0)s.push(a%8);a=a/8;while(!s.empty()str+=s.pop();return str;,例 把十进制数159转换成八进制数,第8页,例如：3*（7 2）(1)要正确求值，首先了解算术四则运算的规则：a.从左算到右 b.先乘除，后加减 c.先括号内，后括号外 由此，通常此表达式的计算顺序为：3*（7 2）=3*5=15,表达式求值(这是栈应用的典型例子)这里，表达式求值的算法是“算符优先法”。,第9页,表达式表示法 算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。,中缀表示法 Syntax:operand1 operator operand2Example:(A+B)*C-D/(E+F)前缀表示法-波兰表示法（Polish notation，PN）Syntax:operator operand1 operand2Example:-*+ABC/D+EF后缀表示法-逆波兰表示法（Reverse Polish Notation，RPN）Syntax:operand1 operand2 operatorExample:AB+C*DEF+/-无操作符优先级问题，求值简单,第10页,1.中缀表达式到后缀表达式的转换 要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。Left associativity:A+B+C=(A+B)+CRight associativity:ABC=A(BC),常用表达式求值方法1.中缀表达式转换成后缀表达式2.计算后缀表达式,第11页,转换算法：,1.读入运算对象（数据），直接输出2.遇到(运算符进栈3.遇到)运算符，则栈内的最上一个(以上的所有运算符退栈，(也退栈4.读入运算符，进入运算栈 4.1 后进栈的运算符 先进栈的运算符，运算符进栈(优先级比较)4.2 后进栈的运算符=先进栈的运算符，将栈内的运算符退栈输出，再进栈,第12页,31*(5-22)+70,第13页,后缀表达式求值 对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。可以用如下算法对后缀表达式求值：初始化一个空堆栈 从左到右读入后缀表达式 如果字符是一个操作数，把它压入堆栈。如果字符是个操作符，弹出两个操作数，执行操作，然后把结果压入堆栈。到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。,第14页,31*(5-22)+70,参看Class1.java代码,第15页,1.顺序栈的一般定义,/堆栈接口public interface Stack public int getSize();public boolean isEmpty();public void push(Object e);public Object pop()throws StackEmptyException;public Object peek()throws StackEmptyException;,二.基本操作的程序实现,第16页,1.顺序栈的一般定义,public class StackArray implements Stack private final int LEN=8;/private Object elements;/private int top;public StackArray()top=-1;elements=new ObjectLEN;public int getSize()return top+1;public boolean isEmpty()return top=elements.length)expandSpace();elements+top=e;,二.基本操作的程序实现,第17页,private void expandSpace()Object a=new Objectelements.length*2;for(int i=0;ielements.length;i+)ai=elementsi;elements=a;public Object pop()throws StackEmptyException if(getSize()1)throw new StackEmptyException(“错误，堆栈空”);Object obj=elementstop;elementstop-=null;return obj;public Object peek()throws StackEmptyException if(getSize()1)throw new StackEmptyException(“错误，堆栈空”);return elementstop;,第18页,入栈算法,出栈算法,链栈基本操作P67 Stack的链式存储实现,初始化、判断栈空、栈满、入栈、出栈、取栈顶元素、销毁。,SLNode p=new SLNode(x,top);top=p;size+;,栈非空，则Object obj=top.getData();top=top.getNext();size-;,第19页,补充1：若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；,第20页,第三章 栈和队列,3.2 队（Queue）,队的基本理论 定义、逻辑结构、存储结构、基本运算规则、队的应用2.基本操作的程序实现方法,第21页,3.2 队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),第22页,ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1,ai D,i=2,n 基本操作：getSize();/返回队列大小，即元素个数 isEmpty();/对为空返回true,否则返回false enqueue(e);/数据元素e入对 dequeue();/对头元素出对 peek();/获取对头元素，但不出对/ADT Queue,队的抽象数据类型定义,第23页,队列的顺序存储结构实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,队列会满吗？,这样操作有没有问题？,第24页,存在问题设数组容量为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出,解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,实现：利用“求模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件？,第25页,队空：front=rear队满：front=rear,真溢出,假溢出,第26页,解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear人为浪费一个单元，令队满特征为front=(rear+1)%N；使用一个计数器记录队列中元素个数（即队列长度）；,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,rear,第27页,例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,front,解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4,入队：rear=(rear+1)%M;出队：front=(front+1)%M;,第28页,例2：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（）rf（）（nfr）%n（）nrf（）（nrf）%n,4种公式哪种合理？当 r f 时（A）合理；当 r f 时（C）合理；,分析：,综合2种情况，以（D）的表达最为合理,例3：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先，后。,移动队首指针,取出元素,第29页,基本运算如下：置空队 分配空间，头尾指针赋值，计数赋0 入队 顺序表插入，调整头尾指针 计数赋 出队 顺序表删除，调整头尾指针 计数赋 判队空 队列中数据数目为0。,使用计数器的循环队列的类型定义：,Java实现使用计数器的循环队列.txt,第30页,结点接口Public interface Nodepublic Object getData();/获取结点数据域Public void setData(Object object);/设置结点数据域,Public class SLNode implements Node private Object element;private SLNode next;public SLNode this(null,null);public SLNode(Object ele,SLnode next)this.element=ele;this.next=next;public SLNode getNext()return next;public void setNext(SLNode next)this.next=next;public Object getData()return element;public void setData(Object obj)element=obj;,链队列结点定义同SLNode的定义,第31页,链队列,设队首、队尾指针front和rear,front指向头结点，rear指向队尾,第32页,第33页,讨论：空队列的特征？,怎样实现入队和出队操作？入队（尾部插入）：出队（头部删除）：P74入队、出队Java实现,队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,第34页,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）;实时监控系统（循环队列）操作系统中多道作业的处理（一个CPU执行多个作业）；4.简化程序设计。舞伴问题，迷宫的最短路径问题,答：只要是存储和使用顺序相同，两端受限操作就应该想到用队列这种数据结构。,