专题17 链表课件-2025-2026学年高考信息技术总复习

专题 17 链表 1 知识梳理 归纳提升 题型考法 考点1 链表的概念与特性 1.链表的概念 （1）链表是将需要处理的数据对象以节点的形式，通过________串联在一起的一种数据结构。 （2）链表每个节点一般由“数据区域”和“指针区域”两部分构成。 （3）每个链表有一个头指针“head”，它是链表的入口，也是为循环链表 设立一个__________，便于数据处理时的边界判断和处理。 指针 　边界　 知识梳理 归纳提升 题型考法 （4）链表可以根据每个节点中指针的数量分为单向链表和双向链表。 ①单向链表：节点中只有一个指针，指向后继节点，尾节点指针为空。 ②基于单向链表的循环链表：每个节点中只有一个指向后继节点的指 针，尾节点指针指向头节点。 知识梳理 归纳提升 题型考法 ③双向链表：节点中有两个指针，一个指向前驱节点，一个指向后继节 点，头节点的前驱指针为空，尾节点的后继指针为空。 ④基于双向链表的循环链表：每个节点中有两个指针，头节点的前驱指 针指向尾节点，尾节点的后继指针指向头节点。 知识梳理 归纳提升 题型考法 2.链表的特性 （1）同一链表中每个节点的结构均相同。 （2）每个链表必定有一个__________，以实现对链表的引用和边界处理。 （3）链表占用的空间不固定。 　头指针　 知识梳理 归纳提升 题型考法 考点2 链表的创建与访问 1.链表的创建 （1）需根据问题特点，规划节点的数据域和指针域，每个节点的结构 必须相同，同时设置一个头指针 head 指向第一个节点。 （2）在 Python 中可以使用二维列表来模拟链表，用包含两个元素的列 表来表示单向链表的每一个节点，用包含三个元素的列表来表示 双向链表的每一个节点。 2.链表节点的访问 只能通过头指针进入链表并通过节点间的链接关系逐个访问，直到找到目标节点查找成功，或遍历结束查找失败。 知识梳理 归纳提升 题型考法 考点3 在链表中插入节点 1.在单向链表中插入节点 （1）在链表头部插入节点。 ①修改新节点的指针，使其指向与头指针一致。 ②修改头指针，使其指向___________。 　新节点　 知识梳理 归纳提升 题型考法 （2）在其他位置插入节点。 ①找到新节点的插入位置，确定其前驱节点prev 以及后继节点 next。 ②修改新节点的指针，使其与_____________ prev 的指针一致，使新节点的指针指向后继节点next。 ③修改前驱节点 prev的指针，使其指向新节点。 　前驱节点　 知识梳理 归纳提升 题型考法 2.在双向链表中插入节点 （1）在链表头部插入节点。 ①先修改新节点的前驱指针，使其指向为空，再修改新节点的后继指针，使其指向与头指针一致。 ②修改头指针以及原头节点的前驱指针，使其指向新节点。 知识梳理 归纳提升 题型考法 （2）在链表中间位置插入节点。 ①找到新节点的插入位置，确定其前驱节点prev 以及后继节点 next。 ② 修改新节点的后继指针，使其与前驱节点prev的后继指针一致。修改新节 点的前驱指针，使其与后继节点 next的前驱指针一致。 ③修改前驱节点 prev 的后继指针和_____________next的前驱指针，使其指向新节点。 　后继节点 知识梳理 归纳提升 题型考法 （3）在链表尾部插入节点。 ①找到链表尾节点 prev，即新节点的前驱节点，修改新节点的后继指针，使 其指向为空。 ②修改新节点的前驱指针，使其指向前驱节点prev（只能通过前驱节点的前 驱节点的后继指针获得）。 ③修改新节点的前驱节点 prev 的后继指针，使其指向新节点。 知识梳理 归纳提升 题型考法 考点4 在链表中删除节点 1.在单向链表中删除节点 （1）删除链表头部的节点。 修改头指针，使其指向待删除节点的后继节点。 （2）删除链表其他位置的节点。 ①确定待删除节点的前驱节点 prev 和后继节点 next。 ②修改前驱节点 prev 的_____________，使其与待删除节点的后继指针一致（若待删除节点在末尾，则节点 prev的后继指针就会为空）。 　后继指针 知识梳理 归纳提升 题型考法 2.在双向链表中删除节点 （1）删除链表头部的节点。 ①修改头指针指向，使其与待删除节点的后继指针一致。 ②修改新的头节点的前驱指针，使其指向为空。 知识梳理 归纳提升 题型考法 （2）删除链表中间位置的节点。 ①确定待删除节点的前驱节点 prev 和后继节点 next。 ②修改前驱节点 prev 的后继指针，使其与待删除节点的后继指针一致，指向 节点 next。 ③修改后继节点 next 的_____________，使其与待删除节点的前驱指针一致，指向节点 prev。 　前驱指针 知识梳理 归纳提升 题型考法 （3）删除链表尾部的节点。 修改待删除节点的前驱节点 prev 的后继指针，使其指向为空。 知识梳理 归纳提升 题型考法 判断正误，正确的画“√”，错误的画“×”。 1. 数组元素在内存中连续存储，链表元素可非连续存储，逻辑关系由指针描述。 （　　） 2. 链表插入操作只需修改指针，无须移动数据元素，因此时间复杂度始终为 O(1)。 （　　） 3. 单 向 链 表 遍 历 的 终 止 条 件 是 指 针 为 空（p! = -1），单向循环链表的终止条件是指针回到头节点（p!=head）。 （　　） 　√ 　× 　√ 知识梳理 归纳提升 题型考法 （1）相同点。 ①数组和链表都存储线性结构的数据。 ②同一个数组或是链表中存储的数据元素的数据类型必须相同。 （2）不同点。 ①数据的存储方式不同：数组元素在分配的内存中按下标顺序依 次存储，链表元素在内存中可以非顺序存储。 ②数据之间的逻辑关系表达不同：数组元素的排列顺序既表示数 据的存储结构，也表示数据的逻辑结构。链表元素的存储结构 与逻辑结构无关，数据之间的逻辑关系由节点间的指针链接和 描述。 知识梳理 题型考法 归纳提升 ③数据的存储空间不同：链表结构中，不仅数据元素本身要占用存储空间，而且指针也需要占用存储空间，链表结构比数组结构的空间开销大。 ④数据的操作不同。 知识梳理 题型考法 归纳提升 （1）链表的创建。 link=[["B",3],["D",-1],["A",0],["C",1]];head=2 #表示的是逻辑结构为 A→B→C→D 的单向链表，节点结构为：[节点数据,后继指针] link=[["A",-1,3],["D",2,4],["C",3,1],["B",0,2],["E",1,-1]];head=0 #表示的是逻辑结构为 A→B→C→D→E 的双向链表，节点结构为：[节点数据,前驱指针,后继指针] 知识梳理 题型考法 归纳提升 （2）链表节点的访问。 link=[["B",3],["D",-1],["A",0],["C",1]];head=2 p=head #初始化指针 while p!=-1: print(link[p][0]) #输出节点数据 p=link[p][1] #更新指针为后继指针 知识梳理 题型考法 归纳提升 （3）链表节点的插入。 link=[["B",3],["D",-1],["A",0],["C",1]];head=2 #将数据 X 插入到节点 A 和 B 的中间 new=["X",None] #存储 X 为新节点 new[1]=link[2][1] #修改新节点的指针与节点 A 一致 link.append(new) #将新节点添加到链表尾部 link[2][1]=len(link)-1 #修改节点 A 的指针指向新节点 知识梳理 题型考法 归纳提升 （4）链表节点的删除。 link=[["B",3],["D",-1],["A",0],["C",1]];head=2 #删除节点 C link[0][1]=link[3][1] #修改节点 B 的指针与节点 C 一致 知识梳理 题型考法 归纳提升 知识梳理 题型考法 归纳提升 考向 一 链表的概念 例 1 下列关于链表节点的说法，正确的是（　　） A.一个链表的头指针可以指向链表中任意一个节点 B.链表中每一个节点都有一个后继节点 C.指针链接链表节点，是一个链表的核心 D.链表的节点中只存放数据元素 C 例 1 C 链表的头指针是唯一的，指向其第一个节点，只有通过头指针才能进入链表。链表的尾节点没有后继节点，其指针域指向为空。链表的节点由数据域和指针域组成，分别存放数据元素和相邻节点的存储地址。 √ 知识梳理 归纳提升 题型考法 例 2 若在处理数据的过程中需要查找数据的前驱与后继，并对其进行频繁的增、删操作，则数据处理过程中使用的数据结构最合适的是 （　　） A.单向链表 B.双向链表 C.一维数组 D.二维数组 B 例 2 B 访问前驱和后继的情况下通常使用数组，但是题中又提到在数据处理的过程中需要对数据进行频繁的增、删操作，若仍使用数组则会导致操作步骤增加，工作量极大，且数据规模不稳定，所以在该场景中最适合的数据结构是双向链表。 √ 知识梳理 归纳提升 题型考法 考向 二 链表的 Python 实现 例 3 ［2025 杭州模拟］使用列表 d 模拟链表结构（节点数大于 2，且不存在连续为 0 的节点），每个节点包含数据区域和指针区域，h 为头指针。链表的头节点和尾节点数据区域的值均为 0，如图 a所示。现要把相邻两个数值为 0 的节点之间所有节点合并为一个节点，该节点值为所有合并节点值之和，并将值为 0 的节点移除，结果如图 b 所示。实现该功能的部分 Python 程序如下： 知识梳理 归纳提升 题型考法 k=h p=d[k][1] while k!=-1 and p!=-1: 　　　　　　　　　　　 p=d[k][1] 方框中应填入的正确代码为 （　　） B √ A.if d[p][0]!=0: d[k][0]+=d[p][0] d[k][1]=d[p][1] if d[p][0]==0: k=p B.if d[p][0]!=0: d[k][0]+=d[p][0] d[k][1]=d[p][1] if d[p][0]==0: k=d[k][1] C.if d[p][0]==0: k=p else: d[k][0]+=d[p][0] d[k][1]=d[p][1] D.if d[p][0]==0: k=d[k][1] else: d[k][0]+=d[p][0] d[k][1]=d[p][1] 知识梳理 归纳提升 题型考法 例 3 B 根据题意可知，链表的头节点和尾节点数据区域的值均为 0，因此，从第一个节点开始就需要将后继节点的值加入到当前头节点的数据域当中，并删除已经被加入的节点，而当下一次遇到值为 0 的节点时，已知最后一个节点也是值为 0 的节点，若按照如上的方案对后面值为 0 的节点进行操作，则最后一个值为 0 的节点无法被删除。因此，跳过第一个值为 0 的节点后，当遇到下一个值为 0 的节点时，直接跳过当前节点，以下一个节点作为当前 k 的节点，既保证了数据域的不丢失，也保证了删除数据域为 0 的节点。选项 A，当遇到值为 0 的节点时，k 移动到当前节点，但是当前节点在上一次的使用中已经被删除。选项 C、D，最后一个值为 0 的节点无法被删除。 知识梳理 归纳提升 题型考法 例 4 ［2024浙江选考］使用列表 d 模拟链表结构（节点数 n>0），如图 a 所示，每个节点包含数据区域和指针区域，h 为头指针。现要按链表顺序将 这 n 个 节点中的数 据依次存放到 d[0][0] 、d[1][0]…d[n-1][0]中，最终保持节点链接关系不变，结果如图 b所示。实现上述功能的 Python程序段如下， 知识梳理 归纳提升 题型考法 方框中应填入的正确代码为 （　　） p,i=h,0 while p!=-1: tp=d[p][1] if p==i: i+=1 elif p>i: d[i][0],d[p][0]=d[p][0],d[i][0] 　　　　　　　　　　　 i+=1 p=tp '''调整头指针 h 及指针区域，保持节点链接关系不变，代码略''' A.d[i][1]=d[p][1] B.d[p][1]=d[i][1] C.d[i][1]=p D.d[p][1]=i d[p][1]=i d[i][1]=p d[p][1]=d[i][1] d[i][1]=d[p][1] B 例 4 B　根据代码可知，当前节点为节点 p，p 从头节点开始进行遍历。变量 i 是从 0 开始顺序增加的，当 p 和 i 相等时，意味着该节点已经按链表顺序存放到 d 中的正确位置，因此不需要处理。当 p>i 时，需要修改数据的存放位置，即通过代码“d[i][0],d[p][0]=d[p][0],d[i][0]”将节点 i和节点 p 的数据区域进行交换，交换之后，剩余节点必须仍然按照原链表的顺序遍历，故还需要修改节点 p 的指针，指向节点 i 的后继，即 d[p][1]=d[i][1]，再修改节点 i 的指针，指向节点 p，即 d[i][1]=p。循环结束后，还需要修改头指针 h 的值，以及重新调整每个节点的指针区域。 √ 知识梳理 归纳提升 题型考法 考向 三 双向链表 例 5 双向链表可以实现逆序遍历，利用 Python列表来模拟双向链表的逆序遍历过程，其中子列表表示链表节点，子列表第一个元素表示节点的前驱指针，第二个元素表示节点中的数据，第三个元素表示节点的后继指针。实现该功能的 Python程序如下，请在划线处填入合适的代码。 a=[[4,5,1],[0,7,2],[1,9,-1],[-1,2,4],[3,4,0]] for i in range(len(a)): if a[i][2]==-1: #找到链表最后一个节点 print(a[i][1],end="→") #获取最后一个节点的前驱指针 pre=　　　①　　　 break while 　　　②　　　: #逆序遍历双向链表 if a[pre][0]!=-1: print(a[pre][1],end="→") else: print(a[pre][1]) pre=a[pre][0] a[i][0] pre!=-1 例 5 ①a[i][0] ②pre!=-1 ①为获取最后一个节点的前驱指针，并将其存储到变量pre中。在 for循环中，首先找到链表的最后一个节点 a[i]，该节点中第一个元素即该节点的前驱指针，故填入代码为 a[i][0]。② 处利用 while 循环对双向链表进行逆序遍历，遍历范围是整个链表，当遍历至链表第一个节点 ，即前驱指针指向为空的节点时结束遍历，所以while 循环的条件是前驱指针指向不为空，故填入代码为pre!=-1。 知识梳理 归纳提升 题型考法 考向 四 循环链表 例 6 有如下 Python 程序段： from random import * a=[["i", 4], ["n", 8], ["i", 5], ["B", 0], ["a", 1], ["n", 7],["Y",3],["g",6],["Q",2]] k=randint(1,4)*2+1 p=q=head=6 while k>0: p=a[p][1] k-=1 while p!=1: q=a[q][1] p=a[p][1] print(a[q][0]) 执行该程序段后，输出的结果不可能是 （　　） A.i B.g C.n D.a 例 6 D 本题考查循环链表的操作。 已知链表元素为"YBianQing"，k 可能的取值为 3、5、7、9。p 和 q 两个指针之间相差 k 个节点，且 q 在 p 之前，当 p 为 1 时，a[p][0]="n"（下一个节点为"Q"），输出 a[q][0]，故输出的结果可能是"B"、"g"、"i"、"n"。 D √ 知识梳理 归纳提升 题型考法 例 7 ［2025 金砖联盟］王老师正带领同学们在操场上玩趣味游戏：n 名同学（编号为 1~n）按编号由小到大的顺序顺时针围成一个圆圈，王老师先报出一个数 m（1~10 之间的整数），然后从编号为 1 的同学开始顺时针报数，报到 m 的同学出列；下一名同学又从 1 开始报数，报数为 m 的同学继续出列，以此类推，直到剩下一位同学为止。请回答下列问题： （1）当 n=10，m=3 时 ，最后剩下的同学编号是　　　　　　（填数字）。 （2）实现上述功能的 Python 程序如下，通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为 m 的节点，直到剩下一个节点为止。请在划线处填入合适的代码。 4 知识梳理 归纳提升 题型考法 n=int(input("请输入游戏人数：")) m=int(input("请输入 m 值：")) lst=[] for i in range(n-1): lst.append([i+1,i+1]) lst.append(　　　①　　　) head=len(lst)-1 p=head while n>1: for i in range(1,m): p=lst[p][1] out=lst[p][1] 　　　②　　　 n=n-1 print("最后剩下的同学编号是：",lst[p][0]) [n,0] lst[p][1]=lst[out][1] 知识梳理 归纳提升 题型考法 例 7 （1）4 （2）①[n,0] ②lst[p][1]=lst[out][1] （1）当 n=10，m=3 时，依次出列的同学编号是 3、6、9、2、7、1、8、5、10，最后剩下的同学编号是 4。 （2）①处添加编号为 n 的学生，其数据域为 n，指针域为 0，指向第一个学生节点，故填入代码为[n,0]。②指针 out 指向报数为 m的节点，指针 p 指向其前驱节点，删除 out节点，故填入代码为 lst[p][1]=lst[out][1]。 知识梳理 归纳提升 题型考法 考向 五 链表的应用 例 8 ［2025浙江 Z20联盟］小乐收集了近一年来学校贴吧的数据，准备将这些帖子按其收到的总点赞数从高到低进行排名，并统计哪些帖子是曾经的“热帖”。在任意连续的 d 天内（0~d-1 视为连续 d 天）总共收到不少于 k 个赞就称为“热帖”。最后输出这些“热帖”近一年来的总点赞数及其排名。请回答下列问题： （1）将贴吧的点赞数据经预处理后存入列表 a，存储格式为：a=[[t,id,c],…]，每个元素表示第 t天编号为 id 的帖子收到 c 个赞。若将“7 天内收到不少于 3 个赞”的帖子判定为“ 热帖 ”，则 当 a=[[0,0,2], [0,1,1], [0,2,1], [5,1,1], [7,1,2],[7,2,2],[10,3,2],[20,3,1]] 时 ，“ 热帖 ”编 号 为_____________。 1 知识梳理 归纳提升 题型考法 （2）定义如下 pm(q)函数，参数 q 的每个元素由 4个数据项组成，函数的功能是根据第 3 个数据项的值进行排名，值最大的为第 1 名，若值相同，则排名也相同，第 4 个数据项用于存放名次。例如，q=[[0,8,15,1], [1,6,20,1], [4,7,30,1],[6,9,20,1]]，调用 pm(q)后得到 q=[[0,8,15,4],[1,6,20,2],[4,7,30,1],[6,9,20,2]]。请在划线处填入合适的代码。 def pm(q): for i in range(len(q)): for j in range(len(q)): if q[j][2]>q[i][2]: 　　　　　　　 q[i][3]+=1 知识梳理 归纳提升 题型考法 （3）实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。'''读取 maxn 条帖子的数据，每条帖子有若干个点赞数据；读取 n 个点赞数据，存储在列表a 的 a[0]至 a[n-1]中，并根据 a[i] [0]的值进行升序排序；读取判定为“热帖”的连续时间长度 d 和点赞数 k，代码略''' f=[False]*maxn q=[[-1,-1,0,1] for i in range(maxn)] for i in range(n): a[i].append(-1) id=a[i][1] 　 ___________________① if f[id]: continue if q[id][0]==-1: q[id][0]=i if q[id][1]!=-1: a[q[id][1]][3]=i　 q[id][1]=i while q[id][0]!=-1 and ___________________②: q[id][0]=a[q[id][0]][3]　　 q[id][2]+=a[i][2] a[i][0]-a[q[id][0]][0]+1>d 或　a[q[id][1]][0]-a[q[id][0]][0]+1>d　 知识梳理 归纳提升 题型考法 cur=q[id][0] num=a[cur][2] while cur!=-1 : cur=a[cur][3] num+=a[cur][2] if num>=k: f[id]=True #标记为“热帖” pm(q) #对所有帖子的总点赞数进行排名 #输出“热帖”近一年来的总点赞数及其排名 for i in range(maxn): if f[i]: print("热帖编号为",i,"总点赞 数 为 ", q[i][2],"排名为",q[i][3]) （4）加框处的代码有误，应修改为______________________。 cur!=q[id][1] 或　a[cur][3]!=-1 知识梳理 归纳提升 题型考法 例8 （1）1 （2）q[i][3]+=1 （3）①q[id][2]+=a[i][2] ②a[i][0]-a[q[id][0]][0]+1>d　或　a[q[id][1]][0]-a[q[id][0]][0]+1>d　或其他等价答案　（4）cur!=q[id][1]或　a[cur][3]!=-1 （1）已知 a=[[0,0,2],[0,1,1],[0,2,1],[5,1,1],[7,1,2],[7,2,2],[10,3,2],[20,3,1]]，表示编号为 0 的帖子在 7 天内共收到 2 个赞，编号为 1 的帖子在 7 天内共收到 3 个赞，编号为 2 的帖子在 7 天内共收到 1 个赞，编号为 3 的帖子在 7 天内共收到 0 个赞，故“热帖”编号为 1。（2）pm(q)函数根据第 3个数据项的值计算排名，存放第 4 个数据项中，第 4 个数据项的初始值为 1。每次循环以 q[i]为基准，遍历所有元素 q[j]，计算所有 q[j][2]中大于 q[i][2]的个数，累加到 q[i][3]中，得到 q[i][3]为最终的排名，故填入代码为 q[i][3]+=1。 （3）①q[id][2]记录编号为 id 的帖子的总点赞数，由列表 a 中所有编号为 id 的帖子的点赞数累加得到，故填入代码为 q[id][2]+=a[i][2]。②已知列表 a 中的元素根据a[i][0]（天数）的值进行升序排序，列表 a 中每个元素都添加了一个 next 指针，将每个编号为 id 的帖子的元素通过链表连接起来， 知识梳理 归纳提升 题型考法 q[id][0]是该链表的头节点位置，q[id][1]是尾节点位置。当添加新的节点 i 时，将之前尾节点的 next 指针设为 i，然后将尾节点设为i。while 循环的作用是调整头节点，以确保时间长度不超过 d，故填入代码为 a[i][0]-a[q[id][0]][0]+1>d 或 a[q[id][1]][0]-a[q[id][0]][0]+1>d。 （4）加框处while 循环通过 cur遍历 d 天内编号为 id 的链表节点， 累加点赞数，cur 从头节点 q[id][0]开始，到尾节点 q[id][1]结束，循环内是跳到下一个节点累加点赞数，故正确代码为 cur!=q[id][1]或 a[cur][3]!=-1。 知识梳理 归纳提升 题型考法 THANK YOU $$