栈的性质、栈的基本操作ppt课件

1、第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构首页首页第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构教学主题教学主题栈的性质、栈的根本操作栈的性质、栈的根本操作教学目的教学目的 经过本次课的学习，使学生掌握栈的概念、经过本次课的学习，使学生掌握栈的概念、栈的存储方式、顺序栈的实现。栈的存储方式、顺序栈的实现。教学重点教学重点 栈的顺序存储方式栈的顺序存储方式 顺序栈的根本操作顺序栈的根本操作教学难点教学难点 顺序栈的实现顺序栈的实现教案教案第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作

2、C语言与数据结构主要内容主要内容 栈的概念栈的概念 栈的根本操作栈的根本操作 栈的存储栈的存储 顺序栈的实现顺序栈的实现第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构引例引例 在日常生活中，有一些这样的例子。在日常生活中，有一些这样的例子。 例例1：食堂师傅把洗好的饭盒按顺序放好，最后洗的饭盒：食堂师傅把洗好的饭盒按顺序放好，最后洗的饭盒总是放在一叠饭盒的最上面。同窗们到食堂就餐时，拿饭盒总是放在一叠饭盒的最上面。同窗们到食堂就餐时，拿饭盒总是按照由上到下的顺序拿，即总是拿一叠饭盒中最顶上的总是按照由上到下的顺序拿，即总是拿一叠饭盒中最顶上的一个。一个

3、。 例例2：有一个盒子，我们在里头放了一叠书。当我们要用：有一个盒子，我们在里头放了一叠书。当我们要用书的时候，只能从第一本开场拿；当我们要把书本放进去时，书的时候，只能从第一本开场拿；当我们要把书本放进去时，总是放在最上面。总是放在最上面。 请问：上面的例子中有什么共同的特点？请问：上面的例子中有什么共同的特点？后放进去的，先拿出来。后放进去的，先拿出来。第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构栈的概念和特点栈的概念和特点 什么是栈？什么是栈？ 栈是一种特殊的线性表，它只在线性表的一端栈是一种特殊的线性表，它只在线性表的一端进展插入和删除操作。

4、进展插入和删除操作。 栈中允许插入、删除的这一端称为栈顶，另一栈中允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。个固定端称为栈底。 当表中没有元素时称为空栈。当表中没有元素时称为空栈。 栈的特点栈的特点 “先进后出先进后出First In Last Out 或或“后进先出后进先出Last In First Out第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构栈的根本操作栈的根本操作 栈主要有建栈、入栈、出栈和销毁栈四个根本操栈主要有建栈、入栈、出栈和销毁栈四个根本操作。作。 建栈：新建一个空栈，向操作系统恳求一组存建栈：新建一个空栈，向操作系统

5、恳求一组存储单元，用于存储栈中的元素。储单元，用于存储栈中的元素。 入栈：将元素压入栈内，存储在栈顶。入栈：将元素压入栈内，存储在栈顶。 出栈：从栈中取出栈顶元素，也称为弹出栈。出栈：从栈中取出栈顶元素，也称为弹出栈。 销毁栈：把存储单元归还给操作系统。销毁栈：把存储单元归还给操作系统。 为了实时了解栈的情况，还需求有输出栈这样的为了实时了解栈的情况，还需求有输出栈这样的操作。操作。 输出栈：显示栈的内容。输出栈：显示栈的内容。第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构栈的存储栈的存储 回想：前面引见的线性表是采用什么方式存储数据的？回想：前面引见

6、的线性表是采用什么方式存储数据的？ 栈与前面引见过的线性表一样，也可以采用顺序存储构造栈与前面引见过的线性表一样，也可以采用顺序存储构造数组或者链式存储构造链表。数组或者链式存储构造链表。顺序栈顺序栈链栈单链表链栈单链表 栈的表示栈的表示 可以用一个栈顶指针可以用一个栈顶指针toptop来指示栈顶元素存放的位置，来指示栈顶元素存放的位置，用一个栈底指针用一个栈底指针bottombottom来指示栈底元素的存放位置。由来指示栈底元素的存放位置。由于栈底位置相对不变，通常不用于栈底位置相对不变，通常不用bottombottom。第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操

7、作C语言与数据结构顺序栈的表示图顺序栈的表示图第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构链栈的表示图链栈的表示图(1) 初始： top=NULL (2) a1入栈后： (3) a2、a3入栈后： (4) 一个元素出栈： top a1 top a3 a2 a1 top a2 a1 第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构顺序栈的实现顺序栈的实现【例】先建栈，然后输入一个整型元素后入栈，显示栈的内【例】先建栈，然后输入一个整型元素后入栈，显示栈的内容。接下来进展出栈操作，再显示栈的内容。最后销毁栈。容。接

