c语言课件栈和队列.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《c语言课件栈和队列.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 课件 队列
- 资源描述:
-
1、栈和队列栈抽象数据类型栈的定义栈的表示和实现栈的应用举例数制转换表达式求解队列是限制仅在线性表的一端进行插入和删除运算的线性表。an.a2a1 栈顶 TOP 栈底 Bottom 栈顶(TOP)允许插入和删除的一端。栈底(bottom)不允许插入和删除的一端。空栈 表中没有元素。栈(Stack)an.a2a1进栈 退栈 栈顶 栈底进栈最先插入的元素放在栈的底部。退栈最后插入的元素最先退栈。栈的基本概念栈:又称为后进先出的线性表(LIFO表,Last In First Out)一叠书或一叠盘子。栈与子程序调用调用子程序时,计算机将子程序要用到的参数及返回地址等信息存放在栈里子程序返回时,从栈顶取回
2、返回地址,转回主调程序继续运行。处理递归调用顺序栈用数组定义(类似于顺序表),将栈底位置设置在向量两端的任意一个端点;用top(整型量,栈顶指针)来指示栈当前栈顶位置。定义:typedef(type)Element;/*栈元素的数据类型*/#define maxsize 100/*栈初始的容量*/typedef struct stackElement datamaxsize;int top;Stack;/*顺序栈类型定义*/Stack*s;/*s是顺序栈类型指针*/3 2 1 0Top=-1空栈空栈A 3 2 1 0TOP A进栈进栈 3 2 1 0DCBAB、C、D依次进栈依次进栈TOP 3
3、 2 1 0BATOPD、C依次退栈依次退栈 3 2 1 0Top=-1,B、A退栈退栈顺序栈:栈顶指针与栈中元素间的关系顺序栈栈底位置固定在数组的低端,即:S-data0-表示栈底元素;进栈:S-TOP加1(正向增长)。退栈:S-TOP减1。空栈:S-TOP TOP=maxsize-1上溢:栈满时再做进栈运算(一种出错状态,应设法避免)。顺序栈的几种基本运算置空栈判栈空进栈退栈取栈顶元素顺序栈的几种基本运算置空栈:Create(Stack&S)void Create(Stack&S)/*将顺序栈S置为空*/S.top=-1 顺序栈的几种基本运算判栈空:Bool Empty(Stack&S)/
4、*判定顺序栈S是否为空*/if(S.top=0)return False;else return True;/*Empty*/void Push(Stack&S,Element e)/*将元素e插入栈S顶部*/if(S.top=maxsize-1)Serr=StackOverflow;else S.top+;S.dataS.top=e;/*Push*/顺序栈的几种基本运算进栈:/*若栈S非空,取出栈顶元素删除*/void Pop(Element&e,Stack&S)/*Pop*/if(Empty(S)Serr=StackUnderflow;else e=S.dataS.top;S.top-;退
5、栈:Pop(S)顺序栈的几种基本运算/*取顺序栈S的栈顶*/Element Top(Stack&S)/*Top*/if(Empty(S)输出“栈空”;return NULL;else return(S.dataS.top);取栈顶:Top(S)顺序栈的几种基本运算链栈 栈的链式存储结构(当顺序栈的最大容量事先无法估计时,可采用链栈结构)。TOP e1 next栈顶栈顶 .链栈的定义:typedef struct cell*Position;typedef struct cell Element e1;Position next;Cell;typedef struct stack Positio
6、n*top;Stack;链栈的特点 插入和删除(进栈/退栈)仅能在表头位置上(栈顶)进行。链栈中的结点是动态产生的,可不考虑上溢问题。不需附加头结点,栈顶指针就是链表(即链栈)的头指针。void Push(Element e,Stack&S)Position p;p=new(Cell);p-e1=e;p-next=S.top;S.top=p;.栈底栈底xs.top链栈进栈运算链栈退栈运算void Pop(Element&e,Stack&S)Position p;if(S.top=NULL)SErr=StackUnderflow;elsee=S.top-e1;p=S.top;S.top=S.to
7、p-next;free(p);top .栈底topq栈小结顺序栈有发生上溢 的可能,而链栈通常不会发生栈满(除非整个空间均被占满)只要满足LIFO原则,均可采用栈结构。栈的应用实例:递归调用。栈的应用举例一数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+(n mod d)(185185)1010=(?)8 8(1 8 51 8 5)10 10 =(2 7 12 7 1)8 88 82 72 78 80 20 21 8 5 1 8 5 8 82 3 12 3 1余数余数 例 把十进制数159转换成八进制数。(
8、159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732栈的应用举例一数制转换void conversion()/conversion Initstack(S);scanf(“%d”,&N);while(N)Push(S,N%8);N=N/8;while(!Stackempty(s)Pop(S,e);Printf(“%d”,e);栈的应用举例一数制转换栈的应用举例一算术表达式 建立2个栈:操作数栈及运算符栈,初始为空 从左到右读取表达式,如果读到操作数则置入操作数栈中,若读到运算符时则置入运算符栈。当读到的运算符优先级比栈中的运算符高,则
9、存入栈 当读到的运算符优先级比堆栈中的运算符低或相等,则取出该运算符并从操作数栈取出相应的操作数运算,并将结果存回操作数栈;同时新运算符入栈;堆栈非空 从运算符栈中取出一个运算符 从操作数栈中取出所需操作数 计算其值后将结果存回操作数栈例 计算 2+4-3*6例 计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12栈的应用举例一算术表达式队列只允许在表的一端进行插入,而在表的另一端进行删除,是一种先入先出的线性表(FIFO)。队列的基本概念队头(head):允许删除(出队)的一端队尾(tail):允许插入的一端空队列:队列中没有元素进
展开阅读全文