数据结构PPT数据结构.ppt

数据结构PPT数据结构.ppt

ID:52508143

大小:389.82 KB

页数:47页

时间:2020-04-09

数据结构PPT数据结构.ppt_第1页
数据结构PPT数据结构.ppt_第2页
数据结构PPT数据结构.ppt_第3页
数据结构PPT数据结构.ppt_第4页
数据结构PPT数据结构.ppt_第5页
资源描述:

《数据结构PPT数据结构.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序3.2.4迷宫求解3.2.5表达式求值3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。假

2、设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。3.1.2顺序栈由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变

3、量top例、一叠书或一叠盘子。栈的抽象数据类型的定义如下:P44anan-1a2a1……栈顶栈底top7654321-1来指示当前栈顶的位置,通常称top为栈顶指针。因此,顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下:#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即s

4、–>data[0]是栈底元素,那么栈顶指针s–>top是正向增加的,即进栈时需将s–>top加1,退栈时需将s–>top减1。因此,s–>top<0表示空栈,s–>top=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。上溢是一种出错状态,应该设法避免之;下溢则可能是正常现象,因为栈在程序中使用时,其初态或终态都是空栈,所以下溢常常用来作为程序控制转移的条件。1、置空栈voidinitstack(seqstack*s){s–>

5、top=-1;}2、判断栈空intstackempty(seqstack*s){return(s–>top==-1);}3、判断栈满intstackfull(seqstack*s){return(s–>top==stacksize-1);}4、进栈voidpush(seqstack*s,datatypex){if(stackfull(s))error(“stackoverflow”);s–>data[++s–>top]=x;}5、退栈datatypepop(seqstack*s){if(stackempty(

6、s))error(“stackunderflow”);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}6、取栈顶元素Datatypestacktop(seqstack*s){if(stackempty(s)error(“stackisenpty”);returns–>data[s–>top];}3.2栈的应用举例由于栈结构具有的后进先出的固有特性,致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.2.1数制转换十进制N和其它

7、进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8,其运算过程如下:nndiv8nmod8134816841682102125202voidconversion(){initstack(s);scanf(“%”,n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e)

8、;}}3.2.2括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例:(()()(()))3.2.3行编辑程序在编辑程序中,设立一个输入缓冲区,用于接受用户输入的一行字符,然后逐行存入用户数据区。允许用户输入错误,并在发现有误时可以及时更正。行编辑程序算法如下:voidlineedit(){initstack(s);ch=gether();whil

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

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

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