8、下来进展出栈操作，再显示栈的内容。最后销毁栈。 数据构造描画数据构造描画顺序栈的类型描画如下：顺序栈的类型描画如下：#define MAXSIZE 200 #define MAXSIZE 200 struct seqstackstruct seqstack Elemtype dataMAXSIZE; Elemtype dataMAXSIZE; int top; int top;定义一个指向顺序栈的指针：定义一个指向顺序栈的指针：struct seqstack struct seqstack * *s;s; 源程序源程序运转运转程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次

9、课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构建栈建栈 分析分析 首先恳求栈空间，然后初始化栈顶指针。首先恳求栈空间，然后初始化栈顶指针。 流程图流程图 源程序源程序运转运转程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构入栈入栈 流程图流程图 源程序源程序int push_seqstack (struct seqstack int push_seqstack (struct seqstack * *s, Elemtype x)s, Elemtype x) s-datas-top=x;

10、 s-datas-top=x; s-top+; s-top+; return 1; return 1; 思索：假设不断入栈，思索：假设不断入栈，会出现什么情况？会出现什么情况？(10_2)(10_2)上溢出上溢出第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构检查栈能否满的子函数检查栈能否满的子函数 源程序源程序/*/* 函函 数数 名：名：full_seqstack */* 函数功能：检查栈能否满函数功能：检查栈能否满 */* 入口参数：入口参数：s栈栈 */* 返返 回回 值：栈满前往值：栈满前往1，否那么前往，否那么前往0 */*/int full

11、_seqstack(struct seqstack *s) if (s-top = MAXSIZE) return 1; else return 0;第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构改良后的入栈改良后的入栈 分析分析 为了防止上溢发生，在入栈前先检查栈能否满。假设未为了防止上溢发生，在入栈前先检查栈能否满。假设未满，那么进展入栈操作，否那么进展溢栈处置或溢栈报告。满，那么进展入栈操作，否那么进展溢栈处置或溢栈报告。 流程图流程图 源程序源程序运转运转程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次课次课-栈的性质、栈的

12、基本操作栈的性质、栈的基本操作C语言与数据结构出栈出栈 流程图流程图 源程序源程序int pop_seqstack (struct seqstack int pop_seqstack (struct seqstack * *s, Elemtype s, Elemtype * *x)x) s-top-; s-top-; * *x=s-datas-top;x=s-datas-top; return 1; return 1; 思索：假设不断出栈，思索：假设不断出栈，会出现什么情况？会出现什么情况？(10_2)(10_2)下溢出下溢出第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本

13、操作C语言与数据结构检查栈能否为空的子函数检查栈能否为空的子函数 源程序源程序 /*/ /* 函函 数数 名：名：empty_seqstack */ /* 函数功能：检查栈能否为空函数功能：检查栈能否为空 */ /* 入口参数：入口参数：s栈栈 */ /* 返返 回回 值：栈空前往值：栈空前往1，否那么前往，否那么前往0 */ /*/ int empty_seqstack(struct seqstack *s) if (s-top = 0) return 1; else return 0; 第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构改良后的出栈改良

14、后的出栈 分析分析 为了防止下溢发生，在出栈前先检查栈能否为空。假设为了防止下溢发生，在出栈前先检查栈能否为空。假设不空，那么进展出栈操作，否那么进展溢栈处置或溢栈报告。不空，那么进展出栈操作，否那么进展溢栈处置或溢栈报告。 流程图流程图 源程序源程序运转运转程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构显示栈显示栈 源程序源程序 void display_seqstack(struct seqstack *s) int i; if (empty_seqstack(s) printf(目前栈为空目前栈为空

15、!n); return; printf(目前栈的内容为：目前栈的内容为：); for (i=0; itop-1;i+) printf(%d ,s-datai); printf(n); 第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构销毁栈销毁栈 分析分析 只需释放建栈时所恳求的空间即可。只需释放建栈时所恳求的空间即可。 源程序源程序 /*/ /* 函函 数数 名：名：destroy_seqstack */ /* 函数功能：销毁栈函数功能：销毁栈 */ /* 入口参数：入口参数：s栈栈 */ /* 返返 回回 值：无值：无 */ /*/ void dest

16、roy_seqstack(struct seqstack *s) free(s); 第第8章章第第10次课次课-栈的性质、栈的基本操作栈的性质、栈的基本操作C语言与数据结构去除栈去除栈 有的情况下只需求去除栈，而不销毁栈。有的情况下只需求去除栈，而不销毁栈。 去除栈：只是将栈内元素清空，栈的存储空间仍保管。去除栈：只是将栈内元素清空，栈的存储空间仍保管。 去除栈的源程序去除栈的源程序 /*/ /* 函函 数数 名：名：clear_seqstack */ /* 函数功能：去除栈函数功能：去除栈 */ /* 入口参数：入口参数：s栈栈 */ /* 返返 回回 值：无值：无 */ /*/ void clear_seqstack(struct seqstack *s) s-top=0; 运转运转程序程序(10_