高中信息技术浙教版 (2019)选修1 数据与数据结构第二章 数据与链表2.2 链表精品ppt课件

课程标准

和

教学目标

链表

教材内容： 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. 参考教材中单向链表的列表实现，请思考如何使用列表实现双向链表的结构及其基本操作，思考完善后编程实现双向链表结点的创建、增加、删除及显示等。

●提升作业（面向学有余力学生）：

①设计查找单链表的中间节点的算法，要求只能使用一重循环（只遍历一次）。

课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。根据学生的基础和能力设置不同难度的作业，以满足不同层次的学生需求。

针对

核心素养培养的

设计考虑

本节教学过程是理论与实践操作相结合的过程，因此可以从以下维度培养学生的核心素养。

信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当方式获取信息与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。”通过“约瑟夫问题”项目情景引导学生在项目实现过程中自主分析并提取关键数据选择合适的数据结构存储这些数据，体验到数据结构设计与算法的相关性，提升学生的关键数据规划意识；以上过程中均在培养或提升学生获取关键信息的能力，即信息意识的培养与提升。

计算思维：落点在 “能够采用计算机科学领域的思想方法界定问题、抽象问题特征、建立结构模型、合理组织数据；通过判断、分析与综合各种信息资源，运用合理的算法形成解决问题的方案。”学生在“约瑟夫问题”项目实现过程中，在教师的引导下体验并参与完整的问题解决过程，学习并明了计算机解决实际问题的步骤及相应算法的设计，在此基础上，学生自主完成程序实现，在该过程中可以加深及强化学生算法设计与程序实现的能力，提升自身的计算思维。