数据结构（Python Java）（微课版） 教案 -单元2线性表

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

单元教案授课日期年月日—月日授课地点授课班级班级人数教学单元单元2线性表教学时数10教学目标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学时）教学内容2.1线性表的定义线性表：n(n≥0)个具有相同特性的数据元素的有限序列，n表示线性表的长度，即数据元素的个数，n=0时表为空表，n>0时记为:（a1，a2，…ai-1，ai，ai+1，…an）基本特征：有且只有一个第一元素，且只有一个最后元素。除第一元素之外，其它元素都有唯一的直接前趋。除最后元素之外，其它元素都有唯一的直接后继线性表举例：数据元素在不同问题中的含义各不相同，可以是一个数、一个符号，一个记录，或其它复杂的信息数据元素是每一个学生的信息，包括：学号、姓名、成绩共三个数据项线性表的运算初始化线性表，表置空，求线性表中第i个元素，查找满足给定条件的数据元素，在线性表的第i个位置之前插入一个新的数据元素，删除线性表中的第i个数据元素，查找表中第i个元素的前驱，查找表中第i个元素的后继2.2线性表的顺序存储顺序存储：在内存中开辟连续的存储空间，用连续的存储单元依次存放线性表的数据元素顺序表：顺序存储的线性表特点：逻辑上相邻的数据元素，其物理位置也相邻。利用物理位置上的关系，反映元素的逻辑关系顺序存储结构的优缺点优点：静态操作容易实现。根据定位公式容易确定表中元素的存储位置，元素随机存取缺点：1.动态操作实现效率较低，插入和删除结点困难，扩展不灵活，容易造成空间浪费。2.建表时，若估计不到表的最大长度，就难以确定分配的空间，影响数据扩展，分配的空间过大，则会造成预留空间浪费教学重点线性表的顺序存储教学难点线性表的顺序存储教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（50分钟）1.线性表的定义（10分钟）2.线性表举例（10分钟）3.线性表的顺序存储（15分钟）4.顺序存储结构的优缺点（15分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动代码实现演示（30分钟）1.顺序表运算代码实现1.认真思考、记录关键内容总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第二次课（2学时）教学内容技能训练：顺序表操作目标：掌握顺序表的数据插入与删除方法训练步骤：1创建线性表String[]strList自己设定长度。2创建方法add（intindex,Stringstr）{方法自己写}//用于向strList的index位置插入str。3创建方法addInHead（Stringstr）{方法自己写}//用于向strList的头部插入str。4创建方法addInTail（Stringstr）{方法自己写}//用于向strList的尾部插入str。5创建方法addByString（Stringstr1,Stringstr2）{方法自己写}//用于向strList中第一个str1前插入str2。6创建方法delete（intindex）{方法自己写}//用于将strList的index位置元素删除（后面的元素依次递补）。7创建方法deleteByString（Stringstr）{方法自己写}//用于将strList的所有str元素删除（后面的元素依次递补）。8创建方法display（）{方法自己写}//用于显示strList的所有元素。9主函数中证明所有方法在各种正常情况下的正确性。教学重点顺序表操作的实现教学难点顺序表操作的实现教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤技能训练（80分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第三次课（2学时）教学内容2.3线性表的链式存储结构链表：以链式结构存储的线性表。用一组在物理位置上任意的存储单元来存储线性表的结点。存储单元可以是相邻的，也可以是不相邻的。物理位置上的关系不能反映结点间的逻辑关系链式存储结构的特点用任意位置的存储单元存储线性表的数据元素。结点间的逻辑关系借助结点中的指针(引用)实现。每个数据元素，除存储本身信息外，还需存储其直接后继的信息。结点 数据域：元素本身信息指针域：指示直接后继的存储位置单链表：链表中，每个结点只包含一个指针域结点的代码结构：publicclassSinNode{//SinNode为结点类型publicObjectdata;publicSinNodenext;}双向链表：每一个结点中有两个指针域。一个指向直接后继，一个指向直接前趋结点的代码结构：publicclassDulNode{Objectdata;DulNodenext;DulNodeprior;}顺序存储与链式存储的比较从时间角度：在按位置查找数据、查找元素的前趋和后继方面，顺序存储有较大优势。在插入数据、删除数据时，链式存储有较大的优势。从空间角度：顺序表的存储空间是静态分配的，在程序执行之前必须规定其存储规模。动态链表的存储空间是动态分配的，只要内存空间有空闲，就不会产生溢出。教学重点线性表的链式存储结构教学难点线性表的链式存储结构教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（40分钟）1.线性表的链式存储结构（10分钟）2.链式存储结构的特点（5分钟）3.单链表（10分钟）4.双向链表（10分钟）5.顺序存储与链式存储的比较（5分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动代码实现演示（40分钟）1.单向链表的代码实现（20分钟）2.双向链表的代码实现（20分钟）1.认真思考、记录关键内容总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第四次课（2学时）教学内容技能训练-链表操作目标：掌握链表的数据插入与删除方法训练步骤：1创建节点Node类，包含Stringstr；Nodenext；NodePrior；创建链表类（类名自己写），创建双向链表strList2创建方法add（intindex,Stringstr）{方法自己写}//用于向strList的index位置插入str。3创建方法addInHead（Stringstr）{方法自己写}//用于向strList的头部插入str。4创建方法addInTail（Stringstr）{方法自己写}//用于向strList的尾部插入str。5创建方法addByString（Stringstr1,Stringstr2）{方法自己写}//用于向strList中第一个str1前插入str2。6创建方法deleteByIndex（intindex）{方法自己写}//用于将strList的index位置元素删除。7创建方法deleteByString（Stringstr）{方法自己写}//用于将strList的所有str元素删除。8创建方法display（）{方法自己写}//用于显示strList的所有元素。9主函数中证明所有方法在各种正常情况下的正确性。教学重点链表操作的实现教学难点链表操作的实现教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤技能训练（80分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第五次课（2学时）教学内容2.4线性表的应用1.有序单链表的合并：一元多项式求和2.稀疏矩阵的三元组表示法3.稀疏矩阵的十字链表表示法循环链表应用-约瑟夫环问题约瑟夫，是一个古犹太人，曾经在一次罗马叛乱中担任将军，后来战败，他和朋友及另外39个人躲在一口井里，但还是被发现了。罗马人表示只要投降就不死，约瑟夫想投降，可是其他人坚决不同意。怎么办呢，他想到一个主意：让41个人围成一个圆圈，从第一个人开始报数，数到3的那个人被旁边的人杀死。这样就可以避免自杀了，因为犹太人的信仰是禁止自杀的。结果一群人杀来杀去最后只剩下两个了，就是约瑟夫和他朋友，于是两人愉快地去投降了。问题：约瑟夫和朋友站在什么位置才保住了性命。请用循环链表实现过程（报数，移除圈），并输出结果（幸存者的位置）。教学重点线性表的应用教学难点线性表的应用教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（30分钟）1.线性表的应用1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动技能训练（50分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程