数据结构（Python Java）（微课版） 教案 -单元3栈和队列

教案课程名称数据结构与算法设计课程代码总学时64课程负责人任课教师

单元教案授课日期年月日—月日授课地点授课班级班级人数教学单元单元3栈和队列教学时数8教学目标AOB1:掌握计算机程序设计中的线性表、栈、队列、树和图的逻辑结构与存储结构。了解递归的数据逻辑组织结构；AOB2:掌握计算机程序设计中的线性表、栈、队列、树、图的数据增、删、改、查操作运算。了解递归的处理算法。掌握选择与排序处理算法；AOB3:掌握对算法的科学分析方法。BOB1:能根据实际问题中的数据特性选择适当的数据结构；BOB2:设计出适当的算法和程序。EOB1:掌握使用搜索引擎、论坛、帮助文档、课外书籍等方法解决学习中出现的问题；EOB2:能主动阅读书后拓展知识并进行实验验证；EOB3:能独立分析解决问题，能把自己的想法用代码实现。教学方式混合式教学评价方式课堂考勤（20%），课堂活动参与程度（20%）线上单元测试（40%）线下课堂教学参与程度（20%）教学资源1.算法与数据结构（Java语言描述），陈媛，清华大学大学出版社2.电脑50台（含eclips）;3.网络学习资源：/forums/ST_Arithmetic：课程平台网址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea单元教学设计第一次课（2学时）教学内容3.1栈定义：只能在表的一端进行插入和删除的线性表逻辑结构：数据元素之间是一对一的关系存储结构：顺序存储或链式存储运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则基本操作：建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值栈的结构栈是仅在表尾进行插入、删除操作的线性表表尾(即an端)称为栈顶(top)表头(即a1端)称为栈底(bottom)插入元素到栈顶的操作，称为入栈从栈顶删除元素的操作，称为出栈栈的基本操作initStack()：初始化操作。设置一个空栈isEmpty()：判栈空函数。若为空栈，函数值为1，否则为0size()：求栈深函数。函数值为栈中当前的元素个数top()：读栈顶元函数。若栈不空，函数值为栈顶元素，否则为空元素NULLpush(x)：进栈操作。将元素x插入栈中，使x成为栈的栈顶元素pop()：出栈函数。若栈不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULLclear()：栈置空操作。不论栈是否为空栈，置为空栈栈的顺序存储结构（顺序栈）利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素栈的链式存储结构（链栈）组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶教学重点栈的顺序存储和链式存储教学难点栈的顺序存储和链式存储教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（30分钟）1.栈的定义（5分钟）2.栈的基本操作（5分钟）3.栈的顺序存储（10分钟）4.栈的链式存储（10分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动代码实现演示（50分钟）1.栈的顺序存储代码实现（25分钟）2.栈的链式存储代码实现（25分钟）1.认真思考、记录关键内容总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第二次课（2学时）教学内容技能训练：栈操作目标：掌握入栈与出栈操作训练步骤：一、用顺序表实现栈1创建栈类，创建数组，设定数组最大值。2创建入栈方法push(){参数、方法自己写}3创建出栈方法pop(){方法自己写}4创建查看栈顶元素的方法getTop(){方法自己写}5主函数中证明所有方法在各种正常情况下的正确性，尤其是栈空与栈满的状态。二、用链表实现栈1创建栈类，创建链表栈。2创建入栈方法push(){参数、方法自己写}3创建出栈方法pop(){方法自己写}4创建查看栈顶元素的方法getTop(){方法自己写}5主函数中证明所有方法在各种正常情况下的正确性，尤其是栈空的状态。教学重点栈操作的实现教学难点栈操作的实现教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤技能训练（80分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第三次课（2学时）教学内容栈的应用1.十进制数转换成二进制数把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）2.单链表的逆置3.表达式求值对算术表达式求值：1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：采用“运算符优先数法”对每种运算符赋于一个优先数：运算符：*/+-#优先数：22110其中#是表达式结束符表达式求值时，设立两个栈运算符栈(OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数4.函数调用模块化程序设计方法，通过主函数调用模块来解决复杂的实际问题。由于函数调用后，需返回调用处，所以在调用时，需用栈记录断点的地址以及有关信息，以便返回。5.地图四染色问题“四染色”：可以用不多于四色对地图着色，使相邻的地区不重色算法思想：回溯法①从第一号地区开始逐一染色，每一个地区逐次用色数1、2、3、4进行试探。②若当前所取的色数与周围已染色的地区不重色，则用栈记下该地区的色数，否则依次用下一色数进行试探。③若出现用1..4色均与相邻地区发生重色，则需退栈回溯，修改当前栈顶的色数。教学重点栈的应用教学难点栈的应用教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（80分钟）1.十进制数转换成二进制数（10分钟）2.单链表的逆置（10分钟）3.表达式求值（25分钟）4.函数调用（10分钟）5.地图四染色问题（25分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第四次课（2学时）教学内容队列队列的定义：只能在表的一端进行插入，在表的另一端进行删除的线性表逻辑结构：元素之间是一对一的关系存储结构：顺序队列和链队列运算规则：队尾入队、队头出队，遵循先进先出（FIFO）的原则基本操作：入队、出队、建空队列、判队空或队满在队尾插入元素称为入队在队首删除元素称为出队队列的顺序存储结构队列的顺序存储，称为顺序队列由一个存放队列元素的一维数组，和队头、队尾“指针”组成。队列的链式存储结构链队列：队列的链式存储是单链表，同时带有头指针和尾指针头指针指向队头结点尾指针指向队尾结点教学重点队列的顺序存储实现，队列的链式存储实现教学难点队列的顺序存储实现，队列的链式存储实现教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（30分钟）1.队列的定义（10分钟）2.队列的顺序存储实现（10分钟）3.队列的链式存储实现（10分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动代码实现演示（50分钟）1.栈的顺序存储代码实现（25分钟）2.栈的链式存储代码实现（25分钟）1.认真思考、记录关键内容总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务教学效果与反思根据单元测验结果，90%的学生教好掌握了教学内容，达成了单元教学目标。其中教学目标AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3达