[其它课程]数据结构ch3_1.ppt
《[其它课程]数据结构ch3_1.ppt》由会员分享,可在线阅读,更多相关《[其它课程]数据结构ch3_1.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() /算术表达式求值的算符优先算法.
2、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 : /栈顶元素优先权低 Push(OPTR,c); c=getchar(); break; case =: /脱括号 Pop(OPTR,x); c=getchar(); break;,6,case : /退栈,并将运算结果入栈 Pop(
3、OPTR,theta); Pop(OPND,b); Pop(OPND,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
4、,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),8,3.3 栈与递归的实现,递归函数: 直接或间接调用自己的函数,1. 递归定义的数学函数:,阶乘函数:,2阶Fibonaci数列:,9,树,2. 具有递归特性的数据结构:,Root,Lchild,Rchild,广义表,A=(a,A),3. 可递归求解的问题:,八皇后问题,Hanoi塔问题,10,Hanoi 塔问题,规则:,(1) 每次只能移动一个
5、圆盘,(2) 圆盘可以插在X,Y和Z中的任一塔座上,(3) 任何时刻不可将较大圆盘压在较小圆盘之上,11,void 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搬到z 4 else 5 hanoi(n-1,x,z,y); /将x上编号为1至n-1的圆盘移到y, /z作辅助塔 6 move(x,n,z); /将编号为n的圆盘从x移到z 7 hanoi(n-1,y,x,z); /将y上编号为1至n-
6、1的圆盘移到z, /x作辅助塔 8 9 ,12,函数调用过程,调用前, 系统完成:,(1)将实参,返回地址等传递给被调用函数,(2)为被调用函数的局部变量分配存储区,(3)将控制转移到被调用函数的入口,调用后, 系统完成:,(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; .
7、second(i); 2:. int second(int d) int x,y; . ,栈顶,15,递归函数调用的实现,“层次”,“递归工作栈”,“工作记录”,实在参数,局部变量,返回地址,16,Hanoi(3,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),
8、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),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
9、,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: . . . ,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;
10、 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=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 i
11、f(n=1) 3 move(x,1,z); 4 else 5 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 else 5 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,30,void hanoi(int n, c
12、har x, char y, char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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 else 5 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,
13、 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 else 5 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 else 5 hanoi(n-1,x,z
14、,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,34,void hanoi(int n, char x, char y, char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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, c
15、har z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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,36,void hanoi(int n, char x, char y, char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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
16、, 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); 4 else 5 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,
17、z); 4 else 5 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 x, char y, char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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,
18、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 else 5 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, 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 else 5 han
19、oi(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 else 5 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,a, 2, b,6, 2, a, c, b,43,voi
20、d hanoi(int n, char x, char y, char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 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 else 5 hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-
21、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 else 5 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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其它课程 其它 课程 数据结构 ch3_1
链接地址:https://www.31doc.com/p-2003045.html