2.2 链表（教学设计）信息技术浙教版2019选择性必修1

2.2 链表 3课时（教学设计） 年级 高二年级 授课时间 3课时 课题 2.2 链表 教学 目标 1.初步理解数据结构的概念及其作用。 2.掌握链表的基本操作。 3.能运用链表编程解决实际问题。 教学 重难点 重点： 1. 链表的概念、特性。 2. 链表的基本操作。 难点： 1. 对链表进行基本操作时各节点及指针的变化。 2. 结合真实的问题情境，选择合适的数据结构来组织和存储数据。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.让学生观看一段排队的视频，视频中的男主人翁用一块砖头标记自己的位置并让别人以此为标记继续站位。 2.再单独把砖头标记那一段截图出来，回忆之前讲过的内容：数组，再次对比链表的优势。 学生观看视频和教师单独截图的图片，思考 数组与链表的优缺点。 新 知 讲 授 2、 链表的概念与特性 概念：将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 1.链表的组成 链表的组成部分：数据区域和指针区域。 ①单向链表中各个结点在内存中可以非顺序存储； ②每个结点使用指针指向其后继结点的存储地址 ③进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。 头节点:用于进入链表和边界判断 前驱节点:某个节点前面的相邻节点 后继节点:某个节点后面的相邻节点 尾节点:最后一个节点，指针指向空 2.单向链表 单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。 进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。 3.链表内存存放方式： 头指针的作用：①链表的入口，只有通过头指针才能进入链表。 ②为循环链表设立一个边界，便于数据处理时的边界判断和处理。 4.链表的特性 （1）同一链表中每个节点的结构均相同 链表节点中包含数据区域和指针区域。不管是单向链表还是双向链表，每个节点的数据区域中的数据类型是相同的，指针区域中的指针数量和功能是相同的。 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 链表的节点间通过指针相连，相邻节点存储时不需要连续空间，充分利用了内存的零散空间，提高了存储空间利用率。由于链表的存储空间由节点数决定，增加或减少节点都会改变链表占用的存储空间，因此链表占用的空间不固定。 5.探讨与讨论 三、链表的基本操作 Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。 实现单向链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。 用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。 1.链表的创建 创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。 ①使用列表模拟链表 ②探讨与讨论 2.链表节点的访问 链表只能通过头指针(head)进行访问，其他节点通过节点间的指针依次访问。如图，当想访问单向链表中data3所在的节点时，需通过头指针进入链表，再分别按照各个节点的指针指向经过data1和data2所在节点，最后通过data2所在节点的指针才能访问data3所在的节点。 3.链表节点的插入与删除 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。链表节点的删除，则通过将需要删除的节点的前驱节点和其后继节点直接相连的方式实现。 (1)链表的插入 以单向链表插入新节点为例，在空单向链表中插入第一个节点或在非空单向链表中插入第一个节点时，需要先修改新节点的指针指向与头指针一致，再修改头指针指向新节点;在非空单向链表两个节点中间插入新节点时，需要先修改新节点指针指向与前一节点的指针指向一致，再将前一节点的指针指向新节点。 ①从头部插入新节点。 ②从中间插入新节点。 ③从尾部插入新节点。 （2）链表元素的删除 删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。 链表节点的删除，并没有将元素从列表中删除，而仅仅是修改了节点指针域的值，通过将被删除节点的前驱节点和其后继节点直接相连的方式实现。 尾节点可以直接删除，若删除了头节点，则需要修改头指针。 （3）探讨与讨论 4.链表节点的访问与遍历 由于链表中的节点通过指针相互链接，当需要访问某个位置的节点元素时，只能通过头指针进入链表并通过节点间的链接关系一个一个往下访问，直到找到指定位置的节点。 与数组相比，其节点的访问效率较低。 实现链表及其基本操作后，可以使用其存储和处理数据，帮助人们解决问题。 （1）约瑟夫问题 n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。 这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的（n个），因此最终会只剩下1个人。 试问：最后剩下的人的初始编号是多少? ①抽象与建模 ②设计数据结构与算法 ③编写程序 四、链表的类实现 在Python中，链表除了可以使用列表来实现，还可以使用“类”来实现。“类”是一种抽 象的数据结构，它将数据及其操作封装在一起。 1. 自定义单向链表的节点类 2.构造单向链表类 有了以上类的构造，就可以创建单向链表并进行空表判断、增删节点等基本操作。使用自定义类的方式建立的单向链表可以充分体现链表的特性。 五、课堂小结 从数组在解决实际问题时的不足出发，引出本节课学习主题，展示学习内容的重要性，并初步建立链表与数组的关系，为最后应用数据结构解决问题做铺垫。 讲授基础理论，辅以图示，让学生对理论有更形象的了解，落实教学重点。 设置难度适当的实践练习，加深学生对链表概念和特性的理解，确定后续新知讲授的推进。 链表基本操作是本次课的重难点内容，通过图片、表格呈现和实例演示，将链表基本操作的原理可视化，便于学生掌握链表基本操作的本质，落实教学重点。 循序渐进的从链表的创建 →节点的访问 →节点的插入与删除 →节点的访问与遍历 该环节新知讲授都在图示作用下推进，让学生对程序实现的目的有直观的感受，提高对新知的理解程度，落实教学重点。 通过讲授部分情况节点插入和删除的实现，加深节点指针在列表中的实现。 通过应用链表解决“约瑟夫问题”，使学生熟悉应用数据结构解决问题的一般步骤，并进一步感受链表的特性，以及链表基本操作的原理，突破教学难点，落实信息意识和计算思维的培养。 梳理本次课内容，形成知识体系；分析数据结构重要性，并对今后学习进行展望。 课 堂 练 习 （有题有答案有解析） 1.链表的节点由 和 两部分组成。 2.每一个链表都有一个 （也称为 ），它的作用之一是： ，作用之二是： 。 3.链表可以根据每个节点中指针的数量分为两类： 和 。 4.链表的基本操作主要有 、 、 和 等 5.python中通过来 和 模拟实现链表结构。 6.链表的特性包括哪些？ 7.以下有关链表的描述,不正确的是( ） A.插入、删除操作无须移动数据元素 B.增加或减少节点会改变链表占用的存储空间 C.可随机快速访问任何一个数据元素 D.同一链表中每个节点的结构均相同 8.在列表： a =[[ 99, 1 ],[ 95, 2 ],[ 88, -1] ]中，列表a有 个元素；数据元素(a[0])的第一个元素(99)为 ，数据元素(a[0])的第二个元素(1)为 ，是列表a的第二元素的 。 9.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a: a=[[“hello”,1],[“china”,3],[“Olympics”,-1],[“winter”,2]] head=0 ①a[1][1]的值为:（ ） A.1 B.2 C.0 D.3 ②a[1][1]的含义是什么? 10.有如下python程序段： a = [[3, 2], [2, 3], [7, 1], [1, 0]] head = 0 p = head while a[p][1] != head: print(a[p][0], end="->") p = a[p][1] print(a[p][0]) 执行上述语句后，程序输出的结果为（ ） 11.有如下python程序段： a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有几个节点（ ） A.1 B.2 C.3 D.4 程序实现了什么功能？ 程序执行后链表a变为： 12.对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ) A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 答案： 1.数据区域和指针区域。 2.表头、头指针、作为链表的入口、为循环链表设立一个边界。 3.单向链表、双向链表。 4.空链表的创建、节点访问、节点插入和删除 5.列表、类 6.（1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 7.[解析]链表的访问需要通过头指针以节点链接的方式依次访问，选项C描述的是数组的访问方式。因此正确答案是C。 答案：C 8.3、数据域、指针域、索引。 9.[解析]根据head=0，头节点是[“hello”,1]，依次访问的节点就是[“china”,3],[“Olympics”,-1],[“winter”,2]，因此输出的类容就是3。 答案：①D②china后面指向的下一个节点是[“winter”,2]。 10.[解析]二维数组a表示一个循环单向链表,a[p][0]和a[p][1]分别存储节点p的数据和指针,程序功能从 头节点开始遍历链表输出各节点的值。 答案：3->7->2->1 11.[解析]根据Python程序段，程序语句执行后，链表a有3个节点。 答案：C、删除了头部节点[6,0]、a=[[7,1],[8,2],[9,-1],[6,0]] 12.B 课 堂 小 结 课堂小结 一、链表的概念与特性 1. 链表的概念 2. 链表的特性 （1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 二、链表的基本操作 1. 链表的创建 2. 链表节点的访问 3. 链表节点的插入与删除 4. 链表节点的访问与遍历 作 业 设 计 1.下列关于数据结构的说法，正确的是（ ） A.常见的线性关系数据结构有数组、链表、队列、栈和图 B.数组和链表在操作时，其存储空间固定不变 C.链表在插入和删除元素时，算法效率比数组高 D.进行数据的插入操作时，链表中的元素会被移动 2.对于单向链表的节点结构，以下说法不正确的是（ ） A.节点的数据区域用于存放实际需要处理的数据元素 B.节点的指针区域用于存储相邻节点的存储地址 C.单向链表必须带有数据区域为空的头节点和尾节点 D.单向链表中的各个节点在内存中可以非顺序存储 3.有如下Python程序段: d=[["a",2],["b",-1],["c",1]] head=0 p=0 d.append(["d",d[p][1]]) d[p][1]=len(d)-1 执行上述程序段后，下列说法正确的是（ ） A.d[0][1]的值为2，单向链表d的尾节点数据值为“b” B.d[1][1]的值为-1，单向链表d的尾节点数据值为“b” C.d[3][1]的值为1，单向链表d的尾节点数据值为“c” D.d[2][1]的值为1，单向链表d的尾节点数据值为“c” 4.采用列表模拟单向链表，data[p][0]为数据区域，data[p][1]为指针区域。在单向链表指针为 p的节点之后插入指针为 s 的节点，正确的操作是( ) A.data[s][1]=p data[p][1]=data[s][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 5.有一组数据集合由1到m之间的正整数组成。指定一段数据的开始位置和结束位置，能够统计出该段数据中不同数值的个数。编写Python，实现上述统计功能。运行程序，随机生成n个1到m之间的正整数和Q个询问L和R。 实现上述功能的Python程序如下，请在划线处填入合适的代码。 n=int(input()) a=list(map(int,input().split())) Q=int(input()) ask=[[0]*100 for i in range(100)] Min=9999999 Max=-1 pos=[0]*100 Next=[-1]*100 for i in range(Q): L,R=map(int ,input().split()) if(L<Min): Min=L if(R>Max): Max=R ask[i][0],ask[i][1]=L,R for i in range(Min,Max+1): if pos[a[i]]==0: pos[a[i]]=i Next[i]=0 else: ① pos[a[i]]=i for i in range(Q): num= ② for j in range(ask[i][1],ask[i][0]+1,-1): if ③ : num-=1 print(ask[i][0],"到",ask[i][1],"之间有：",num,"个不同的数") 答案： 1.[解析]常用的线性结构有:线性表，栈，队列，双队列，串(一维数组)，但树和图是非线性结构选项A错误;数组在创建时其存储空间就已经固定，选项B错误;链表在插入和删除元素时，算法效率比数组 高;进行数据的插入操作时，链表中的元素不会被移动。 答案：C 2.[解析] 单向链表的头节点和尾节点可以是单独的数据区域为空的节点,也可以将节点序列中的第一个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式,即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。 答案：C 3.答案：B 4.[解析] 在单向链表指针为p的节点之后插入指针为s的节点，则s的指针域指向p的下一个节点，即data [s] [1] = data [p] [1]，其次将p和s连接起来即p的指针域指向s，所以选项C符合题意。 答案：C 5. ①Next[i]=pos[a[i]] ②ask[i][1]-ask[i][0]+1 ③Next[j]>=ask[i][0] and Next[j]<=ask[i][1] 反 思 评 价 本课时通过项目驱动，开展“链表在解决实际问题时的应用”的教学，包括应用过程和编程实现，需要学生具有比较全面的素质。结合微课在项目实践中的优势，学生可以有充分的思考和尝试时间，但考虑到学生的差异性，因此在编程实践时提供半成品程序资源，让编程能力较弱的同学也能在项目实践中感受到项目完成的成就感，激发其进一步学习的积极性。为实践能力较强的同学提供了拓展程序，让其能力得到充分的训练。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$