32栈的应用举例 325表达式求值 算符优先法: 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 操作数( operand):进OPND栈 操作符( operator):进OPTR栈 界限符( delimiter):
3.2 栈的应用举例 3.2.5 表达式求值 算符优先法: 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 进OPND栈 操作符(operator):进OPTR栈 界限符(delimiter):
算符间的优先关系: 0 -2/()# <<< Precede:判定运算符栈的栈顶运算符01与读入的运算符02之间 的优先关系的函数 Operate:进行二元运算a0b的函数
算符间的优先关系: θ1 θ2 + - * / ( ) # + > > > - > > > * > > > > > / > > > > > ( > > > > > # < < < < < = Precede: 判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间 的优先关系的函数. Operate: 进行二元运算aθb的函数
算术表达式求值过程算法3.4) OperandType Evaluate Expression( fInitStack(OPTR), Push(OPTR, # InitStack(OPND); c= getchar While(c!=#' Get Top(OPTR)!=#) If(!n(c,OP){Push(OPND,c);c= getchar;}∥不是运算符则进栈 else switch(Precede( Get Top(OPTR), c)i case 栈顶元素优先权低 Push(oPTR,c),c=getchar break case‘与:∥脱括号并接受下一个字符 Pop(OPTR, X); c=getchar break case>?:∥/退栈并将运算结果入栈 Pop(OPTR, theta): Pop(oPnD,b): Pop(OPND, a) Push(OPND, Operate(a, theta, b)) break default: printf(" Expression error! ) return(ERROR) 1//switch 3// while return GetTop(OPND) }∥ Evaluate Expression
算术表达式求值过程(算法3.4) OperandType EvaluateExpression() {InitStack(OPTR); Push(OPTR, ‘#’); InitStack(OPND); c = getchar(); While(c!=’#’|| GetTop(OPTR)!=’#’){ If(!In(c,OP)){ Push(OPND,c); c = getchar();} // 不是运算符则进栈 else switch(Precede(GetTop(OPTR),c)){ case ‘’: // 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; default: printf(“Expression error!”); return(ERROR); } // switch } // while return GetTop(OPND); } // EvaluateExpression
对算术表达式3*(7-2)求值 步骤OPTR栈OPND栈|输入字符 主要操作 3*(7-2)#Push(OPND,3”) *(7-2)# Push(OPTR, * 123456789 ##### (7-2)# Push(OPTR,,() ***** 333 7-2)# Push(OPND, 7) 37 2 )# Push(OPTR,"-) 37 2)# Push(OPND, 2) 372 )# Operate(7”,…,2”) ) POP(OPTR) Operate(3,,7*7,75) 10 # 15 Return( Get Top(OPND)
对算术表达式 3*(7-2) 求 值 . 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,’3’) 2 # 3 * ( 7 - 2 ) # Push(OPTR,’*’) 3 # * 3 ( 7 - 2 ) # Push(OPTR,’(’) 4 # * ( 3 7 - 2 ) # Push(OPND,’7’) 5 # * ( 3 7 - 2 ) # Push(OPTR,’-’) 6 # * ( - 3 7 2 ) # Push(OPND,’2’) 7 # * ( - 3 7 2 ) # Operate(‘7’,’-‘,’2’) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(‘3’,’*’,’5’) 10 # 15 # Return(GetTop(OPND))
血an0塔间题 例:汉诺塔问题: 将a柱子上的盘移到c柱,用b柱放临时盘 要求:一次只能移动一个盘,大盘不可放于小盘上。 b
例：汉诺塔问题： 将a柱子上的盘移到 c柱，用 b柱放临时盘 要求：一次只能移动一个盘，大盘不可放于小盘上。 a b c hanoi塔问题
血an0塔的递归算法 定义函数: movetower(n,a,c,b)n个盘a->c,b放临时盘 分三步: movetower(n-1,a,b,c)将n-1个盘从a->b,c放临时盘 movedisk(a, n, c) 将第n个盘从a->c movetower(n-1,b,c,a)将n-1个盘从b->c,a放临时盘 void hanoi (int n, char a, char b, char c) fif(n==1)move(a, 1, c) else hanoi(n-1, a, c, b) move(a, n,c) hanoi(n-1,b, a, c)
定义函数：movetower(n,a,c,b) n个盘a－>c，b放临时盘 分三步： movetower(n-1,a,b,c) 将n-1个盘从a->b， c放临时盘 movedisk(a,n,c) 将第n个盘从a->c movetower(n-1,b,c,a) 将n-1个盘从b->c,a放临时盘 void hanoi(int n, char a, char b, char c) {if (n==1) move(a,1,c); else{ hanoi(n-1,a,c,b); move(a,n,c); hanoi(n-1,b,a,c); } } hanoi塔的递归算法
34队列 34.1抽象数据类型队列的定义 队列( Queue):先进先出( First in first out) 缩写为FIFO)的线性表 仅在队尾进行插入和队头进行删除操作的线性表。 队头(ront):线性表的表头端,即可删除端。 队尾(rear):线性表的表尾端,即可插入端。 队头 对尾 a a, a 1a2 3 n 出队列 equeque) 入队列( Enqueue)
3.4 队列 3.4.1抽象数据类型队列的定义 队列（Queue）: 先进先出(First In First Out) • (缩写为FIFO）的线性表。 • 仅在队尾进行插入和队头进行删除操作的线性表。 队头（front）: 线性表的表头端，即可删除端。 队尾（rear）: 线性表的表尾端，即可插入端。 队头 对尾 a1 a2 a3 ...... an-1 an 出队列(Dequeque) 入队列(Enqueue)
队列的抽象数据类型 ADT Queue i 数据对象:D={a1|a1属于 Elemnet, 1,2,,n,n≥0) 数据关系:列队尾为队属于 D,(-23,,n) 基本操作: InitQueue(&Q) DestroyQueue(& Q) Clear Queue(& Q); QueueEmpty(Q); QueueLength(Q); GetHead(Q, &e); En Queue(&Q,e); De Queue(& Q, &e); QueueTraverse(Q, visit O ADT Queue
队列的抽象数据类型 ADT Queue { 数 据 对 象 ： D = {ai | ai 属 于 Elemset, (i=1,2,…,n, n≥0)} 数据关系 ： R1 = { ＜ ai-1 ,ai ＞ |ai-1 ,ai 属 于 D,(i=2,3,…,n)} 约定an为队尾, a1为队头。 基本操作： • InitQueue(&Q); DestroyQueue (& Q); • ClearQueue (& Q); QueueEmpty(Q); • QueueLength(Q) ; GetHead(Q,&e); • EnQueue (& Q,e); DeQueue (& Q,&e); • QueueTraverse(Q ,visit ()) }ADT Queue
队列的基本操作(之一) InitQueue(&Q) 操作结果构造一个空的队列Q。 Destroy Queue(&Q) 初始条件:队列Q已经存在 操作结果:销毁队列Q。 ClearQueue(&Q) 初始条件:队列Q已经存在 操作结果:将队列Q重置为空队列
队列的基本操作(之一) InitQueue (&Q) • 操作结果:构造一个空的队列Q。 DestroyQueue (&Q) • 初始条件: 队列Q已经存在。 • 操作结果: 销毁队列Q。 ClearQueue (&Q) • 初始条件: 队列Q已经存在。 • 操作结果: 将队列Q重置为空队列
队列的基本操作(之二) QueueEmpty (Q) 初始条件:队列Q已经存在 操作结果:若队列Q为空队列,则返回TURE 否则返回 FALSE。 Queuelength(Q) 初始条件:队列Q已经存在 结果:返回队列Q中的数据元素个数,即 列Q的长度 GetHead(Q, &e) 初始条件:队列Q已经存在且非空。 操作结果:用e返回队列Q中队头元素的值
队列的基本操作(之二) QueueEmpty(Q) • 初始条件: 队列Q已经存在。 • 操作结果: 若队列Q为空队列，则返回TURE; 否则返回FALSE。 QueueLength(Q) • 初始条件: 队列Q已经存在。 • 操作结果: 返回队列Q中的数据元素个数, 即 队列Q的长度。 GetHead(Q,&e) • 初始条件: 队列Q已经存在且非空。 • 操作结果: 用e返回队列Q中队头元素的值