《链表》公开课教学设计（徐玲芳）高中信息技术浙教版选择性必修1 数据与数据结构.docx

链表一.教学目标1 .通过案例分析，理解链表的概念、特性。2.结合链表的具体应用，在解决问题的过程中理解链表的特性和基本操作。二.教学重点链表的概念、组织结构及其特性三.教学难点能理解数组、链表的区别，并能用程序实现链表的基本操作。选择合理的数据结构编程 实现、解决问题。四.学情分析本课针对选择性必修1数据与数据结构的学生进行教学，“链表”是学生接触的第 二种数据结构。在前面的教学中，学生对于数据结构的概念应该已经比较清晰，也明确了数 组的组织形式及其应用，在这个基础上介绍链表的概念、特性及基本操作，可以让学生更加 深刻的理解数组与链表两种数据结构，同时对于顺序存储模式和非顺序存储模式(链式存储 模式)也有一个更深入的了解。五.教学活动设计(1)情境导入观看“排队与插队”视频，讨“数组”存储结构的应用局限性：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费设计意图:排队与插队的生活案例,引导学生思考“数组”数据结构在特定场景下的应 用局限性,为“链表”非顺序存储结构的介绍做好铺垫。同时通过“数组”的过渡有利于加 深学生对“数组”存储模式和“链表”存储模式的理解。(2)知识讲解通过围绕“体育课整队”的案例展开探讨，回顾单向链表数据结构，学习链表的基本概 念。设计意图:在122常见的数据结构中已经有对链表知识的介绍,本课通过“生活中的 数据结构”问题探讨展开教学,既起到回顾已有知识的作用,又能自然过渡到本课对链表展 开的研究。(3)自主学习参考单向链表的节点结构及其指针指向，讨论并描述双向链表和循环链表的节点结构及其指 针指向。设计意图:基于单向链表的学习,引导拓展到双向链表和循环链表知识,有助强化学生 对链表结构的理解,培养学生知识迁移的能力。(4)知识讲解基于前面链表结构与概念的讲解，引导学生总结归纳链表的三大性质：一链表中每个节点的结构均相同 每个链表必定有一个头指针，以实现对链表的引用和边界处理 表占用的空间不固定设计意图:学生通过前面的教学环节学习基本理解链表的结构特征与实现方式。本环节 通过交流、反思的形式来进一步梳理链表的特性,既有利于进一步加深学生对链表的理解, 同时,又有利于学生分析、总结、归纳能力的提升,也有利于学生与团队成员分享信息意识 的形成。明确告诉学生，由于Python没有指针的概念，无法直接定义链表的结构，只能通过列表来 模拟，在这里我们通过列表的索引来模拟数据存放的地址。然后，围绕列表模拟来讲解链表 创建、链表访问及链表节点的插入与删除方法。设计意图:利用列表模拟来研究链表的特征与基本操作,既有利于培养学生编程实现的 意识与能力,同时又能让学生养成探究计算机领域原理与方法的习惯,培养学生对计算机科 学的兴趣。（5）自主学习引导学生自主思考以下两个问题：在单向链表中插入新节点时，指针指向的修改是否必须有先后？如果将其顺序逆转， 能否完成新节点的插入？为什么？如果在尾节点之后插入新节点，那么节点指针该如何修改？用列表模拟插入新节点的过程，并描述在8个节点的单向链表中删除第一个节点、中 间节点及尾节点的过程。设计意图:教师不是直接向学生讲解节点插入的步骤,而是通过问题的形式引导学生思 考链表节点插入的步骤为什么不能颠倒,有利于加深对链表操作实质的理解,从而实现知识 的内化。同时，通过让学生在自学链表插入新节点方法的基础上,自主探究删除节点的方法, 有利于学生知识迁移能力的提升。（6）学习任务分组实现将两个链表中的数据合并到其中一个链表中（保持降序）的程序。具体编程可以分为以下几步：算法设计初始化两个空链表data_a和data_b,并使用head_a和head_b作为两个链表的头指 针，其中data_a作为存储结果的链表。模拟生成两个降序序列数据，每个序列中第一个数据使用随机函数randint（start, end） 产生，其他数据则由前一个数据减去一个随机值（15）产生，产生的数据作为新节点的数 据区域的值，生成新的节点在尾部插入。使用变量k_a与k_b指向两个链表中未合并的数据序列中最前面（值最大）的结点， 初始化k_a二head_a, k_b=head_b,由于在链表data_a中需要进行插入结点的操作，必须记 录插入位置的前驱结点，使用变量q_a,初始化q_a二head。重复以下操作，直到k_a或k_b 指向空（即某个链表元素全部处理完）：比较data_ak_a和data_bk_b的大小。若 data_ak_aOdata_bk_bO,则修改q_a与k_a相等，再将k_a指向下一个结点；否则将 链表data_b中k_b指向的结点插入到链表data_a中，作为q_a指向结点的后继结点，再将 k_b指向链表data_b中的下一个结点。 k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。 输出链表data_a中每个结点的数据区域的值。程序实现代码（略）设计意图:根据上面两步的学习与分析,在数宁机房内分组编程解决具体问题,体验链 表的具体操作与应用。（7）课堂小结知识梳理:通过思维导图梳理本节课知识链表的概念链表的概念与特性链表的概念与特性链表的基本操作同一链表中将4结点的结构均相同链表的特性每个链表必定有一个头指针.以实现对链表的弓用和边界处理链表占用的空间不固定链表的创建链表结序的迈回出陵5点的插入与除链表结点的访问与遍历课后练习1.链表不具有的特点是A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间2 .下面关于线性表的叙述中, A.线性表采用顺序存储, B.线性表采用顺序存储, C.线性表采用链接存储, D.线性表采用链接存储,错误的是哪一个？必须占用一片连续的存储单元。便于进行插入和删除操作。不必占用一片连续的存储单元。 便于插入和删除操作。D.所需空间与线性长度成正比以下题目均采用列表模拟链表结构，datapO为数据区域，datap为指针区域。3 .在一个以h为头指针的单循环链中，p指针指向链尾的条件是A.datapl=hB.datapO=hC.datadatapll=hD.datapl=-1.在单链表指针为p的节点之后插入指针为s的节点，正确的操作是:A.datapl = sdata sl = data plB.datapl = sdatasl = datapl C.datasl=datapl datapl = sD.datapl = datasl datasl = p参考答案: 14:BBAC