2.2链表教学设计
一、教学设计
课程标准 和 教学目标 链表
教材内容： 2.2链表的概念、特性、基本操作
1.3结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。 1.4 通过案例分析，理解链表的概念，并能编程实现其相关操作。
教学目标： ●通过案例分析，理解链表的概念、特性。 ●结合链表的具体应用，在解决问题的过程中理解链表的特性和基本操作。 教学重点：链表的概念、组织结构及其特性 教学难点：能理解数组、链表的区别，并能选择合理的数据结构编程实现、解决问题。 指向的核心素养： 本节主要内容为介绍链表的概念、特性及其基本操作，并在此基础上结合实例（合并数据项目的链表实现、约瑟夫问题等）学习，体验如何使用链表组织、存储数据并编程解决具体问题，核心素养主要通过以下几方面进行落实： ●信息意识方面的指向:使学生能够运用生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，用合理的数据结构表达数据的逻辑关系。 ●计算思维方面的指向:使学生能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法编程实现、解决问题。
学习环境：机房，预装Python编程环境。
建议课时：1.5课时
教学活动设计 教学环节 教学过程 设计意图
情境导入1 观看“排队与插队”视频，讨“数组”存储结构的应用局限性： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 排队与插队的生活案例，引导学生思考“数组”数据结构在特定场景下的应用局限性，为“链表”非顺序存储结构的介绍做好铺垫。同时通过“数组”的过度有利于加深学生对“数组”存储模式和“链表”存储模式的理解。
知识讲解1 通过围绕“体育课整队”的案例展开探讨，回顾单向链表数据结构，学习链表的基本概念。 在1.2.2常见的数据结构中已经有对链表知识的介绍，本课通过“生活中的数据结构”问题探讨展开教学，既起到回顾已有知识的作用，又能自然过度到本课对链表展开深入研究。。
问题与讨论1 参考单向链表的结点结构及其指针指向，讨论并描述双向链表和循环链表的结点结构及其指针指向。 基于单向链表的学习，引导拓展到双向链表和循环链表知识，有助强化学生对链表结构的理解，培养学生知识迁移的能力。
知识讲解2 基于前面链表结构与概念的讲解，引导学生总结归纳链表的三大性质： 同一链表中每个结点的结构均相同 每个链表必定有一个头指针，以实现对链表的引用和边界处理 链表占用的空间不固定 明确告诉学生，由于Python没有指针的概念，无法直接定义链表的结构，只能通过列表来模拟，在这里我们通过列表的索引来模拟数据存放的地址。然后，围绕列表模拟来讲解链表创建、链表访问及链表结点的插入与删除方法。 学生通过前面的教学环节学习基本理解链表的结构特征与实现方式。本环节通过交流、反思的形式来进一步梳理链表的特性，既有利于进一步加深学生对链表的理解，同时，又有利于学生分析、总结、归纳能力的提升，也有利于学生与团队成员分享信息意识的形成。 利用列表模拟来研究链表的特征与基本操作，既有利于培养学生编程实现的意识与能力，同时又能让学生养成探究计算机领域原理与方法的习惯，培养学生对计算机科学的兴趣。
问题与讨论2 引导学生自主思考以下两个问题： 在单向链表中插入新结点时，指针指向的修改是否必须有先后？如果将其顺序逆转，能否完成新结点的插入？为什么？ 如果在尾结点之后插入新结点，那么结点指针该如何修改？ 用列表模拟插入新结点的过程，并描述在8个结点的单向链表中删除第一个结点、中间结点及尾结点的过程。 教师不是直接向学生讲解结点插入的步骤，而是通过问题的形式引导学生思考链表结点插入的步骤为什么不能颠倒，有利于加深对链表操作实质的理解，从而实现知识的内化。同时，通过让学生在自学链表插入新结点方法的基础上，自主探究删除结点的方法，有利于学生知识迁移能力的提升。
知识讲解3 通过“基于链表实现数据合并功能”的项目讲解，落实单向链表的基本操作。 通过“约瑟夫”项目的分析，让学生体验问题界定、抽象特征、建立结构模型、合理组织数据结构，形成算法、程序实现的过程，同时进一步学会循环链表的操作。 在“合并数据”项目的链表实现与数组实现内容前后呼应，但其并未体现链表的优势，不过在熟悉的项目中，有利于落实单向链表的基本操作；链表教学项目的重点放在了“约瑟夫问题”项目，一方面是“约瑟夫问题”是链表应用的经典项目，另一方面则是其应用需要构造单向循环链表，可以更全面的展示链表的特性与基本操作。
课堂小结 知识梳理： 学习评价（附件10：学习评价表） 通过自评引导学生反思本节课所学内容，发现问题与不足，起到查漏及巩固的作用，通过互评与交流加强同伴的交流与合作，实现团队协作中多种能力的培养。
布置作业 ●基础作业（面向所有学生）： 基础作业（面向所有学生）： 1. 在单向链表在内存中的存储模式图（课本图2.2.2）基础上，请根据双向链表和循环链表的特性，画出它们在内存中的存储模式图。 2. 参考课本图2.2.3，描述出在有3个结点的单向链表中删除第1个、第2个及第3个结点的过程。 3. 数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善课后思考与练习表格。 4. 参考教材中单向链表的列表实现，请思考如何使用列表实现双向链表的结构及其基本操作，思考完善后编程实现双向链表结点的创建、增加、删除及显示等。 ●提升作业（面向学有余力学生）： 设计查找单链表的中间节点的算法，要求只能使用一重循环（只遍历一次）。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。根据学生的基础和能力设置不同难度的作业，以满足不同层次的学生需求。
针对 核心素养培养的 设计考虑 本节教学过程是理论与实践操作相结合的过程，因此可以从以下维度培养学生的核心素养。 信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当方式获取信息与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。”在链表的概念及其基本操作讲解中加入数组对比，如链表允许每个结点随机存储，而数组则是按照下标顺序存储；链表的插入、删除操作不需要移动其他结点的位置，而数组则需要进行其它相关数组元素中的数据移动位置，链表不能直接访问结点，必须通过头指针进行访问，其他结点通过结点件的指针依次访问，而数组可以通过下标直接访问等等。通过“数据合并”、“约瑟夫问题”等项目情景引导学生在项目实现过程中自主分析并提取关键数据选择合适的数据结构存储这些数据，体验到数据结构设计与算法效率的相关性，提升学生的关键数据规划意识；以上过程中均在培养或提升学生获取关键信息的能力，即信息意识的培养与提升。 计算思维：落点在 “能够采用计算机科学领域的思想方法界定问题、抽象问题特征、建立结构模型、合理组织数据；通过判断、分析与综合各种信息资源，运用合理的算法形成解决问题的方案。”学生在“约瑟夫问题”实现过程中，在教师的引导下体验并参与完整的问题解决过程，学习并明了计算机解决实际问题的步骤及相应算法的设计，在此基础上，学生自主完成班级学生随机抽奖问题（链表实现）的建模及算法设计，在该过程中可以加深及强化学生建模及算法设计的能力，提升自身的计算思维。2.2链表教学设计
一、教学设计
课程标准 和 教学目标 链表
教材内容： 2.2链表的概念、特性、基本操作
1.3结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。 1.4 通过案例分析，理解链表的概念，并能编程实现其相关操作。
教学目标： ●结合链表的具体应用，在解决问题的过程中理解链表的特性和基本操作。 ●掌握链表元素访问、修改及输出的方法。 ●学会分析数据结构与算法对程序执行效率的影响 的特性和基本操作。 教学重点：链表的基本操作 教学难点：能理解数组、链表的区别，并能用程序实现链表的基本操作。选择合理的数据结构编程实现、解决问题。 指向的核心素养： 本节主要内容在理解链表的概念、特性及其基本操作结合实例约瑟夫问题的学习，体验如何使用链表组织、存储数据并编程实现，核心素养主要通过以下几方面进行落实： 信息意识方面的指向:使学生能够运用生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，用合理的数据结构表达数据的逻辑关系。 计算思维方面的指向:使学生能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法编程实现、解决问题。
学习环境：机房，预装Python编程环境。
建议课时：1.5课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 约瑟夫问题是以弗拉维奥约瑟夫斯（FlaVius Josephus）命名的，他是一世纪的一名犹太历史学家。在 Josephus留下的日记中，描述了这样一个故事:在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人，该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16与第31号位置，于是逃过了这场死亡游戏。 Josephus把他的存活归因于运气或天意，但实际上对于任意给定的n（n个人）和m（第m个人出列），可以通过一个计算模型推断出所有人员自杀的序列。请思考解决约瑟夫问题的计算模型，结合所学线性表数据结构来设计约瑟夫问题的算法，并使用Python语言编程实现。 通过约瑟夫问题情境的引入，提出本节课的学习活动目标
知识讲解1 ①对“约瑟夫问题”进行抽象与问题界定。 ②探讨实现“约瑟夫问题”可以选择那些数据结构？（链表、数组、列表） ③基于各种数据结构的算法效率进行预判。 培养学生问题分析、抽象、建模的能力
问题与讨论 设计数据结构与算法： 组内成员根据分配的数据结构展开算法设计。如：通过探讨，在“约瑟夫问题”中，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。组内2到3人可以围绕“链表”数据结构展开编程设计，程序实现能力较强的成员在“链表”外另选一种数据结构进行拓展学习。 算法实现如下： 链表版算法： ①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。 ②重复执行下列处理，直到链表中只剩下一个结点随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数 器i的值为1。 ③将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。 数组版算法： ①创建一个数组含n个数组元素组成，使报数计数器i的初始化值为1，同时当前报数人的指针k指向数组中第一个元素。 ②重复执行下列处理，直到数组中只剩下一个数组元素。随着报数的进行，不断指向下一个数据元素，报数计数器i，k（k=k%剩余人数+1）也随之增加，当i增加到淘汰数m时，将K之后的所有数组元素向前移动一位，k位置元素被覆盖删除；在k元素被删除的同时，需要重置报数计数器i的值为0，k的设为K-1。 ③将数组中唯一数组元素，也就是K指向的数组元素（即初始编号）输出。 列表版算法 ①创建一个列表含n列表元素，使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个列表元素。 ②重复执行下列处理，直到列表中只剩下一个列表元素。随着报数的进行，不断指向下一个列表元素，报数计数器i，k（k=k%剩余人数+1）也随之增加，当i增加到淘汰数m时，直接删除K元素；在k元素被删除的同时，需要重置报数计数器i的值为0，k设为K-1。 ③将列表中唯一列表元素，也就是K指向的列表元素（即初始编号）输出 采用链表、数组、列表等多种数据结构实现“约瑟夫”问题，让学生在对比分析中加深各种数据结构的理解，同时，学会从不同角度思考问题，评价并采用最优方案解决问题。
自主学习 代码实现 调试运行 测试项目问题背景数据41,3 输出是否为31。 测试边界值18,1；99,1；999,1结果是否为前一个数。 组内数据对标：组内成员选择几组数据进行对标，查看是否一致。 程序效率对比 自学“python time包”学习材料，使用time.clock（）对程序运行时间进行计时。 小组成员分别记录程序在不同数据规模下的运行时间，分析数据结构与算法设计对程序运行效率的影响。 根据上面两步的学习与分析，在数字机房内分组采取不同的算法编程解决具体问题，体验链表的具体操作与应用。同时，采用控制变量法测试程序效率，让学生体验程序开发与测试的全过程。
课堂小结 知识梳理: ①总结链表的基本概念与特性 ②使用链表实现约瑟夫问题 ③掌握链表节点的访问与遍历 学习评价：（详见附件9） 通过自评引导学生反思本节课所学内容，发现问题与不足，起到查漏及巩固的作用，通过互评与交流加强同伴的交流与合作，实现团队协作中多种能力的培养。
布置作业 ●基础作业（面向所有学生）： 1. 数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善课后思考与练习表格。 2. 参考教材中单向链表的列表实现，请思考如何使用列表实现双向链表的结构及其基本操作，思考完善后编程实现双向链表结点的创建、增加、删除及显示等。 ●提升作业（面向学有余力学生）： ①设计查找单链表的中间节点的算法，要求只能使用一重循环（只遍历一次）。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。根据学生的基础和能力设置不同难度的作业，以满足不同层次的学生需求。
针对 核心素养培养的 设计考虑 本节教学过程是理论与实践操作相结合的过程，因此可以从以下维度培养学生的核心素养。 信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当方式获取信息与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。”通过“约瑟夫问题”项目情景引导学生在项目实现过程中自主分析并提取关键数据选择合适的数据结构存储这些数据，体验到数据结构设计与算法的相关性，提升学生的关键数据规划意识；以上过程中均在培养或提升学生获取关键信息的能力，即信息意识的培养与提升。 计算思维：落点在 “能够采用计算机科学领域的思想方法界定问题、抽象问题特征、建立结构模型、合理组织数据；通过判断、分析与综合各种信息资源，运用合理的算法形成解决问题的方案。”学生在“约瑟夫问题”项目实现过程中，在教师的引导下体验并参与完整的问题解决过程，学习并明了计算机解决实际问题的步骤及相应算法的设计，在此基础上，学生自主完成程序实现，在该过程中可以加深及强化学生算法设计与程序实现的能力，提升自身的计算思维。
