数据结构电子课件教案-第3章 栈和列队.ppt

1,第三章栈和队列,2,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS,栈栈的应用栈与递归队列队列的应用,3,3.1栈（stack）,3.1.1栈的定义和特点3.1.2栈的表示和实现3.1.3栈的应用,4,3.1.1栈的定义和特点,定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）,push(e)pop()clear()gettop()isempty(),栈的基本操作,5,3.1.2栈的表示和实现,顺序栈：用一维数组实现,栈顶指针top,指向实际栈顶后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,6,3.1.2栈的表示和实现,链栈：用链表实现栈功能,结点定义,入栈算法,出栈算法,typedefstructnodeintdata;structnode*next;JD;,7,在一个空间中定义两个栈,3.1.2栈的表示和实现,8,3.2栈的应用,数制转换回文游戏括号匹配检验表达式求值,9,数制转换,例把十进制数1348转换成八进制数（原理：N=(Ndivd)d+Nmodd）,4,0,5,3.2栈的应用,NNdiv8Nmod8134816841682102125202,2,(1348)10=(2504)8,10,3.2栈的应用,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文,字符串：“madamimadam”,11,3.2栈的应用,括号匹配的检验假设在表达式中（）或（）为等为正确的格式而（）或（）或（）)均为不正确的格式则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,例如：考虑下列括号序列：()12345678分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；直到结束，也没有到来所“期待”的括弧。,12,3.2栈的应用,算法设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,13,3.2栈的应用,表达式求值（限于二元运算符的表达式定义）表达式:=(操作数)+(运算符)+(操作数)操作数:=简单变量|表达式简单变量:=标识符|无符号整数表达式的三种标识方法：,设Exp=S1+OP+S2,则称OP+S1+S2为前缀表示法,S1+OP+S2为中缀表示法,S1+S2+OP为后缀表示法,14,3.2栈的应用,例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+,三种表达式小结操作数之间的相对次序不变运算符的相对次序不同;中缀式丢失了括弧信息，致使运算的次序不确定;,15,3.2栈的应用,前缀式的运算规则为:Exp=ab+(cd/e)f前缀式:+abc/def连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,后缀式的运算规则为:Exp=ab+(cd/e)f后缀式:abcde/f+运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前且紧靠它的两个操作数构成一个最小表达式。,16,3.2栈的应用,如何从后缀式求值？,例：abcde/f+,ab,d/e,c-d/e,(c-d/e)f,运算规则连续出现的两个操作数和在它们之后且紧靠它们的运算符构成一个最小表达式;,先找运算符再找操作数,17,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f,3.2栈的应用,如何从原表达式求得后缀式？,18,操作符优先级关系表,19,3.2栈的应用,从原表达式求得后缀式的步骤设立运算符栈；设表达式的结束符为“#”，予设运算符栈的栈底为“#”；若当前字符是操作数，则直接发送给后缀式。若当前运算符的优先数高于栈顶运算符，则进栈；否则，退出栈顶运算符发送给后缀式；“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,20,3.3栈与递归,21,3.4队列,3.4.1队列的定义及特点3.4.2队列的链式存储链队列3.4.3队列的顺序存储循环队列3.4.4队列的应用,22,3.4.1队列的定义及特点,定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),双端队列,23,3.4.2队列的链存储链队列,结点定义,设队首、队尾指针front和rear,front指向头结点，rear指向队尾,typedefstructQNode/结点类型QElemTypedata;structQNode*next;QNode,*QueuePtr;,typedefstruct/链队列类型QueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;,24,3.4.2队列的链存储链队列,25,3.4.2队列的链存储链队列,入队算法,voidEnQueue(LinkQueue,26,3.4.2队列的链存储链队列,出队算法,BOOLDeQueue(LinkQueuereturntrue,27,3.4.3队列的顺序存储结构,简单顺序队列：用一维数组实现sqM,front=0rear=0,队空,front,J1,J1,J3入队,J1,J2,J3,rear,J4,J5,J6入队,J4,J5,J6,front,设两个指针front,rear,约定：rear指示队尾元素下一位置；front指示队头元素初值front=rear=0,空队标志：front=rear入队列：sqrear+=x;出队列：x=sqfront+;,J1,J2,J3出队,J1,J2,J3,满队标志：rear=M,28,存在问题设数组维数为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队时，剩余元素向队头移动浪费时间循环队列,29,循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0,实现：利用“模”运算入队：sqrear=x;rear=(rear+1)%M;出队：x=sqfront;front=(front+1)%M;队满、队空判定条件,0,M-1,1,front,rear,.,.,30,rear,front,初始状态,队空：front=rear队满：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear队满：(rear+1)%M=front,队空,队满,31,#defineMAXQSIZE100/最大队