数据结构栈学习教案.pptx

会计学1数据结构数据结构(sh j ji u)栈栈第一页，共30页。2第二章第二章 栈栈 第二章 栈（stack）2.1 栈的定义和运算(yn sun)2.2 顺序栈 2.3 栈的应用 第1页/共30页第二页，共30页。3第二章第二章 栈栈栈是软件设计中最基本栈是软件设计中最基本栈是软件设计中最基本栈是软件设计中最基本(jbn)(jbn)的数据结构，的数据结构，的数据结构，的数据结构，这是本课程所介绍的第一种数据结构。这是本课程所介绍的第一种数据结构。这是本课程所介绍的第一种数据结构。这是本课程所介绍的第一种数据结构。学习栈结构时，需要掌握哪些方面的内容？学习栈结构时，需要掌握哪些方面的内容？学习栈结构时，需要掌握哪些方面的内容？学习栈结构时，需要掌握哪些方面的内容？为此，回顾一下上一章所介绍的数据结构的组成部分。为此，回顾一下上一章所介绍的数据结构的组成部分。为此，回顾一下上一章所介绍的数据结构的组成部分。为此，回顾一下上一章所介绍的数据结构的组成部分。由此可知，对每一种结构的学习的组成部分。由此可知，对每一种结构的学习的组成部分。由此可知，对每一种结构的学习的组成部分。由此可知，对每一种结构的学习的组成部分。逻辑(lu j)结构分析(fnx)运算实现（算法）运算定义 存储结构数据结构的组成第2页/共30页第三页，共30页。42.1 2.1 栈的定义栈的定义栈的定义栈的定义(dngy)(dngy)和运算和运算和运算和运算栈的定义栈的定义栈的定义栈的定义栈是只能在一端插入和删除元素栈是只能在一端插入和删除元素栈是只能在一端插入和删除元素栈是只能在一端插入和删除元素(yun s)(yun s)的线性表。的线性表。的线性表。的线性表。术语：栈顶术语：栈顶术语：栈顶术语：栈顶,栈底栈底栈底栈底,入栈（压栈）入栈（压栈）入栈（压栈）入栈（压栈）,出栈（弹栈）出栈（弹栈）出栈（弹栈）出栈（弹栈）an an-1 a1入栈(PUSH)出栈(POP)栈顶(top)栈底(bottom)逻辑结构(jigu)和运算a1 a2 an 特性：后进先出(LIFO)-Last in First out a1a2anana2a1第3页/共30页第四页，共30页。52.1 栈的定义栈的定义(dngy)和运算和运算栈的运算栈的运算栈的运算栈的运算(yn sun)(yn sun)(yn sun)(yn sun)1.1.1.1.栈的基本运算栈的基本运算栈的基本运算栈的基本运算(yn sun)(yn sun)(yn sun)(yn sun)定义定义定义定义对栈的基本运算对栈的基本运算对栈的基本运算对栈的基本运算(yn sun)(yn sun)(yn sun)(yn sun)有如下几个：有如下几个：有如下几个：有如下几个：(1)(1)(1)(1)初始化初始化初始化初始化 ：设置栈为空。：设置栈为空。：设置栈为空。：设置栈为空。(2)(2)(2)(2)判断栈为空：判断栈为空：判断栈为空：判断栈为空：若为空，则返回若为空，则返回若为空，则返回若为空，则返回TRUETRUETRUETRUE，否则返回，否则返回，否则返回，否则返回FALSE.FALSE.FALSE.FALSE.(3)(3)(3)(3)判断栈为满：判断栈为满：判断栈为满：判断栈为满：若为满，则返回若为满，则返回若为满，则返回若为满，则返回TRUETRUETRUETRUE，否则返回，否则返回，否则返回，否则返回FALSE.FALSE.FALSE.FALSE.(4)(4)(4)(4)取栈顶元素：取出栈顶元素。取栈顶元素：取出栈顶元素。取栈顶元素：取出栈顶元素。取栈顶元素：取出栈顶元素。条件：栈不空。条件：栈不空。条件：栈不空。条件：栈不空。否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)(5)(5)入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？如果栈满，怎样处理？如果栈满，怎样处理？如果栈满，怎样处理？(6)(6)(6)(6)出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？如因为栈空而不能进行，应怎样处理？如因为栈空而不能进行，应怎样处理？如因为栈空而不能进行，应怎样处理？运算(yn sun)定义第4页/共30页第五页，共30页。6栈的运算栈的运算(yn sun)2.栈的运算的栈的运算的C+描述描述如何用如何用C+描述栈的内容和运算？描述栈的内容和运算？一种方法是：一种方法是：将栈的有关数据和运算封装在一起，将栈的有关数据和运算封装在一起，以以C+的类的形式来封装描述。的类的形式来封装描述。封装的数据和运算要便于被有关程序来调用。封装的数据和运算要便于被有关程序来调用。因此，栈的因此，栈的C+描述的框架描述的框架(kun ji)如下所如下所示：示：class stack ;运算描述(mio sh)部分数据描述部分类的名称类的框架第5页/共30页第六页，共30页。7栈的运算栈的运算(yn sun)n n下面下面下面下面(xi mian)(xi mian)讨论栈的运算的讨论栈的运算的讨论栈的运算的讨论栈的运算的C+C+描述的细节，先给出每一个运算的对应描述：描述的细节，先给出每一个运算的对应描述：描述的细节，先给出每一个运算的对应描述：描述的细节，先给出每一个运算的对应描述：n n初始化函数的描述初始化函数的描述初始化函数的描述初始化函数的描述栈的C+类描述(mio sh)：class stack stack();栈的数据成员;栈的运算(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？采用C+的构造函数第6页/共30页第七页，共30页。8栈的运算栈的运算(yn sun)n n判断函数判断函数(hnsh)的对应的对应栈的C+类描述：class stack stack();Bool empty()Bool full()栈的数据(shj)成员;栈的运算(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？判断为空的函数判断为满的函数const;const;第7页/共30页第八页，共30页。9栈的运算栈的运算(yn sun)n n其他几个函数的对应描述其他几个函数的对应描述其他几个函数的对应描述其他几个函数的对应描述n n分析：分析：分析：分析：n n（1 1）几个运算）几个运算）几个运算）几个运算(yn sun)(yn sun)的条件可能有不成立的情况，的条件可能有不成立的情况，的条件可能有不成立的情况，的条件可能有不成立的情况，n n 因此，需要给予明确的反映。因此，需要给予明确的反映。因此，需要给予明确的反映。因此，需要给予明确的反映。n n（2 2）设立运算）设立运算）设立运算）设立运算(yn sun)(yn sun)是否正常的类型是否正常的类型是否正常的类型是否正常的类型error_codeerror_code，n n正常时返回正常时返回正常时返回正常时返回success,success,n n否则返回错误类型，如否则返回错误类型，如否则返回错误类型，如否则返回错误类型，如overflow,underflowoverflow,underflow等。等。等。等。n n enum error_code success,overflow,underflow;enum error_code success,overflow,underflow;n n（3 3）可以将这几个函数的类型设置为）可以将这几个函数的类型设置为）可以将这几个函数的类型设置为）可以将这几个函数的类型设置为error_codeerror_code；n n（4 4）如果需要返回其他的值，可以作为参数来返回。）如果需要返回其他的值，可以作为参数来返回。）如果需要返回其他的值，可以作为参数来返回。）如果需要返回其他的值，可以作为参数来返回。第8页/共30页第九页，共30页。10栈的运算栈的运算(yn sun)由上述讨论可得到其他几个函数的功能描述(mio sh)：（4)取栈顶元素的运算功能描述(mio sh)：如果栈不空，则取出栈顶元素到参数x中，然后返回success。否则，返回downflow。对应的运算函数为：error_code get_top(elementtype&x)const;(5)入栈的运算功能描述(mio sh)：如果栈不满，则将元素入栈，并返回success。否则，返回overflow。对应的运算函数为：error_code push(const elementtype x);第9页/共30页第十页，共30页。11栈的运算栈的运算(yn sun)(6)(6)(6)(6)出栈的运算功能描述出栈的运算功能描述出栈的运算功能描述出栈的运算功能描述(mio sh)(mio sh)(mio sh)(mio sh)：如果栈不空，删除当前栈顶的元素，并返回如果栈不空，删除当前栈顶的元素，并返回如果栈不空，删除当前栈顶的元素，并返回如果栈不空，删除当前栈顶的元素，并返回successsuccesssuccesssuccess。否则，返回否则，返回否则，返回否则，返回underflowunderflowunderflowunderflow。对应的运算函数为：对应的运算函数为：对应的运算函数为：对应的运算函数为：error_code pop();error_code pop();error_code pop();error_code pop();第10页/共30页第十一页，共30页。12栈的运算栈的运算(yn sun)n n由此得到栈的类由此得到栈的类由此得到栈的类由此得到栈的类stackstack的函数成员列表如下：的函数成员列表如下：的函数成员列表如下：的函数成员列表如下：n nclass stackclass stackn n stack();/stack();/初始化初始化初始化初始化n n Bool empty()const;/Bool empty()const;/判断空判断空判断空判断空n n Bool full()const;/Bool full()const;/判断满判断满判断满判断满n n error_code get_top(elementtype&x)const;error_code get_top(elementtype&x)const;n n /取栈顶元素取栈顶元素取栈顶元素取栈顶元素n n error_code push(const elementtype x);/error_code push(const elementtype x);/入栈入栈入栈入栈n n error_code pop();/error_code pop();/出栈出栈出栈出栈n n 栈的数据成员栈的数据成员栈的数据成员栈的数据成员;n n;n n问题：上述类的描述问题：上述类的描述问题：上述类的描述问题：上述类的描述(mio sh)(mio sh)是否还需要补充什么？是否还需要补充什么？是否还需要补充什么？是否还需要补充什么？第11页/共30页第十二页，共30页。132.2 顺序顺序(shnx)栈栈n n存储结构：存储结构：存储结构：存储结构：n n假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）data,data,可用于存储栈的元素。可用于存储栈的元素。可用于存储栈的元素。可用于存储栈的元素。n n则可将栈中元素连续地存储到数组的各元素则可将栈中元素连续地存储到数组的各元素则可将栈中元素连续地存储到数组的各元素则可将栈中元素连续地存储到数组的各元素-顺序存储方式。顺序存储方式。顺序存储方式。顺序存储方式。n n如下图所示：如下图所示：如下图所示：如下图所示：n n其中：为了其中：为了其中：为了其中：为了(wi le)(wi le)能随时知道栈中的元素个数，设置了一个计数变量能随时知道栈中的元素个数，设置了一个计数变量能随时知道栈中的元素个数，设置了一个计数变量能随时知道栈中的元素个数，设置了一个计数变量countcount。n n将数组将数组将数组将数组datadata和和和和countcount作为类作为类作为类作为类stackstack的数据成员。的数据成员。的数据成员。的数据成员。栈的存储(cn ch)结构a1a2an01n-1maxlenndatacount顺序栈存储结构第12页/共30页第十三页，共30页。142.2 顺序顺序(shnx)栈栈n n由此而得到由此而得到由此而得到由此而得到(d do)(d do)类类类类stackstack的完整描述。的完整描述。的完整描述。的完整描述。n n封装类封装类封装类封装类:n n class stack class stackn n public:public:n n stack();stack();n n Bool empty()const;Bool empty()const;n n Bool full()const;Bool full()const;n n error_code get_top(elementtype&x)const;error_code get_top(elementtype&x)const;n n error_code push(const elementtype x);error_code push(const elementtype x);n n error_code pop();error_code pop();n n private:private:n n int count;int count;n n elementtype datamaxlen;elementtype datamaxlen;n n /定义其它成员定义其它成员定义其它成员定义其它成员n n;这是起什么(shn me)作用的？作用是什么？第13页/共30页第十四页，共30页。152.2 顺序顺序(shnx)栈栈n n运算实现：即类运算实现：即类运算实现：即类运算实现：即类classclass的各函数的各函数的各函数的各函数(hnsh)(hnsh)成员的具体实现。成员的具体实现。成员的具体实现。成员的具体实现。n n初始化函数初始化函数初始化函数初始化函数(hnsh)(hnsh)的实现：的实现：的实现：的实现：n n stack:stack()stack:stack()n n count=0;count=0;a1a2an01n-1maxlenndatacount第14页/共30页第十五页，共30页。162.2 顺序顺序(shnx)栈栈判断空的函数判断空的函数判断空的函数判断空的函数(hnsh)(hnsh)的实现：的实现：的实现：的实现：Bool stack:empty()const Bool stack:empty()const if(count=0)return TRUE;if(count=0)return TRUE;else return FALSE;else return FALSE;判断满的函数判断满的函数判断满的函数判断满的函数(hnsh)(hnsh)的实现：的实现：的实现：的实现：Bool stack:full()const Bool stack:full()const if(count=maxlen)return TRUE;if(count=maxlen)return TRUE;else return FALSE;else return FALSE;/等价于：等价于：等价于：等价于：return count=maxlen;return count=maxlen;a1a2an01n-1maxlenndatacount第15页/共30页第十六页，共30页。172.2 顺序顺序(shnx)栈栈取栈顶元素取栈顶元素取栈顶元素取栈顶元素(yun s)(yun s)的实现：的实现：的实现：的实现：error_code stack:get_top(elementtype&x)const error_code stack:get_top(elementtype&x)const if(empty()return underflow;if(empty()return underflow;else else x=datacount-1;x=datacount-1;return success;return success;a1a2an01n-1maxlenndatacount第16页/共30页第十七页，共30页。182.2 顺序顺序(shnx)栈栈入栈的实现入栈的实现入栈的实现入栈的实现(shxin)(shxin)：error_code stack:push(const elementtype x)error_code stack:push(const elementtype x)if(full()return overflow;if(full()return overflow;datacount=x;datacount=x;count+;count+;return success;return success;a1a2an01n-1maxlenndatacount第17页/共30页第十八页，共30页。192.2 顺序顺序(shnx)栈栈出栈的实现出栈的实现出栈的实现出栈的实现 error_code stack:pop()error_code stack:pop()if(empty()return underflow;if(empty()return underflow;count-;count-;return success;return success;算法分析：时间性能算法分析：时间性能算法分析：时间性能算法分析：时间性能 全部是全部是全部是全部是O(1)O(1)其他方面的性能：空间的分配？。其他方面的性能：空间的分配？。其他方面的性能：空间的分配？。其他方面的性能：空间的分配？。特点分析：任意特点分析：任意特点分析：任意特点分析：任意(rny)(rny)位置可访问性，容量的确定位置可访问性，容量的确定位置可访问性，容量的确定位置可访问性，容量的确定a1a2an01n-1maxlenndatacount第18页/共30页第十九页，共30页。202.3 栈的应用栈的应用(yngyng)表达式的计算表达式的计算n n算法描述n n1）输入表达式n n2）从左向右读入每个符号n n 如果(rgu)是数字，则转换成数值型，压入数字栈；n n 否则，判断当前操作符与栈顶操作符优先级n n 如果(rgu):操作符入栈n n 否则：n n 数字栈出栈2次，与当前操作符运算n n 结果压入数字栈；n n 转向2）第19页/共30页第二十页，共30页。212.3 栈的应用栈的应用(yngyng)n n表达式的计算表达式的计算表达式的计算表达式的计算n n 以表达式以表达式以表达式以表达式12+5*(2+3)*6/2-412+5*(2+3)*6/2-4的计算过程的实现为例来讨论栈结构在的计算过程的实现为例来讨论栈结构在的计算过程的实现为例来讨论栈结构在的计算过程的实现为例来讨论栈结构在n n实现对任意输入的通用实现对任意输入的通用实现对任意输入的通用实现对任意输入的通用(tngyng)(tngyng)表达式的计算中的作用表达式的计算中的作用表达式的计算中的作用表达式的计算中的作用#12+5*(2+3)*6/2-4#开始时，指向第一个位置，准备(zhnbi)读入，此时的两个栈均为空。CurrentS=#12+5*(2+3)*6/2-4#CurrentS=12 由于#是第一个算符，因而自动进栈。读到操作数（12）自动进栈。12#第20页/共30页第二十一页，共30页。222.3 栈的应用栈的应用(yngyng)栈顶算符#比当前(dngqin)运算符优先级低，故算符要入栈#12+5*(2+3)*6/2-4#12+#12+5*(2+3)*6/2-4#CurrentS=依次(yc)读入5、（、2和后，栈顶算符（比当前算符优先级低，故要入栈+#12CurrentS=52X(3+第21页/共30页第二十二页，共30页。232.3 栈的应用栈的应用(yngyng)#12+5*(2+3)*6/2-4#CurrentS=)(X+#512栈顶算符比当前(dngqin)运算符）优先级高，故要执行其运算 2+3并入栈#12+5*(2+3)*6/2-4#CurrentS=)X+#512栈顶算符（与当前运算符）相对应，故要出栈，一同(ytng)释放32+5(第22页/共30页第二十三页，共30页。242.3 栈的应用栈的应用(yngyng)#12+5*(2+3)*6/2-4#CurrentS=X+#12栈顶算符比当前运算(yn sun)符优先运算(yn sun)，故要执行运算(yn sun)5*5并入栈#12+5*(2+3)*6/2-4#CurrentS=X +#12栈顶算符比当前(dngqin)运算符优先级低，故要入栈X5525X6第23页/共30页第二十四页，共30页。252.3 栈的应用栈的应用(yngyng)#12+5*(2+3)*6/2-4#CurrentS=/+#12栈顶算符比当前运算符/优先运算，故要执行(zhxng)运算25*6并入栈#12+5*(2+3)*6/2-4#CurrentS=-+#12栈顶算符/比当前运算(yn sun)符优先级高，故要执行/运算(yn sun)150/2并入栈X625/1502#12+5*(2+3)*6/2-4#CurrentS=-#12栈顶算符比当前运算符优先，故执行运算12+75并入栈75+第24页/共30页第二十五页，共30页。262.3 栈的应用栈的应用(yngyng)#12+5*(2+3)*6/2-4#CurrentS=#87栈顶算符比当前运算符优先级高，故要执行(zhxng)运算87-4并入栈#12+5*(2+3)*6/2-4#CurrentS=#83栈顶算符与当前运算符相对(xingdu)应，故要一同释放，83出栈为最后结果4-第25页/共30页第二十六页，共30页。272.3 栈的应用栈的应用(yngyng)n n几个问题n n实现：n n2个栈n n输入扫描（数字和运算符的识别(shbi)）n n运算符优先级的描述n n延伸：n n多位数的读入n n小数，负数的读入n n其他运算符如开方，sin，cos等n n括号，多重括号第26页/共30页第二十七页，共30页。28顺序顺序(shnx)栈栈本本章习题章习题(1)n n2.1 2.1 对一个栈的输入序列对一个栈的输入序列a1,a2,a3,ana1,a2,a3,an，称由此栈依次出栈，称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。例如，假设栈后所得到的元素序列为栈的合法输出序列。例如，假设栈S S的一个输入序列为的一个输入序列为1,2,3,4,51,2,3,4,5，则可得到多个输出序列。例，则可得到多个输出序列。例如，如，1,2,3,4,51,2,3,4,5就是一个合法的输出序列，同理，就是一个合法的输出序列，同理，5,4,3,2,15,4,3,2,1和和3,2,1,4,53,2,1,4,5也分别是其合法的输出序列。分别求解下列问题：也分别是其合法的输出序列。分别求解下列问题：n n（1 1）判断序列）判断序列1,3,4,5,21,3,4,5,2是否是合法的输出序列。是否是合法的输出序列。n n（2 2）对输入序列）对输入序列1,2,3,4,51,2,3,4,5，求出其所有的合法的输出序列。，求出其所有的合法的输出序列。n n（3*3*）设计算法以判断对输入序列）设计算法以判断对输入序列1,2,3,n1,2,3,n，序列，序列a1,a2,a1,a2,a3,ana3,an是否是该栈的合法的输出序列（假设输出序列在是否是该栈的合法的输出序列（假设输出序列在数组数组A A中）。中）。n n2.2 2.2 如果顺序栈中的第二个分量是记录如果顺序栈中的第二个分量是记录(jl)(jl)元素个数的变量元素个数的变量而不是栈顶指针，应如何实现各算法？而不是栈顶指针，应如何实现各算法？第27页/共30页第二十八页，共30页。29顺序顺序(shnx)栈栈本本章习题章习题(2)n n2.3 2.3 对一个合法的数学对一个合法的数学(shxu)(shxu)表达式来说，其中的各大小括号表达式来说，其中的各大小括号“”，“”“”，“”“”，“”“”，“(”“(”和和“)”“)”应是相互匹配的。设计算法对以字应是相互匹配的。设计算法对以字符串形式读入的表达式符串形式读入的表达式S S，判断其中的各括号是否是匹配的。，判断其中的各括号是否是匹配的。n n2.4 2.4 对表达式对表达式5+3*(12+4)/4-85+3*(12+4)/4-8，依次画出在求解过程中的各步骤，依次画出在求解过程中的各步骤中的栈的状态。中的栈的状态。n n2.5 *2.5 *设计算法以求解所读入的表达式的值。假设数据类型为整设计算法以求解所读入的表达式的值。假设数据类型为整型，并且仅包含加减乘除四则运算。型，并且仅包含加减乘除四则运算。n n2.6 *2.6 *设计算法以求解所读入的表达式的值。假设数据类型为浮设计算法以求解所读入的表达式的值。假设数据类型为浮点型，并且仅包含加减乘除四则运算。点型，并且仅包含加减乘除四则运算。第28页/共30页第二十九页，共30页。30结束结束(jish)n n本章内容(nirng)回顾n n谢谢第29页/共30页第三十页，共30页。