c++_栈和队列解读.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。 虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，且中缀表达式有不唯一的问题。因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。 对计算机来说，计算前缀或后缀表达式的值非常简单。 表达式处理（中缀表达式） 表达式处理（后缀表达式） top 4 top 4 3 top 4 3 5 top 例 计算 4+3*5 后缀表达式：435*+ top 4 15 top 19 后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1 括号匹配检验 假设在表达式中 （［］（））或［（［ ］［ ］）］等为正确的格式， ［（ ］）或（［（ ））或 (( )])均为不正确的格式。 则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。即后出现的左括弧，它等待与其匹配的右括弧出现的急迫心情要比先出现的左括弧高。 括号匹配检验：算法设计思想 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余 函数调用 r 主程序 s r r r s 子过程1 r s t 子过程2 r s t 子过程3 4.2 队列 4.2.1 队列的定义 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。 队列定义 a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。 ADT Queue ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾 基本操作： } ADT Queue 队列基本操作 InitQueue DestroyQueue QueueEmpty QueueLength ClearQueue DeQueue EnQueue QueueTravers 入队/出队示意 front=-1 rear=-1 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J1,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1 空队列条件：front==rear 入队列：sq[++rear]=x; 出队列：x=sq[++front]; rear rear front rear 1 2 3 4 5 0 J1,J2,J3出队 J1 J2 J3 front front front 循环队列的提出 存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; 循环队列 实现：利用“模”运算 入队： rear=(rear+1)%M; sq[rear]=x; 出队： front=(front+1)%M; x=sq[front];