严蔚敏版数据结构第三章.pptVIP

* （3）算法思想： 设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符 栈顶元素，则退栈、计算，结果压入OPND栈； 操作符 = 栈顶元素且不为‘#’，脱括号（弹出左括号）； 操作符 栈顶元素，压入OPTR栈。 栈的应用（表达式求值） * 栈的应用（表达式求值） OPTR OPND INPUT OPERATE 3*(7-2)# Push(opnd,’3’) # *(7-2)# 3 # Push(optr,’*’) #,* 3 (7-2)# Push(optr,’(’) #,*,( 3 7-2)# Push(opnd,’7’) #,*,( 3,7 -2)# Push(optr,’-’) #,*,(,－ 3,7 2)# Push(opnd,’2’) #,*,(,－ 3,7,2 )# Operate(7-2) #,*,( 3,5 )# Pop(optr) #,* 3,5 # Operate(3*5) # 15 # GetTop(opnd) * Status EvaluateExpression( OperandType result) { InitStack(OPND); InitStack(OPTR);Push(OPTR ,’#’);c=getchar(); while((c!=‘#’)//(GetTop(OPTR)!=‘#’)) { if (!In(c,OP) { Push(OPND,c); c=getchar();} else switch(compare(c,GetTop(OPTR))) {case ‘’ : Push(OPTR , c); c=getchar();break; case ‘=’: Pop(OPTR);c=getchar();break; case ‘’ : temat=Pop(OPTR); b=Pop();a=Pop(); result= Operate(a,temat,b);Push(OPND,result); c=getchar();break; } //switch }//while result=GetTop(OPND);}//EvaluateExpression 此函数在哪里？ * 定 义 3.2 队列 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队列，判队空或队满等操作。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （头删尾插） * 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。 表尾即 an 端，称为 队尾 ； 表头即 a1 端，称为队头。 它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 插入元素称为入队；删除元素称为出队。 队头 队尾 教材P59对队列有更详细定义： 队列的抽象数据类型定义见教材Ｐ59－60 队列的存储结构为链队或顺序队 （常用循环顺序队） * 链队列示意图 讨论： 空队列的特征？ Q (队尾) (队首) front a1 a2 a3 ^ rear p front ^ rear ③ 怎样实现入队和出队操作？ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next; ② 队列会满吗？ front=rear 一般不会，因为删除时有free动作。除非内存不足！ * front rear x ^ 元素x入队 front rear x y ^ 元素y入队 front rear x ^ ^ y 元素x出队 front rear ^ 空队列 ^ * 链式队列的定义 typedef