C语言《栈》.ppt

《C语言《栈》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈本次课程内容掌握栈的定义和原理掌握顺序栈的基本操作。了解链式栈的基本操作。掌握栈的应用（重点、难点）（重点、难点）一、栈的定义栈：只能在表的一端进行插入和删除操作的线性表。栈顶(top)：允许插入和删除的一端。栈底(bottom)：不允许插入和删除的另一端。空栈：不含元素的空表。1.1栈的特点a1a2a3入栈出栈栈底插入：入栈、进栈、压栈删除：出栈、弹栈特点先进后出（FILO）后进先出（LIFO）1.2顺序栈top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0进栈：top加1top123450进栈Atop出栈栈满BCDEF设数组大小为Mtop=0,栈

2、空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)出栈：top减1toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空实现：一维数组s[M]1.2.1顺序栈的类型定义#defineMAX100/*顺序栈最大容量*/typedefintDataTypetypedefstruct{DataTypedata[MAX];inttop;}SeqStack;SeqStack*s;1.2.2顺序栈的置空1、置空栈voidinitstack(seqstack*s){s–>top=-1;}2、判断栈空in

3、tstackempty(seqstack*s){return(s–>top==-1);}1.2.3栈满3、判断栈满intstackfull(seqstack*s){return(s–>top==stacksize-1);}1.2.4顺序栈的入栈4、入栈voidpush(seqstack*s，datatypex){if(stackfull(s))error(“stackoverflow”);s–>data[++s–>top]=x;}1.2.5顺序栈的出栈5、出栈viodpops(SeqStack*s){if(stackemptys(&s)){printf("underflow

4、");}else{s->top--;}}1.2.6取栈顶元素6、取栈顶元素Datatypestacktop(seqstack*s){if(stackempty(s)error(“stackisempty”);returns–>data[s–>top];}1.2.7代码演示1用顺序栈实现0~10元素的入栈和出栈演示代码演示23_1栈顶^…...topdatalink栈底结点定义typedefstructnode{intdata;structnode*link;}JD;1.3链式栈1.3.1链式栈的入栈入栈算法^…...栈底toptopxpLSNode*pushls(LSN

5、ode*top,intx){LSNode*p;p=(LSNode*)malloc(sizeof(LSNode));p->data=x;p->link=top;return(p);}1.3.2链式栈的出栈出栈算法top^…...栈底topqLSNode*popls(LSNode*top){LSNode*q;if(top){q=top;top=top->link;free(q);}returntop;}1.3.3代码演示2用链式栈实现0~10元素的入栈和出栈演示代码演示23_2二、栈的应用-过程的嵌套调用r主程序srrrs子过程1rst子过程2rst子过程32.1递归调用例递归

6、的执行情况分析voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：1，2，2，3，3，3，2.1.1递归调用分析主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2

7、(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)2.2TowerofHanoi（汉诺塔）问题有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘；圆盘可在三个塔座上任意移动；任何时刻，每个塔座上不能将大盘压到小盘上。ABC问题描述nxyz返回地址解决方法：n=1时，直接把圆盘从A移到Cn>