数据结构 教学课件 作者 晋良颖 3.ppt

数据结构 教学课件 作者 晋良颖 3.ppt

ID:50048666

大小:796.00 KB

页数:47页

时间:2020-03-08

数据结构 教学课件 作者 晋良颖 3.ppt_第1页
数据结构 教学课件 作者 晋良颖 3.ppt_第2页
数据结构 教学课件 作者 晋良颖 3.ppt_第3页
数据结构 教学课件 作者 晋良颖 3.ppt_第4页
数据结构 教学课件 作者 晋良颖 3.ppt_第5页
资源描述:

《数据结构 教学课件 作者 晋良颖 3.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、第三章栈和队列3.1栈栈的主要操作如下:(1)、建立一个空栈(2)、进栈(3)、出栈:(4)、判断一个栈是否为空?(5)、判断栈是否已满?(6)、获得栈顶元素值退出图3-13.1.2栈的表示和操作的实现1、顺序存储的栈#defineMAXSIZE50typedefstruct{elemtypeelem[MAXSIZE];inttop;}SQSTACK;(1)、建立一个空栈voidinitstack(SQSTACK*s){(*s).top=-1;}(2)、判断一个栈是否为空intstackempty(SQSTACKs){if(s.t

2、op==-1)return1;elsereturn0;}(3)、让一个数据元素为e的结点进栈。算法3.1如书第42页所示(4)、出栈一个结点并得到栈顶数据元素值算法3.2如书第42页所示(5)、获取栈顶元素值voidgetelm(SQSTACKs,elemtype*e){if(s.top==-1){printf(“栈空”);return;*e=s.elem[s.top];}1、接存储的栈(1)、建立一个空栈NODEPTRtop;top=NULL;(2)、让一个数据元素为e的结点进栈算法3.3如书第43页所示(3)、出栈一个结点

3、并得到栈顶数据元素值算法3.4如书第43页所示3.1.3栈的应用举例1、子程序的调用和返回图3-21、算术表达式求值表3.1算符的栈内、外优先级[例1]计算:2+3*2^2^2*5-2;图3-3[例2]计算3*2^(4+2*2-6)-5;图3.4算法3.5如书第47页所示例2的算式的三种形式为:中辍式:3*2^(4+2*2-6)-5;前辍式:-*3^2-+4*2265;后辍式:32422*+6-^*5-;图3-5把输入的中辍表达式化成后辍式的算法算法3.6如书第49页所示将算式“2+3*2^2^2*5-2;”化为拓辍式的过程:图3

4、-61、栈与递归1n=0

5、

6、n=1n!=n*(n-1)!n>=2例如,我们要计算5!,按定义有:5!=5*4!=5*4*3!=5*4*3*2!=5*4*3*2*1!=120[例3]Ackermann函数A(n,x,y)的计算x+1n=0xn=1,y=00n=2,y=0A(n,x,y)=1n=3,y=02n>=4,y=0A(n-1,A(n,x,y-1),x)n!=0,y!=0A(3,1,2)=A(2,A(3,1,1),1)=A(2,A(2,A(3,1,0),1),1)=A(2,A(2,1,1),1)=A(2,A(1,A(2,1,0)

7、,1),1)=A(2,A(1,0,1),1)=A(2,A(0,A(1,0,0),0),1)=A(2,A(0,0,0),1)=A(2,1,1)=A(1,A(2,1,0),1)=A(1,0,1)=A(0,A(1,0,0),0)=A(0,0,0)图3-7计算Ackermann函数A(n,x,y)的算法思想可以描述如下:反复执行:(1)、递归:只要有n!=0&&y!=0则反复执行:计算A(n,x,y-1);y--;并将(n-1,x)作返回信息进栈;(2)、返回:计算出递归函数终点值v;若栈空则结束算法,否则出栈一组值,作新参数(n,y);

8、v赋给x;构造出一个新函数A(n,x,y),再递归。定义递归出口,即n=0或y=0时的Ackermann函数如下算法3.7如书第52页所示定义栈中元素类型为一个结构类型:typedefstruct{intn;intx;}elemtype;算法3.8如书第53页所示定义栈中元素类型为一个结构类型:typedefstruct{intn;intx;}elemtype;算法3.9如书第53页所示另一种处理算法:定义栈中元素类型为:typedefstruct{intn;intx;inty;}elemtype;图3-8算法3.9如书第53页所

9、示[例4]迷宫问题图3-9定义栈中元素类型为:typdefstruct{intx;/*行下标*/inty;/*列下标*/intv;/*方向号*/}elemtype;算法3.10如书第56页所示[例5]n阶汉诺塔(Hanoi)问题(1)、每次只能移动一个圆盘;(2)、圆盘可以插在x、y、z中任一塔座上;(3)、任何时刻都不能将一个大盘压在小盘上。图3-10算法3.11如书第58页所示图3-11定义栈中元素类型为:typdefstruct{intn;/*盘子数目(返回时代表编号)*/charx,y,z;/*起始针座、辅助针座和目标针座

10、*/}elemtype;算法3.12如书第59页所示将n个盘子从x座移到z座的一项任务可以分为三项任务来完成:(1)、将n-1个盘子由x座移到y座;(2)、把第n号盘子从x座移到z座;(3)、将n-1个盘子由y座移到z座。图3-12算法3.13如书

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。