C语言《栈》.ppt

《C语言《栈》.ppt》由会员分享，可在线阅读，更多相关《C语言《栈》.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、栈栈本次课程内容u掌握栈的定义和原理u掌握顺序栈的基本操作。u了解链式栈的基本操作。u掌握栈的应用（重点、难点）（重点、难点）（重点、难点）（重点、难点）一、栈的定义栈栈：只能在表的一端进行插入和删除操作的线性只能在表的一端进行插入和删除操作的线性表。表。栈顶栈顶(top)(top)：允许插入和删除的一端。：允许插入和删除的一端。栈底栈底(bottom)(bottom)：不允许插入和删除的另一端。：不允许插入和删除的另一端。空栈空栈：不含元素的空表。：不含元素的空表。1.1 栈的特点a1a2a3入栈出栈栈底插入：入栈、进栈、压栈删除：出栈、弹栈u特点特点先进后出（先进后出（FILO）后进先出（

2、后进先出（LIFO）1.2 顺序栈top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0进栈：top加1top123450进栈Atop出栈栈满BCDEF设数组大小为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)出栈：top减1toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空实现：一维数组sM1.2.1 顺序栈的类型定义#define MAX 100/*顺序栈最大容量*/typedef int DataTypetypedef struct DataType data

3、MAX;int top;SeqStack;SeqStack*s;1.2.2 顺序栈的置空1、置空栈 void initstack(seqstack*s)stop=-1;2、判断栈空 int stackempty(seqstack*s)return(stop=-1);1.2.3 栈满3、判断栈满 int stackfull(seqstack *s)return(stop=stacksize-1);1.2.4 顺序栈的入栈4、入栈 void push(seqstack *s，datatype x)if(stackfull(s)error(“stack overflow”);sdata+stop=x

4、;1.2.5 顺序栈的出栈5、出栈viod pops(SeqStack*s)if(stackemptys(&s)printf(underflown);elses-top-;1.2.6 取栈顶元素6、取栈顶元素 Datatype stacktop(seqstack *s)if(stackempty(s)error(“stack is empty”);return sdatastop;1.2.7 代码演示1u用顺序栈实现010元素的入栈和出栈演示代码演示23_1栈顶栈顶 .topdata link栈底l结点定义typedef struct node int data;struct node *li

5、nk;JD;1.3 链式栈1.3.1 链式栈的入栈l入栈算法 .栈底toptopxpLSNode*pushls(LSNode*top,int x)LSNode*p;p=(LSNode*)malloc(sizeof(LSNode);p-data=x;p-link=top;return(p);1.3.2 链式栈的出栈l出栈算法top .栈底topqLSNode*popls(LSNode*top)LSNode*q;if(top)q=top;top=top-link;free(q);return top;1.3.3 代码演示2u用链式栈实现010元素的入栈和出栈演示代码演示23_2二、栈的应用-过程的

6、嵌套调用r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程32.1 递归调用例例 递归的执行情况分析递归的执行情况分析 void print(int w)int i;if(w!=0)print(w-1);for(i=1;i1时，先把上面时，先把上面n-1个圆盘从个圆盘从A移到移到B,然后将然后将n号盘从号盘从A移到移到C,再将再将n-1个盘从个盘从B移到移到C。即把求解。即把求解n个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解n-1个圆盘的个圆盘的Hanoi问题，依次问题，依次类推，直至转化成只有一个圆盘的类推，直至转化成只有一个圆盘的Hanoi问题问题执行情

7、况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示2.2.1 问题分析2.3 代码分析 main()int m;printf(Input the number of disks:);scanf(%d,&m);printf(The steps to moving%3d disks:n,m);hanoi(m,A,B,C);void hanoi(int n,char x,char y,char z)if(n=1)move(1,x,z);else hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);void move(int h,char

8、c,char f)printf(%d:%c-%cn,h,c,f);2.4 多进制输出例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732三、项目教学：学员信息管理3.1 用栈排序（1）功能功能功能功能9 9：打印数据：打印数据：打印数据：打印数据项目演示：用栈排序，参考代码：项目演示：用栈排序，参考代码：23_3注意观察，列表中年龄是乱序。3.2 用栈排序（2）完成功能完成功能完成功能完成功能6 6：用栈排序：用栈排序：用栈排序：用栈排序注意观察，最后列表按年龄升序排列了。且入栈时顺序和出栈时的顺序相反：先进后出！本次课课程总结1掌握栈的定义和原理2掌握栈的基本操作3掌握栈的应用掌握栈的应用作业布置与要求 1、用代码解决汉诺塔问题。2、编写函数，利用栈对学员考试信息的链表进行排序。