合工大数据结构02-栈.ppt

《合工大数据结构02-栈.ppt》由会员分享，可在线阅读，更多相关《合工大数据结构02-栈.ppt（29页珍藏版）》请在三一办公上搜索。

1、1,数 据 结 构（第二章 栈）Data Structures张晶计算机与信息学院 2023/9/6,2,第二章 栈,第二章 栈（stack）2.1 栈的定义和运算 2.2 顺序栈 2.3 栈的应用,3,第二章 栈,栈是软件设计中最基本的数据结构，这是本课程所介绍的第一种数据结构。学习栈结构时，需要掌握哪些方面的内容？为此，回顾一下上一章所介绍的数据结构的组成部分。由此可知，对每一种结构的学习的组成部分。,逻辑结构,分析,运算实现（算法）,运算定义,数据结构的组成,4,2.1 栈的定义和运算,2.1.1 栈的定义栈是只能在一端插入和删除元素的线性表。术语：栈顶,栈底,入栈（压栈）,出栈（弹栈）

2、,入栈(PUSH),出栈(POP),栈顶(top),栈底(bottom),逻辑结构和运算,a1 a2 an,特性：后进先出(LIFO)-Last in First out,a1,a2,an,an,a2,a1,5,2.1 栈的定义和运算,2.1.2 栈的运算1.栈的基本运算定义对栈的基本运算有如下几个：(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)

3、出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？,运算定义,6,2.1.2 栈的运算,2.栈的运算的C+描述如何用C+描述栈的内容和运算？一种方法是：将栈的有关数据和运算封装在一起，以C+的类的形式来封装描述。封装的数据和运算要便于被有关程序来调用。因此，栈的C+描述的框架如下所示：class stack;,运算描述部分,数据描述部分,类的名称,类的框架,7,2.1.2 栈的运算,下面讨论栈的运算的C+描述的细节，先给出每一个运算的对应描述：初始化函数的描述,栈的C+类描述：class stack stack();栈的数据成员;,栈的运算(1)初始化：设置栈为空。(2)判断栈为空：

