[其它课程]数据结构ch31.ppt
《[其它课程]数据结构ch31.ppt》由会员分享,可在线阅读,更多相关《[其它课程]数据结构ch31.ppt(109页珍藏版)》请在三一办公上搜索。
1、1,例5:表达式求值,4+2 3-10/5,4,+,6,-,2,=,8,=,算术四则运算规则,(1)先乘除,后加减,(2)从左算到右,(3)先括号内,后括号外,4+2 3-10/5,4,+,6,-,10/5,=,10,=,-,10/5,=,10,-,2,=,8,10,-,2,=,2,表达式,3,1 2:,1=2:,1 2:,1的优先级低于 2,1的优先级等于 2,1的优先级高于 2,=,x,=,x,x,4,工作栈 OPTR-运算符 OPND-操作数或运算结果,算符优先算法,5,OperandType EvaluateExpression()/算术表达式求值的算符优先算法.InitStack(O
2、PTR);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:/栈顶元素优先权低 Push(OPTR,c);c=getchar();break;case=:/脱括号 Pop(OPTR,x);c=getchar();break;,6,case:/退栈,并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,
3、a);Push(OPND,Operate(a,theta,b);break;/switch/while return GetTop(OPND);/EvaluateExpression,7,例:利用算法EvaluationExpress 求表达式 3*(7-2)的值,1,PUSH(OPND,3),#,2,#,3,PUSH(OPTR,*),3,#*,3,PUSH(OPTR,(),4,#*(,3,PUSH(OPND,7),5,#*(,3 7,PUSH(OPTR,-),6,#*(-,3 7,PUSH(OPND,2),7,#*(-,3 7 2,Operat(7,-,2),8,#*(,3 5,Pop(OP
4、TR)消括号,9,#*,3 5,#,Operat(3,*,5),10,#,15,#,Return(GetTop(OPND),8,3.3 栈与递归的实现,递归函数:直接或间接调用自己的函数,1.递归定义的数学函数:,阶乘函数:,2阶Fibonaci数列:,9,树,2.具有递归特性的数据结构:,Root,Lchild,Rchild,广义表,A=(a,A),3.可递归求解的问题:,八皇后问题,Hanoi塔问题,10,Hanoi 塔问题,规则:,(1)每次只能移动一个圆盘,(2)圆盘可以插在X,Y和Z中的任一塔座上,(3)任何时刻不可将较大圆盘压在较小圆盘之上,11,void hanoi(int n,
5、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,12,函数调用过程,调用前,系统完成:,(1)将实参,返回地址等传递给被调用函数,(2)为被调用函数的局部变量分配存储区,(3)将控制
6、转移到被调用函数的入口,调用后,系统完成:,(1)保存被调用函数的计算结果,(2)释放被调用函数的数据区,(3)依照被调用函数保存的返回地址将控制转移到调用函数,13,函数调用过程,栈,14,int 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;.,栈顶,15,递归函数调用的实现,“层次”,“递归工作栈”,“工作记录”,实在参数,局部变量,返回地址,16,Hanoi(3
7、,a,b,c),Hanoi(2,a,c,b),move(a,3,c),Hanoi(2,b,a,c),0,1,17,Hanoi(1,a,b,c),move(a,2,b),Hanoi(1,c,a,b),2,18,3,move(a,1,c),move(c,1,b),19,Hanoi(1,b,c,a),move(b,2,c),Hanoi(1,a,b,c),20,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),Hanoi(1,b,c,a),move(b,2
8、,c),Hanoi(1,a,b,c),0,1,2,3,move(a,1,c),move(c,1,b),move(b,1,a),move(a,1,c),21,move(a,2,b),Hanoi(1,c,a,b),Hanoi(3,a,b,c),Hanoi(2,a,c,b),Hanoi(1,a,b,c),22,move(a,3,c),Hanoi(2,b,a,c),Hanoi(1,b,c,a),move(b,2,c),Hanoi(1,c,a,b),23,void main(void)int n;unsigned char a,b,c;n=3;a=1;b=2;c=3;hanoi(n,a,b,c);0:.
9、,0 层,24,void main(void)int n;unsigned char a,b,c;n=3;a=1;b=2;c=3;hanoi(n,a,b,c);0:.,0 层,25,void main(void)int n;unsigned char a,b,c;n=3;a=1;b=2;c=3;hanoi(n,a,b,c);0:.,0 层,26,void main(void)int n;unsigned char a,b,c;n=3;a=1;b=2;c=3;hanoi(n,a,b,c);0:.,0 层,27,void main(void)int n;unsigned char a,b,c;n=
10、3;a=1;b=2;c=3;hanoi(n,a,b,c);0:.,0 层,0,3,a,b,c,28,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,1 层,0,3,a,b,c,3,a,b,c,29,void 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);move(x,n,z);hano
11、i(n-1,y,x,z);8 9,1 层,0,3,a,b,c,3,a,b,c,30,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,1 层,0,3,a,b,c,3,a,b,c,31,void 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);move(x,n,z);hanoi(n-1,y,
12、x,z);8 9,1 层,0,3,a,b,c,3,a,b,c,2,a,c,b,32,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,1 层,0,3,a,b,c,3,a,b,c,2,a,c,b,6,2,a,c,b,33,void 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);move(x
13、,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,6,2,a,c,b,34,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,6,2,a,c,b,35,void 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
14、,z,y);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,6,2,a,c,b,36,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,1,a,b,c,6,2,a,c,b,37,void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z)
15、;4 else5 hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,1,a,b,c,6,2,a,c,b,6,1,a,b,c,38,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,a,b,c,6,2,a,c,b,6,1,a,b,c,39,void hanoi(int n,char
16、x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,a,b,c,6,2,a,c,b,6,1,a,b,c,40,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,a,b,c,a,1,c,6,2,a,c
17、,b,6,1,a,b,c,41,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,a,b,c,6,2,a,c,b,6,1,a,b,c,42,void 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);move(x,n,z);hanoi(n-1,y,x,z);8
18、 9,2 层,0,3,a,b,c,2,a,c,b,a,2,b,6,2,a,c,b,43,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,1,c,a,b,6,2,a,c,b,44,void 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);move
19、(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,1,c,a,b,6,2,a,c,b,8,1,c,a,b,45,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,c,a,b,6,2,a,c,b,8,1,c,a,b,46,void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 m
20、ove(x,1,z);4 else5 hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,c,a,b,6,2,a,c,b,8,1,c,a,b,47,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,c,a,b,c,1,b,6,2,a,c,b,8,1,c,a,b,48,void hanoi(int
21、 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,3 层,0,3,a,b,c,1,c,a,b,6,2,a,c,b,8,1,c,a,b,49,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,6,2,a
22、,c,b,50,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,2 层,0,3,a,b,c,2,a,c,b,6,2,a,c,b,51,void 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);move(x,n,z);hanoi(n-1,y,x,z);8 9,1 层,0,3,a,b,c,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其它课程 其它 课程 数据结构 ch31
链接地址:https://www.31ppt.com/p-4886325.html