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

首页 教案 主要内容 引例 栈的概念和特点 栈的基本操作 栈的存储 顺序栈的示意图 链栈的示意图 顺序栈的实现 建栈 入栈 检查栈是否满的子函数 改进后的入栈 出栈 检查栈是否为空的子函数 改进后的出栈 显示栈 销毁栈 清除栈 本次课总结 下课 《C语言与数据结构》 第6次课-----循环结构 * 第8章 第10次课----栈的性质、栈的基本操作 《C语言与数据结构》 １．栈的顺序存储方式　 ２．顺序栈的基本操作 教学重点 顺序栈的实现 教学难点 通过本次课的学习，使学生掌握栈的概念、栈的存储方式、顺序栈的实现。 教学目标 栈的性质、栈的基本操作 教学主题 栈的概念 栈的基本操作 栈的存储 顺序栈的实现 在日常生活中，有一些这样的例子。 例1：食堂师傅把洗好的饭盒按顺序放好，最后洗的饭盒总是放在一叠饭盒的最上面。同学们到食堂就餐时，拿饭盒总是按照由上到下的顺序拿，即总是拿一叠饭盒中最顶上的一个。 例2：有一个盒子，我们在里头放了一叠书。当我们要用书的时候，只能从第一本开始拿；当我们要把书本放进去时，总是放在最上面。 请问：上面的例子中有什么共同的特点？ 后放进去的，先拿出来。 什么是栈？ 栈是一种特殊的线性表，它只在线性表的一端进行插入和删除操作。 栈中允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。 当表中没有元素时称为空栈。 栈的特点 “先进后出”（First In Last Out） 或“后进先出”（Last In First Out） 栈主要有建栈、入栈、出栈和销毁栈四个基本操作。 建栈：新建一个空栈，向操作系统申请一组存储单元，用于存储栈中的元素。 入栈：将元素压入栈内，存储在栈顶。 出栈：从栈中取出栈顶元素，也称为弹出栈。 销毁栈：把存储单元归还给操作系统。 为了实时了解栈的情况，还需要有输出栈这样的操作。 输出栈：显示栈的内容。 回顾：前面介绍的线性表是采用什么方式存储数据的？ 栈与前面介绍过的线性表一样，也可以采用顺序存储结构（数组）或者链式存储结构（链表）。 顺序栈 链栈（单链表） 栈的表示 可以用一个栈顶指针（top）来指示栈顶元素存放的位置，用一个栈底指针（bottom）来指示栈底元素的存放位置。由于栈底位置相对不变，通常不用bottom。 【例】先建栈，然后输入一个整型元素后入栈，显示栈的内容。接下来进行出栈操作，再显示栈的内容。最后销毁栈。 数据结构描述 顺序栈的类型描述如下： #define MAXSIZE 200 struct seqstack { Elemtype data[MAXSIZE]; int top; }; 定义一个指向顺序栈的指针： struct seqstack *s; 源程序 运行程序(10_1) 看源程序(10_1) 分析 首先申请栈空间，然后初始化栈顶指针。 流程图 源程序 运行程序(10_1) 看源程序(10_1) 流程图 源程序 int push_seqstack (struct seqstack *s, Elemtype x) { s-data[s-top]=x; s-top++; return 1; } 思考：如果不断入栈，会出现什么情况？(10_2) 上溢出 源程序 /*******************************************************/ /* 函 数 名：full_seqstack */ /* 函数功能：检查栈是否满 */ /* 入口参数：s——栈 */ /* 返 回 值：栈满返回1，否则返回0 */ /******************************************************/ int full_seqstack(struct seqstack *s) { if (s-top == MAXSIZE) return 1; else return 0; } 分析 为了防止上溢发生，在入栈前先检查栈是否满。若未满，则进行入栈操作，否则进行溢栈处理或溢栈报告。 流程图 源程序 运行程序(10_1) 看源程序(10_1) 流程图 源程序 int pop_seqstack (struct