4、若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？,采用C+的构造函数,8,2.1.2 栈的运算,判断函数的对应,栈的C+类描述：class stack stack();Bool empty()Bool full()栈的数据成员;,栈的运算(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判

5、断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？,判断为空的函数,判断为满的函数,const;,const;,9,2.1.2 栈的运算,其他几个函数的对应描述分析：（1）几个运算的条件可能有不成立的情况，因此，需要给予明确的反映。（2）设立运算是否正常的类型error_code，正常时返回success,否则返回错误类型，如overflow,underflow等。enum error

6、_code success,overflow,underflow;（3）可以将这几个函数的类型设置为error_code；（4）如果需要返回其他的值，可以作为参数来返回。,10,2.1.2 栈的运算,由上述讨论可得到其他几个函数的功能描述：（4)取栈顶元素的运算功能描述：如果栈不空，则取出栈顶元素到参数x中，然后返回success。否则，返回downflow。对应的运算函数为：error_code get_top(elementtype,11,2.1.2 栈的运算,(6)出栈的运算功能描述：如果栈不空，删除当前栈顶的元素，并返回success。否则，返回underflow。对应的运算函数为：e

7、rror_code pop();,12,2.1.2 栈的运算,由此得到栈的类stack的函数成员列表如下：class stack stack();/初始化 Bool empty()const;/判断空 Bool full()const;/判断满 error_code get_top(elementtype 问题：上述类的描述是否还需要补充什么？,13,2.2 顺序栈,2.2.1 存储结构：假设有一个足够大的存储空间（数组）data,可用于存储栈的元素。则可将栈中元素连续地存储到数组的各元素-顺序存储方式。如下图所示：其中：为了能随时知道栈中的元素个数，设置了一个计数变量count。将数组dat

8、a和count作为类stack的数据成员。,栈的存储结构,a1,a2,an,0,1,n-1,maxlen-1,n,data,count,顺序栈存储结构,14,2.2 顺序栈,由此而得到类stack的完整描述。封装类:class stack public:stack();Bool empty()const;Bool full()const;error_code get_top(elementtype,这是起什么作用的？,作用是什么？,15,2.2 顺序栈,2.2.2 运算实现：即类class的各函数成员的具体实现。初始化函数的实现：stack:stack()count=0;,16,2.2 顺序栈

9、,判断空的函数的实现：Bool stack:empty()const if(count=0)return TRUE;else return FALSE;判断满的函数的实现：Bool stack:full()const if(count=maxlen)return TRUE;else return FALSE;/等价于：return count=maxlen;,17,2.2 顺序栈,取栈顶元素的实现：error_code stack:get_top(elementtype,18,2.2 顺序栈,入栈的实现：error_code stack:push(const elementtype x)if(

10、full()return overflow;datacount=x;count+;return success;,19,2.2 顺序栈,出栈的实现 error_code stack:pop()if(empty()return underflow;count-;return success;算法分析：时间性能 全部是O(1)其他方面的性能：空间的分配？。,20,2.3 栈栈的应用,表达式的计算：模拟表达式：12+5*(2+3)*6/2-4的求解过程。,例,操作数运算符各自依次入栈。,出栈规则：当前入栈的运算符比栈顶的运算符优先级低。,21,2.3 栈的应用,表达式的计算 以表达式12+5*(2+

11、3)*6/2-4的计算过程的实现为例来讨论栈结构在实现对任意输入的通用表达式的计算中的作用,#12+5*(2+3)*6/2-4#,开始时，指向第一个位置，准备读入，此时的两个栈均为空。,CurrentS=#,#12+5*(2+3)*6/2-4#,CurrentS=12,由于#是第一个算符，因而自动进栈。读到操作数（12）自动进栈。,12,#,22,2.3 栈的应用,栈顶算符#比当前运算符优先级低，故算符要入栈,#12+5*(2+3)*6/2-4#,#,12,+,#12+5*(2+3)*6/2-4#,CurrentS=,依次读入5、（、2和后，栈顶算符（比当前算符优先级低，故要入栈,+#,12,

12、CurrentS=,5,2,X,(,3,+,23,2.3 栈的应用,#12+5*(2+3)*6/2-4#,CurrentS=),(X+#,512,栈顶算符比当前运算符）优先级高，故要执行其运算2+3并入栈,#12+5*(2+3)*6/2-4#,CurrentS=),X+#,512,栈顶算符（与当前运算符）相对应，故要出栈，一同释放,32,+,5,(,24,2.3 栈的应用,#12+5*(2+3)*6/2-4#,CurrentS=X,+#,12,栈顶算符比当前运算符优先运算，故要执行运算5*5并入栈,#12+5*(2+3)*6/2-4#,CurrentS=X,+#,12,栈顶算符比当前运算符优先

13、级低，故要入栈,X,55,25,X,6,25,2.3 栈的应用,#12+5*(2+3)*6/2-4#,CurrentS=/,+#,12,栈顶算符比当前运算符/优先运算，故要执行运算25*6并入栈,#12+5*(2+3)*6/2-4#,CurrentS=-,+#,12,栈顶算符/比当前运算符优先级高，故要执行/运算150/2并入栈,X,625,/,150,2,#12+5*(2+3)*6/2-4#,CurrentS=-,#,12,栈顶算符比当前运算符优先，故执行运算12+75并入栈,75,+,26,2.3 栈的应用,#12+5*(2+3)*6/2-4#,CurrentS=#,#,87,栈顶算符比当

14、前运算符优先级高，故要执行运算87-4并入栈,#12+5*(2+3)*6/2-4#,CurrentS=#,#,83,栈顶算符与当前运算符相对应，故要一同释放，83出栈为最后结果,4,-,27,顺序栈本章习题(1),2.1 对一个栈的输入序列a1,a2,a3,an，称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。例如，假设栈S的一个输入序列为1,2,3,4,5，则可得到多个输出序列。例如，1,2,3,4,5就是一个合法的输出序列，同理，5,4,3,2,1和3,2,1,4,5也分别是其合法的输出序列。分别求解下列问题：（1）判断序列1,3,4,5,2是否是合法的输出序列。（2）对输入序列1,

15、2,3,4,5，求出其所有的合法的输出序列。（3*）设计算法以判断对输入序列1,2,3,n，序列a1,a2,a3,an是否是该栈的合法的输出序列（假设输出序列在数组A中）。2.2 如果顺序栈中的第二个分量是记录元素个数的变量而不是栈顶指针，应如何实现各算法？,28,顺序栈本章习题(2),2.3 对一个合法的数学表达式来说，其中的各大小括号“”，“”，“”，“”，“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S，判断其中的各括号是否是匹配的。2.4 对表达式5+3*(12+4)/4-8，依次画出在求解过程中的各步骤中的栈的状态。2.5*设计算法以求解所读入的表达式的值。假设数据类型为整型，并且仅包含加减乘除四则运算。2.6*设计算法以求解所读入的表达式的值。假设数据类型为浮点型，并且仅包含加减乘除四则运算。,29,结束,本章内容回顾谢谢,