单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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):,算符间的优先关系:,1,2,+-*/()#,+,-,*,/,(,#=,Precede:判定运算符栈的栈顶运算符1与读入的运算符2之间,的优先关系的函数.,Operate:进展二元运算ab的函数.,算术表达式求值过程(算法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栈 输入字符 主要操作,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),例：汉诺塔问题：,将a柱子上的盘移到 c柱，用 b柱放临时盘,要求：一次只能移动一个盘，大盘不行放于小盘上。,a,b,c,hanoi塔问题,定义函数：movetower(n,a,c,b)n个盘ac，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塔的递归算法,3.4 队列,3.4.1抽象数据类型队列的定义,队列Queue:先进先出(First In First Out),(缩写为FIFO的线性表。,仅在队尾进展插入和队头进展删除操作的线性表。,队头front:线性表的表头端，即可删除端。,队尾rear:线性表的表尾端，即可插入端。,队头,对尾,.,a,1,a,2,a,3,a,n-1,a,n,入队列(Enqueue),出队列(Dequeque),队列的抽象数据类型,ADT Queue,数据对象：D=ai|ai属于Elemset,(i=1,2,n,n0),数据关系：R1=ai-1,ai|ai-1,ai属于D,(i=2,3,n)商定an为队尾,a1为队头。,根本操作：,InitQueue(,ClearQueue(,QueueLength(Q);GetHead(Q,EnQueue(,QueueTraverse(Q,visit),ADT Queue,队列的根本操作(之一),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中队头元素的值。,队列的根本操作(之三),EnQueue(&Q,e),初始条件:队列Q已经存在。,操作结果:插入元素e为新的队尾元素。,DeQueue(&Q,&e),初始条件:队列Q已经存在且非空。,操作结果:删除队列Q 的队头元素并用e返回其值。,QueueTraverse(Q,visit),初始条件:队列Q已经存在且非空。,操作结果:从队头到队尾依次对队列Q的每个元素调用函数visit。一旦visit 失败，则操作失败。,3.4.2 链队列-,队列的链式表示与实现,typedef,struct QNode,QElemType data;,struct,QNode,*next;,Qnode,*QueuePtr;,typedef struct,QueuePtr front;/队头指针,QueuePtr rear;/队尾指针,LinkQueue;,#define OK 1,#define OVERFLOW-1,#define ERROR 0,data,*next,front,rear,链队列,示意图,front,rear,front,rear,赵,front,rear,钱,赵,front,rear,钱,赵,(a)空队列,(b)元素“赵”入队列,(c)元素“钱”入队列,(d)元素“赵”出队列,链队列,的操作实现举例,/*,InitQueue,构造一个空的队列Q*/,Status,InitQueue,(,LinkQueue,&Q,),Q.rear=(QueuePtr),malloc,(,sizeof,(QNode);,Q.front=Q.rear;,if,(!Q.front),return,(OVERFLOW);,Q.front-next=,NULL,;,return,OK;,/InitQueue,链队列,的操作实现,(,DestroyQueue,),/销毁队列Q,Status,DestroyQueue,(,LinkQueue,&Q,),while(Q.front),Q.rear=Q.front-next;,free,(Q.front);,Q.front=Q.rear;,return,OK;,/DestroyQueue,链队列,的操作实现(,EnQueue,),/插入元素e为新的队尾元素,Status,EnQueue,(,LinkQueue,&Q,QelemType e,),p=(QueuePtr),malloc,(,sizeof,(QNode);,if,(!p),return,(OVERFLOW);,p-data=e;,p-next=,NULL,;,Q.rear-next=p;,Q.rear=p;,return,OK;,/EnQueue,链队列的操作实现(DeQueue)/假设队列不空,删除队列Q 的队头元素并用e返回其值,同时返回OK;否则返回ERROR。,Status,DeQueue,(,LinkQueue,&Q,QelemType&e,),if,(Q.front=Q.rear),retrun,ERROR;,p=Q.front-next;,e=p-data;,Q.front-next=p-next;,if,(Q.rear=p)Q.rear=Q.front,;,free,(p);,return,OK;,/,DeQueue,3.4.3 循环队列-队列的挨次表示与实现,承受挨次存储构造,商定:1)初始空队列：front=rear=0;,2)插入新的元素时,rear+;,3)删除队头元素时,front+;,J,1,J,2,J,3,Q.front,Q.rear,J,3,Q.front,Q.rear,J,5,J,6,Q.front,Q.rear,Q.rear,Q.front,1,0,2,3,5,4,循环列表-解决数组越界但未占满空间的方法,1,0,maxsize-1,.,Q.front,Q.rear,.,队列,当Q.rear Q.front时:Q.rear Q.front =队列中元素个数,当Q.rear Q.front时:Q.rear Q.front+maxsize=队列中元素个数,当Q.rear=Q.front时:队列是空或满,循环队列的头尾指针,0,1,2,3,4,5,J,3,J,4,J,5,Q.rear,Q.front,(a)一般队列,0,1,2,3,4,5,Q.rear,Q.front,(c)空队列,J,6,J,3,J,4,J,5,0,1,2,3,4,5,J,7,J,8,Q.rear,Q.front,(b)满队列,循环队列-队列的挨次存储构造实现(1),typedef struct,QElemType *base;/存储空间基地址,int front;/队头指针,int rear;/队尾指针,SqQueue;,#define MAXSIZE 100,Status,InitQueue,(Sq,Queue,&Q,),Q,.base=(QElemType*),malloc,(,sizeof,(QElemType),*MAXSIZE);,if,(!Q.base),return,(OVERFLOW);,Q.front =Q.rear=0;,return,OK;,/InitQueue,循环队列-队列的挨次存储构造实现(2),Status,EnQueue,(,SqQueue,&Q,QelemType e,),if,(Q.rear+1)%MAXSIZE=Q.front),return,(ERROR);,Q.baseQ.rear=e;,Q.rear=(Q.rear+1)%MAXSIZE;,return,OK;,/EnQueue,循环队列-队列的挨次存储构造实现(3),Status,DeQueue,(,SqQueue,&Q,QelemType&e,),if,(Q.front=Q.rear),retrun,ERROR;,e=Q.baseQ.front;,Q.front=(Q.front+1)%MAXSIZE;,return,OK;,/,DeQueue,试验与习题,理论习题 3.7,3.11,3.13,3.18,试验题:,写一个主程序来上机验证挨次存储构造-循环队列的根本操作；,3.18,