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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。