《数据结构》课程教学资源（教案设计）03 顺序栈

编号：004 课程 章节 数据结构 第三章栈和队列 课程讲 名称 名称 31栈 45分钟 授学时 学习要求 知识点 熟练 识记理解 分析 掌握 应用 综合 课堂 栈的基本操作算法和复杂性分析 √ √ 教学 顺序栈及实现 态度积极主动学习 目的 熟练掌握栈这两种抽象数据类型的特点，并能在应用问题中正确选择 能力 使用哪种数据结构： 熟练掌握栈这两种结构的顺序表示和链式表示，会应用它们的基本操 作算法，学会分析算法的时间复杂性和空间夏杂性； 教学内容（教学过程设计) 教学安排 复习与新课导入 5分钟 复习：线性表的插入和删除操作 提出向题：1、什么是线性结构？ 2、你见过餐馆中一叠叠的盘子吗？如果它们是按1,2，n的次序往上 叠的，那么使用时候的次序应该是怎样的呢？ 3、在日常生活中，我们去买火车票，我们经常要做的事情是什么？ 10分钟 总结导入新课—一受限的线性表 3.1栈 给出栈的定义，通过实例说明栈的操作特性，给出栈的抽象类型 10分钟 根据顺序栈存储示意图写出入栈和出栈算法，分析时间性能 5分钟 基本操作算法实现与分析 1 5分钟 提出问题：如何改造单链表形成链栈？给出链栈的存储方案 10分钟 根据链栈存储示意图写出入栈和出栈算法，分析时间性能 回顾顺序表和单链表的比较方法，引导学生自己得出顺序栈和链栈的比 较结果

编号：004 课程 名称 数据结构 章节 名称 第三章 栈和队列 3.1 栈 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 栈的基本操作算法和复杂性分析 √ √ √ 顺序栈及实现 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 熟练掌握栈这两种抽象数据类型的特点，并能在应用问题中正确选择 使用哪种数据结构； ➢ 熟练掌握栈这两种结构的顺序表示和链式表示，会应用它们的基本操 作算法，学会分析算法的时间复杂性和空间复杂性； 教学内容（教学过程设计） 教学安排 复习与新课导入 复习：线性表的插入和删除操作 ↓ 提出问题：1、什么是线性结构？ 2、你见过餐馆中一叠叠的盘子吗？如果它们是按 1,2,.,n 的次序往上 叠的，那么使用时候的次序应该是怎样的呢？ 3、在日常生活中，我们去买火车票，我们经常要做的事情是什么？ ↓ 总结导入新课——受限的线性表 ↓ 3．1 栈 给出栈的定义，通过实例说明栈的操作特性，给出栈的抽象类型 根据顺序栈存储示意图写出入栈和出栈算法，分析时间性能 基本操作算法实现与分析 ↓ 提出问题：如何改造单链表形成链栈？给出链栈的存储方案 ↓ 根据链栈存储示意图写出入栈和出栈算法，分析时间性能 ↓ 回顾顺序表和单链表的比较方法，引导学生自己得出顺序栈和链栈的比 较结果 ↓ 5 分钟 10 分钟 10 分钟 5 分钟 5 分钟 10 分钟

分析顺序栈的缺点，提出共享栈 #define m 64 typedef struct (ElemType data[m]; int top[2:/top[0],top[1]分别是两个栈的栈顶指针 )TStack: 教学提示」 >栈是程序设计中常常用到的一种数据结构，栈的研究历史比较长，也比 较成熟。 熟练掌握并学会使用栈对后面的学习十分有益 注意将栈与线性表进行比较，根据生活中的实例深刻理解栈的操作特性 一多准备一些栈的应用实例，如果学时有多，给出钱在计算机软件系统的 一些应用实例 重点 (1)栈的梅作特性 重点 （2)栈基本操作的实现， 与 难点 难点 两栈共享共间的实现 教学策赠： 对策 在授课过程中采用多煤体教学，首先还原问题的本来面目 提出问题，引导学生 积极参与—尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率 方法 教学方法：导入，配合图形、实例讲解，提问、讨论 与 教学手段：PPT课件，板书，动画演示 手段 作业： (1)回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回 文，但“god”不是回文。试写一个算法判定给定的字符向量是否为回文。（提 作业 示：将一半字符入栈) 及 课外 (2)设从键盘输入一整数的序列：al,a2,a3,an,试编写算法实现：用 栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并 出栈。算法应对异常情况（入栈满等）给出相应的信息。 (3)从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆 波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作 符只可能有+、一、/四种运算。例如：23434+2$

分析顺序栈的缺点，提出共享栈 #define m 64 typedef struct {ElemType data[m]; int top[2]; //top[0],top[1]分别是两个栈的栈顶指针 }TStack; 教学提示： ➢ 栈是程序设计中常常用到的一种数据结构，栈的研究历史比较长，也比 较成熟。 ➢ 熟练掌握并学会使用栈对后面的学习十分有益 ➢ 注意将栈与线性表进行比较，根据生活中的实例深刻理解栈的操作特性 ➢ 多准备一些栈的应用实例，如果学时有多，给出栈在计算机软件系统的 一些应用实例 重点 与 难点 对策 重点： （1）栈的操作特性； （2）栈基本操作的实现。 难点： 两栈共享共间的实现 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回 文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提 示：将一半字符入栈) （2）设从键盘输入一整数的序列：a1, a2, a3，.，an，试编写算法实现：用 栈结构存储输入的整数，当 ai≠-1 时，将 ai 进栈；当 ai=-1 时，输出栈顶整数并 出栈。算法应对异常情况（入栈满等）给出相应的信息。 （3）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆 波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作 符只可能有+、-、*、/四种运算。例如：234 34+2*$

课后导读： 回顾C语言中学过的函数嵌套调用，深入理解函数调用时系统的工作 关于栈与队列的实现，《数据结构与算法》（齐德昱编著清华大学出版社）中 有用面向对像方法实现的 在《数据结构》（刘大友等高等教育出版社）中对递归和汉诺塔问题进行了更 深入的介绍 教学 后记

课后导读： ➢ 回顾 C 语言中学过的函数嵌套调用，深入理解函数调用时系统的工作 ➢ 关于栈与队列的实现，《数据结构与算法》（齐德昱编著 清华大学出版社）中 有用面向对象方法实现的 ➢ 在《数据结构》（刘大友等 高等教育出版社）中对递归和汉诺塔问题进行了更 深入的介绍 教学 后记