次课-栈的性质、栈的基本操作.ppt

《次课-栈的性质、栈的基本操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首页遇到困难时,请发挥集体的智慧!有所收获教学主题栈的性质、栈的基本操作教学目标通过本次课的学习，使学生掌握栈的概念、栈的存储方式、顺序栈的实现。教学重点１．栈的顺序存储方式　２．顺序栈的基本操作教学难点顺序栈的实现教案主要内容栈的概念栈的基本操作栈的存储顺序栈的实现引例在日常生活中，有一些这样的例子。例1：食堂师傅把洗好的饭盒按顺序放好，最后洗的饭盒总是放在一叠饭盒的最上面。同学们到食堂就餐时，拿饭盒总是按照由上到下的顺序拿，即总是拿一叠饭盒中最顶上的一个。例2：有一个盒子，我们在里头放了一叠书。当我们要用书的时候，只能从第一

2、本开始拿；当我们要把书本放进去时，总是放在最上面。请问：上面的例子中有什么共同的特点？后放进去的，先拿出来。栈的概念和特点什么是栈？栈是一种特殊的线性表，它只在线性表的一端进行插入和删除操作。栈中允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈的特点“先进后出”（FirstInLastOut）或“后进先出”（LastInFirstOut）返回栈的基本操作栈主要有建栈、入栈、出栈和销毁栈四个基本操作。建栈：新建一个空栈，向操作系统申请一组存储单元，用于存储栈中的元素。入栈：将元素压入栈内，存储在栈顶

3、。出栈：从栈中取出栈顶元素，也称为弹出栈。销毁栈：把存储单元归还给操作系统。为了实时了解栈的情况，还需要有输出栈这样的操作。输出栈：显示栈的内容。返回栈的存储回顾：前面介绍的线性表是采用什么方式存储数据的？栈与前面介绍过的线性表一样，也可以采用顺序存储结构（数组）或者链式存储结构（链表）。顺序栈链栈（单链表）栈的表示可以用一个栈顶指针（top）来指示栈顶元素存放的位置，用一个栈底指针（bottom）来指示栈底元素的存放位置。由于栈底位置相对不变，通常不用bottom。顺序栈的示意图链栈的示意图返回顺序栈的实现【例】先建栈，然后输入

4、一个整型元素后入栈，显示栈的内容。接下来进行出栈操作，再显示栈的内容。最后销毁栈。数据结构描述顺序栈的类型描述如下：#defineMAXSIZE200structseqstack{Elemtypedata[MAXSIZE];inttop;};定义一个指向顺序栈的指针：structseqstack*s;源程序运行程序(10_1)看源程序(10_1)建栈分析首先申请栈空间，然后初始化栈顶指针。流程图源程序运行程序(10_1)看源程序(10_1)入栈流程图源程序intpush_seqstack(structseqstack*s,Elem

5、typex){s->data[s->top]=x;s->top++;return1;}思考：如果不断入栈，会出现什么情况？(10_2)上溢出检查栈是否满的子函数源程序/*******************************************************//*函数名：full_seqstack*//*函数功能：检查栈是否满*//*入口参数：s——栈*//*返回值：栈满返回1，否则返回0*//******************************************************/intf

6、ull_seqstack(structseqstack*s){if(s->top==MAXSIZE)return1;elsereturn0;}改进后的入栈分析为了防止上溢发生，在入栈前先检查栈是否满。若未满，则进行入栈操作，否则进行溢栈处理或溢栈报告。流程图源程序运行程序(10_1)看源程序(10_1)出栈流程图源程序intpop_seqstack(structseqstack*s,Elemtype*x){s->top--;*x=s->data[s->top];return1;}思考：如果不断出栈，会出现什么情况？(10_2)下溢

7、出检查栈是否为空的子函数源程序/*******************************************//*函数名：empty_seqstack*//*函数功能：检查栈是否为空*//*入口参数：s——栈*//*返回值：栈空返回1，否则返回0*//*******************************************/intempty_seqstack(structseqstack*s){if(s->top==0)return1;elsereturn0;}改进后的出栈分析为了防止下溢发生，在出栈前先检

8、查栈是否为空。若不空，则进行出栈操作，否则进行溢栈处理或溢栈报告。流程图源程序运行程序(10_1)看源程序(10_1)显示栈源程序voiddisplay_seqstack(structseqstack*s){inti;if(empty_seqsta