合工大数据结构02栈ppt课件.ppt
《合工大数据结构02栈ppt课件.ppt》由会员分享,可在线阅读,更多相关《合工大数据结构02栈ppt课件.ppt(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1数数 据据 结结 构构(第二章第二章 栈栈) Data Structures张晶张晶计算机与信息学院计算机与信息学院 2022-8-82022-8-82第二章第二章 栈栈 第二章第二章 栈(栈(stack) 2.1 栈的定义和运算 2.2 顺序栈 2.3 栈的应用 3第二章第二章 栈栈栈栈是软件设计中最基本的数据结构,是软件设计中最基本的数据结构,这是本课程所介绍的第一种数据结构。这是本课程所介绍的第一种数据结构。学习栈结构时,需要掌握哪些方面的内容?学习栈结构时,需要掌握哪些方面的内容?为此,回顾一下上一章所介绍的数据结构的组成部分。为此,回顾一下上一章所介绍的数据结构的组成部分。由此可知
2、,对每一种结构的学习的组成部分。由此可知,对每一种结构的学习的组成部分。逻辑结构逻辑结构分析分析 运算实现(算法)运算实现(算法) 运算定义运算定义 存储结构存储结构数据结构的组成数据结构的组成42.1 栈的定义和运算2.1.1 栈的定义栈的定义o栈栈是只能在一端插入和删除元素的线性表。是只能在一端插入和删除元素的线性表。 术语术语:栈顶栈顶, 栈底栈底, 入栈(压栈)入栈(压栈), 出栈(弹栈)出栈(弹栈) an an-1 a1入栈(PUSH) 出栈(POP) 栈顶(top)栈底(bottom)逻辑结构和运算逻辑结构和运算a1 a2 an 特性:后进先出特性:后进先出 ( LIFO )-La
3、st in First out a1a2anana2a152.1 栈的定义和运算2.1.2 2.1.2 栈的运算栈的运算o 1.1.栈的基本运算定义栈的基本运算定义对栈的基本运算有如下几个:对栈的基本运算有如下几个:(1)(1)初始化初始化 :设置栈为空。:设置栈为空。 (2)(2)判断判断栈为栈为空空: 若为空,则返回若为空,则返回TRUETRUE,否则返回,否则返回FALSE. FALSE. (3)(3)判断判断栈为栈为满满: 若为满,则返回若为满,则返回TRUETRUE,否则返回,否则返回FALSE. FALSE. (4)(4)取取栈顶栈顶元素:元素:取出栈顶元素。取出栈顶元素。 条件:
4、栈不空。条件:栈不空。 否则,应能明确给出标识,以便程序的处理。否则,应能明确给出标识,以便程序的处理。(5)(5)入栈入栈:将元素入栈,即放到栈顶。:将元素入栈,即放到栈顶。 如果栈满,怎样处理?如果栈满,怎样处理? (6)(6)出栈出栈:删除当前栈顶的元素。:删除当前栈顶的元素。 如因为栈空而不能进行,如因为栈空而不能进行,应怎样处理?应怎样处理? 运算定义运算定义62.1.2 栈的运算2. 栈的运算的栈的运算的C+描述描述o 如何用如何用C+描述栈的内容和运算?描述栈的内容和运算?一种方法是:一种方法是:n将栈的有关将栈的有关数据数据和和运算运算封装在一起,封装在一起,n以以C+的的类类
5、的形式来的形式来封装封装描述。描述。n封装的数据和运算要便于被有关程序来调用。封装的数据和运算要便于被有关程序来调用。o 因此,栈的因此,栈的C+描述的框架如下所示: class stack ;运算描述部分运算描述部分数据描述部分数据描述部分类的名称类的名称类的框架类的框架72.1.2 栈的运算o下面讨论栈的运算的下面讨论栈的运算的C+描述的细节,先给出每一个运算的对应描述:描述的细节,先给出每一个运算的对应描述:n初始化函数的描述初始化函数的描述栈的栈的C+类描述:类描述: class stack stack(); 栈的数据成员 ;栈的运算栈的运算(1)(1)初始化初始化 :设置栈为空:设置
6、栈为空。 (2)(2)判断栈为空:判断栈为空: 若为空,则返回若为空,则返回TRUETRUE,否则返回,否则返回FALSE. FALSE. (3)(3)判断栈为满:判断栈为满: 若为满,则返回若为满,则返回TRUETRUE,否则返回,否则返回FALSE. FALSE. (4)(4)取栈顶元素:取出栈顶元素。取栈顶元素:取出栈顶元素。 条件:栈不空。条件:栈不空。 否则,应能明确给出标识,以便程序的处理。否则,应能明确给出标识,以便程序的处理。(5)(5)入栈:将元素入栈,即放到栈顶。入栈:将元素入栈,即放到栈顶。 如果栈满,怎样处理?如果栈满,怎样处理? (6)(6)出栈:删除当前栈顶的元素。
7、出栈:删除当前栈顶的元素。 如因为栈空而不能进行,应怎样处理?如因为栈空而不能进行,应怎样处理? 采用采用C+的的构造函数构造函数82.1.2 栈的运算o 判断函数的对应判断函数的对应栈的栈的C+类描述:类描述:class stack stack(); Bool empty() Bool full() 栈的数据成员栈的数据成员;栈的运算栈的运算(1)(1)初始化初始化 :设置栈为空。:设置栈为空。 (2)(2)判断栈为空:判断栈为空: 若为空,则返回若为空,则返回TRUETRUE,否则返回,否则返回FALSE. FALSE. (3)(3)判断栈为满:判断栈为满: 若为满,则返回若为满,则返回T
8、RUETRUE,否则返回,否则返回FALSE. FALSE. (4)(4)取栈顶元素:取出栈顶元素。取栈顶元素:取出栈顶元素。 条件:栈不空。条件:栈不空。 否则,应能明确给出标识,以便程序的处理。否则,应能明确给出标识,以便程序的处理。(5)(5)入栈:将元素入栈,即放到栈顶。入栈:将元素入栈,即放到栈顶。 如果栈满,怎样处理?如果栈满,怎样处理? (6)(6)出栈:删除当前栈顶的元素。出栈:删除当前栈顶的元素。 如因为栈空而不能进行,应怎样处理?如因为栈空而不能进行,应怎样处理?判断为空的函数判断为空的函数判断为满的函数判断为满的函数const;const;92.1.2 栈的运算o 其他几
9、个函数的对应描述其他几个函数的对应描述分析分析:(1)几个运算的条件可能有不成立的情况,)几个运算的条件可能有不成立的情况, 因此,需要给予明确的反映。因此,需要给予明确的反映。(2)设立运算是否正常的类型)设立运算是否正常的类型error_code,正常时返回正常时返回success,否则返回错误类型,如否则返回错误类型,如overflow, underflow等。等。 enum error_code success, overflow, underflow;(3)可以将这几个函数的类型设置为)可以将这几个函数的类型设置为error_code;(4)如果需要返回其他的值,可以作为参数来返回。
10、)如果需要返回其他的值,可以作为参数来返回。102.1.2 栈的运算由上述讨论可得到由上述讨论可得到其他几个函数其他几个函数的功能描述:的功能描述:(4)4)取栈顶元素取栈顶元素的运算功能描述:的运算功能描述: 如果栈不空,则取出栈顶元素到参数如果栈不空,则取出栈顶元素到参数x x中,然后返回中,然后返回successsuccess。 否则,返回否则,返回downflowdownflow。 对应的运算函数为:对应的运算函数为: error_code get_top(elementtype &x) const;(5)(5)入栈入栈的运算功能描述:的运算功能描述: 如果栈不满,则将元素入栈,并返回
11、如果栈不满,则将元素入栈,并返回successsuccess。 否则,返回否则,返回overflowoverflow。 对应的运算函数为:对应的运算函数为: error_code push(const elementtype x); 112.1.2 栈的运算(6)(6)出栈出栈的运算功能描述:的运算功能描述: 如果栈不空,删除当前栈顶的元素,并返回如果栈不空,删除当前栈顶的元素,并返回successsuccess。 否则,返回否则,返回underflowunderflow。 对应的运算函数为:对应的运算函数为: error_code pop();122.1.2 栈的运算o 由此得到栈的类由此得
12、到栈的类stack的函数成员列表如下:的函数成员列表如下:class stack stack(); / 初始化初始化 Bool empty( ) const; / 判断空判断空 Bool full( ) const; / 判断满判断满 error_code get_top(elementtype &x) const; / 取栈顶元素取栈顶元素 error_code push(const elementtype x); /入栈入栈 error_code pop(); / 出栈出栈 栈的数据成员栈的数据成员;问题:上述类的描述是否还需要补充什么?问题:上述类的描述是否还需要补充什么?132.2 顺
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 合工大 数据结构 02 ppt 课件
限制150内