例5: 表达式求值4+ 2 3 -10/54 + 6 - 2 =8=算术四则运算规则(1) 先乘除,后加减(2) 从左算到右(3) 先括号内,后括号外4+ 2 3 -10/54 + 6 - 10/5 = 10=- 10/5= 10 - 2 = 810 - 2 =1表达式常数标识符操作数(operand)运算符(operator)界限符(delimiter)算术逻辑关系括号结束符21 2:1的优先级低于 21的优先级等于 21的优先级高于 2xOPNDelse 比较ch和OPTR栈顶元素的优先级 case : 退栈,运算结果入栈4OperandType EvaluateExpression() /算术表达式求值的算符优先算法. InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while(c!=# | GetTop(OPTR)!=ch) 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; /switch /while return GetTop(OPND);/EvaluateExpression6步骤 OPTR栈 OPND栈 输入字符 主要操作例: 利用算法EvaluationExpress 求表达式 3*(7-2)的值13 *(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 72 )#PUSH(OPND,2)7# * ( -3 7 2) #Operat(7,-,2)8# * ( 3 5) #Pop(OPTR)消括号9# *3 5#Operat(3,*,5)10#15#Return(GetTop(OPND)73.3 栈与递归的实现递归函数: 直接或间接调用自己的函数1. 递归定义的数学函数:阶乘函数: 2阶Fibonaci数列: 8树 2. 具有递归特性的数据结构:RootLchildRchild广义表 A=(a,A)3. 可递归求解的问题:八皇后问题 Hanoi塔问题 9Hanoi 塔问题规则:(1) 每次只能移动一个圆盘(2) 圆盘可以插在X,Y和Z中的任一塔座上(3) 任何时刻不可将较大圆盘压在较小圆盘之上10void hanoi(int n, char x, char y, char z) /将塔座x上由小到大且自上而下编号为1至n的n个圆盘按规 / 则搬到塔座z上,y可用作辅助塔座1 2 if(n=1)3 move(x,1,z); /将编号为1的圆盘从x搬到z4 else5 hanoi(n-1,x,z,y); /将x上编号为1至n-1的圆盘移到y, /z作辅助塔 6 move(x,n,z); /将编号为n的圆盘从x移到z7 hanoi(n-1,y,x,z); /将y上编号为1至n-1的圆盘移到z, /x作辅助塔 8 9 11函数调用过程调用前, 系统完成:(1)将实参,返回地址等传递给被调用函数(2)为被调用函数的局部变量分配存储区(3)将控制转移到被调用函数的入口调用后, 系统完成:(1) 保存被调用函数的计算结果(2)释放被调用函数的数据区(3)依照被调用函数保存的返回地址将控制转移到调用函数12函数调用过程当多个函数构成嵌套调用时, 遵循后调用先返回栈13int first(int s,int t);int second(int d);int main() int m,n; . first(m,n); 1:.int first(int s,int t) int i; . second(i); 2:.int second(int d) int x,y; .栈顶栈顶14递归函数调用的实现“层次”主函数第1次调用第 i 次调用0层1层i 层“递归工作栈”“工作记录”实在参数,局部变量,返回地址15Hanoi(3,a,b,c)Hanoi(2,a,c,b)move (a,3,c)Hanoi(2,b,a,c)0116Hanoi(1,a,b,c)move(a,2,b)Hanoi(1,c,a,b)2Hanoi(3,a,b,c)Hanoi(2,a,c,b)move (a,3,c)Hanoi(2,b,a,c)01173move(a,1,c)Hanoi(3,a,b,c)Hanoi(2,a,c,b)move (a,3,c)Hanoi(2,b,a,c)Hanoi(1,a,b,c)move(a,2,b)Hanoi(1,c,a,b)012move(c,1,b)183move(a,1,c)Hanoi(3,a,b,c)Hanoi(2,a,c,b)move (a,3,c)Hanoi(2,b,a,c)Hanoi(1,a,b,c)move(a,2,b)Hanoi(1,c,a,b)012move(c,1,b)Hanoi(1,b,c,a)move(b,2,c)Hanoi(1,a,b,c)19Hanoi(3,a,b,c)Hanoi(2,a,c,b)move (a,3,c)Hanoi(2,b,a,c)Hanoi(1,a,b,c)move(a,2,b)Hanoi(1,c,a,b)Hanoi(1,b,c,a)move(b,2,c)Hanoi(1,a,b,c)0123move(a,1,c)move(c,1,b)move(b,1,a)move(a,1,c)20move(a,2,b)Hanoi(1,c,a,b)Hanoi(3,a,b,c)Hanoi(2,a,c,b)Hanoi(1,a,b,c)21move (a,3,c)Hanoi(2,b,a,c)Hanoi(1,b,c,a)321abcmove(b,2,c)Hanoi(1,c,a,b)22void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层23void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层24void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层25void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层26void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层0, 3, a, b, c27void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c28void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c29void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c30void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c2, a, c, b31void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c2, a, c, b6, 2, a, c, b32void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b6, 2, a, c, b33void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b6, 2, a, c, b34void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b6, 2, a, c, b35void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b1, a, b, c6, 2, a, c, b36void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b1, a, b, c6, 2, a, c, b6, 1, a, b, c37void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c6, 2, a, c, b6, 1, a, b, c38void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c6, 2, a, c, b6, 1, a, b, c39void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z);7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, ca, 1, c6, 2, a, c, b6, 1, a, b, c40void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c6, 2, a, c, b6, 1, a, b, c41void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, ba, 2, b6, 2, a, c, b42void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b1,c,a,b6, 2, a, c, b43void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b1,c,a,b6, 2, a, c, b8, 1, c, a, b44void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, c, a, b6, 2, a, c, b8, 1, c, a, b45void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, c, a, b6, 2, a, c, b8, 1, c, a, b46void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z);7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, c, a, bc, 1, b6, 2, a, c, b8, 1, c, a, b47void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, c, a, b6, 2, a, c, b8, 1, c, a, b48void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b6, 2, a, c, b49void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, a, c, b6, 2, a, c, b50void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, ca, 3, c51void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c2, b, a, c52void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c2, b, a, c8, 2, b, a, c53void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c8, 2, b, a, c54void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c8, 2, b, a, c55void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c8, 2, b, a, c56void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c1, b, c, a8, 2, b, a, c57void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c1, b, c, a8, 2, b, a, c6, 1, b, c, a58void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, b, c, a8, 2, b, a, c6, 1, b, c, a59void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, b, c, a8, 2, b, a, c6, 1, b, c, a60void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 b, 1, a3 层0, 3, a, b, c1, b, c, a8, 2, b, a, c6, 1, b, c, a61void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, b, c, a8, 2, b, a, c6, 1, b, c, a62void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层2, b, a, cb,2,c0, 3, a, b, c8, 2, b, a, c63void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1,a,b,c2 层2, b, a, c0, 3, a, b, c8, 2, b, a, c64void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1,a,b,c2 层2, b, a, c0, 3, a, b, c8, 2, b, a, c8, 1, a, b, c65void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c8, 2, b, a, c8, 1, a, b, c66void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c8, 2, b, a, c8, 1, a, b, c67void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 a, 1, c3 层0, 3, a, b, c1, a, b, c8, 2, b, a, c8, 1, a, b, c68void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 3 层0, 3, a, b, c1, a, b, c8, 2, b, a, c8, 1, a, b, c69void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c8, 2, b, a, c70void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 2 层0, 3, a, b, c2, b, a, c8, 2, b, a, c71void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c72void hanoi(int n, char x, char y, char z)1 2 if(n=1)3 move(x,1,z); 4 else5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 9 1 层0, 3, a, b, c3, a, b, c73void main (void) int n; unsigned char a,b,c; n=3; a=1; b=2; c=3; hanoi(n, a, b, c);0: . . .0 层74队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.a1a2a3an.入队列队头队尾75队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.出队列a1a2a3an.队头队尾76队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.出队列a1a2a3an.队头队尾77队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.出队列a1a2a3an.队头队尾78队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.出队列a1a2a3an.队头队尾79队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.出队列a1a2a3an.队头队尾80队列-Queue 队列是一种先进先出(First In First Out-FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素.a1a2a3an.出队列入队列队头队尾81双端队列-Dequea1a2a3an.插入删除插入删除 输出受限的双端队列端1端282双端队列-Dequea1a2a3an.插入删除插入删除 输出受限的双端队列 输入受限的双端队列端1端283队列的抽象数据类型数据对象:数据关系:基本操作: (1) InitQueue (&Q) /构造空队列 (2) DestroyQueue (&Q) /销毁队列 (3) ClearQueue (&S) /清空队列 (4) QueueEmpty(S) /判空. 空-TRUE,ADT Queue 84队列的抽象数据类型(续) (5) QueueLength(Q) /取队列长度 (6) GetHead (Q,&e) /取队头元素, (7) EnQueue (&Q,e) /入队列 (8) DeQueue (&Q,&e) /出队列 (9) QueueTraverse(Q,visit() /遍历ADT Queue85链队列86单链队列-队列的链式存储结构Typedef struct QNode QElemType data; struct Qnode *next;Qnode, *QueuePtr;Typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue; 87(a) 空队列(b) 元素x入队列(c) 元素y入队列(d) 元素x出队列88链队列基本操作的实现(1)初始化Status InitQueue (LinkQueue &Q) Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;/InitQueue89(2).销毁队列Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK:/ DestroyQueue链队列基本操作的实现(续)90(3).清空队列Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK:/ DestroyQueue链队列基本操作的实现(续)91(4) 队列判空 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); / QueueEmpty(5) 求队列长度 int QueueLength (LinkQueue Q) return (Q.rear-Q.front); / QueueLength链队列基本操作的实现(续)92(6).取队头元素Status GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;/GetHead链队列基本操作的实现(续)93(7).入队列Status EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;/EnQueue链队列基本操作的实现(续)94(8).出队列Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return 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链队列基本操作的实现(续)95(9) 链队列的遍历 Status QueueTraverse (LinkQueue Q, Status (*visit)(ElemType) for(p=Q.front-next;pdata) return ERROR; / QueueTraverse Status visit(ElemType e) printf(“The value of the element is %dn”, (int) e);链队列基本操作的实现(续)963.4.3 循环队列-队列的顺序存储979899循环队列-队列的顺序存储结构#define MAXQSIZE 100 /最大队列长度Typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针 int rear; /尾指针SqQueue; 100(1)初始化Status InitQueue (SqQueue &Q) /构造一个空队列Q Q.base=(ElemType *) malloc(MAXQSIZE *sizeof(ElemType); if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;/InitQueue循环队列基本操作的实现101(2).销毁队列Status DestroyQueue (SqQueue &Q) Q.front=Q.rear=0; free(Q); return OK:/ DestroyQueue循环队列基本操作的实现(续)102(3).清空队列Status ClearQueue (SqQueue &Q) Q.front=Q.rear=0; return OK:/ DestroyQueue循环队列基本操作的实现(续)103(4) 队列判空 Status QueueEmpty (SqQueue Q) return (Q.front=Q.rear); / QueueEmpty(5) 求队列长度 int QueueLength (SqQueue Q) return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; / QueueLength循环队列基本操作的实现(续)104(6).取队头元素Status GetHead (SqQueue Q, QElemType &e) /返回队首元素 if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front= (Q.front+1)%MAXQSIZE; return OK;/GetHead循环队列基本操作的实现(续)105(7).入队列Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR;/队列满 Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;/EnQueue循环队列基本操作的实现(续)106(8).出队列Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;/DeQueue循环队列基本操作的实现(续)107(9) 循环队列的遍历 Status QueueTraverse (SqQueue Q, Status (*visit)(ElemType) for(p=Q.front-next;pdata) return ERROR; / QueueTraverse Status visit(ElemType e) printf(“The value of the element is %dn”, (int) e); 循环队列基本操作的实现(续)108练习3.17, 3.28, 5.17(1), (3), (5)109