资源简介

(共64张PPT)
课时22 链表
一、链表的概念
1. 链表指的是将需要处理的数据对象以　　　　的形式，通过　　　　串联在一起的一种数据结构。链表的核心是使用指针链接节点。
2. 表头：每个链表拥有一个表头——head（也称头指针），有两个作用：
（1）作为链表的　　　　，只有通过头指针才能进入链表。
（2）为循环链表设立一个　　　　，便于数据处理时的边界判断和处理。
节点
入口
指针
边界
3. 节点：链表中的每个节点一般由“　　　　区域”和“　　　　区域”两部分构成。
（1）数据区域：用于保存　　　　需要处理的数据元素。
（2）指针区域：用来保存该节点　　　　的存储地址，通过该地址指向（指针）来实现从当前节点按顺序走到其相邻的节点。
（3）某个节点前面的相邻节点称为该节点的　　　　节点，后面的相邻节点称为该节点的　　　　节点。
4. 链表的分类。
（1）单向链表：只有　　　　个指针区域，指向该节点的后继节点。
（2）双向链表：有　　　　个指针区域，一个指向该节点的前驱节点，一个指向该节点的后继节点。
（3）循环链表：根据需要把链表　　　　节点和最后一个节点使用　　　　链接，就形成了循环链表。
数据
实际
指针
相邻节点
前驱
一
后继
两
第一个
指针
5. 单向链表的存储结构如图所示，单向链表中各个节点在内存中可以非顺序存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针 head，其他节点则需要经过所有在它之前的节点才可以访问，尾节点的指针指向为 null，表示指向为空。
1. 同一链表中每个节点的结构均相同。
（1）每个节点的数据区域中的　　　　 是相同的。
（2）每个节点指针区域中的指针　　　　 是相同的。
2. 每个链表必定有一个头指针，以实现对链表的引用和边界处理。
（1）访问链表中的某一节点，只能从头指针开始，通过　　　　链接依次访问，不能通过下标直接引用。
（2）对于循环链表，一轮访问的开始和结束都可以借助　　　　指向位置来进行判断，即边界处理。
数据类型
数量和功能
二、链表的特性
指针
头指针
3.链表占用的空间　　　　。
（1）链表的相邻节点存储时不需要连续空间，充分利用了内存的零散空间，提高了存储空间利用率。
（2）链表的存储空间由　　　　决定，增加或减少节点都会改变链表占用的存储空间，因此链表占用的空间不固定。
不固定
节点数
1.链表的创建。
（1）首先要根据问题特点规划节点的数据域和指针域。
（2）然后根据规划创建一个空链表。
（3）接下来就可以根据输入的实际数据形成节点并逐步插入已有的链表中。
2.链表节点的访问。
（1）链表只能通过头指针（head）进行访问。
（2）其他节点通过节点间的指针依次访问。
（3）与数组相比，链表节点的访问效率较低。
三、链表的基本操作
3.链表节点的插入与删除。
（1）链表节点的插入。
①链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的　　　　，将新节点插入到链表的正确位置。
②插入举例。
③插入过程。
情况 操作步骤
在空/非空单向链表头部插入节点 根据新输入的实际数据形成新节点；修改新节点的指针指向与头指针一致；修改头指针指向新节点
在非空单向链表其他位置插入新节点 根据新输入的实际数据形成新节点；修改新节点的指针指向与前驱节点的指针指向一致；将前驱节点的指针指向新节点
指针
（2）链表节点的删除。
①链表节点的删除，是通过将需要删除的节点的前驱节点和其后继节点　　　　的方式实现。
②删除举例。
③删除过程。
情况 操作步骤
删除链表第一个节点 修改头指针head指向该节点的后继节点
删除非空链表其他位置节点 修改该节点的前驱节点的指针与被删节点指针一致
直接相连
4.列表模拟实现链表操作。
（1）创建链表。
在 Python 中用一个子列表表示节点：[数据区域,指针区域]，用大列表存储所有的节点：[[数据 1,指针],[数据 2,指针],[数据 3,指针],[数据 4,指针]]，其中节点的指针指向其后继节点在大列表中的位置下标，若为尾节点，则指针区域值为-1。
（2）插入节点。
①首先使用 append()方法，将新节点添加到列表的尾部，这样不会影响其他节点的存储位置；然后修改新节点的指针值与其“目标前驱节点”的指针一致；最后修改“目标前驱节点”的指针值为新节点的位置下标。
②注意：若插入新节点作为链表的头节点，则将新节点添加到列表尾部，然后修改新节点的指针值与头指针一致，最后修改头指针的值为新节点的位置下标。
（3）删除节点。
①找到“待删除节点”的前驱节点，使前驱节点的指针指向与“待删除节点”的指针
指向一致即可。
②注意：若“待删除节点”是头节点，则直接将头指针修改为“待删除节点”的指针值。
5.链表的类实现。
（1）自定义单向链表的节点类，代码如下：
class LinkNode: #自定义节点类 LinkNode
def __init__(self,data,next_=None):
#初始化节点包含两个区域 self.data、self.next_
self.data=data #self.data 区域保存数据
self.next_=next_ #self.next_区域保存指针
（2）构造单向链表类，代码如下：
class LinkList: #自定义单向链表类 LinkList
def __init__(self): #初始化空链表
self._head=None #空链表头指针指向为空
（3）有了以上类的构造，就可以创建单向链表并进行空表判断、增删节点等基本操作。使用自定义类的方式建立的单向链表可以充分体现链表的特性。
典例 1 下列关于链表的说法，正确的是（　　）
A.只有单向链表才能形成循环链表
B.通过链表中的任意一个节点能够访问到完整的链表
C.链表中的数据无须存储在连续的存储空间内
D.在对链表进行操作的过程中可以根据需要增加或删除某个节点的指针
C
√
题型导向一　链表的特性
胜券点拨1
明考向 本题主要考查链表的相关知识
审关键 链表的概念和特性
考场思维快闪 A 单向链表和双向链表都能形成循环链表
B 只有通过链表的头指针才能访问到完整的链表
C 链表通过节点间的指针相连，相邻节点存储时不需要连续空间
D 同一个链表中每个节点的结构必须相同，在数据操作的过程中仅能够修改指针域的值，而不能对某个节点的指针域的数量或功能进行修改
画线处应填入的代码为 （　　）
A.①link[p][0]==key and p!=-1 ②link[q][1]=p
B.①link[p][0]!=key and p!=-1 ②link[q][1]=p
C.①link[p][0]==key and p!=-1
②link[q][1]=link[p][1]
D.①link[p][0]!=key and p!=-1
②link[q][1]=link[p][1]
典例 2 ［2025 强基联盟］有如下 Python 程序段，其功能是在降序链表中删除数据为 key 的所有节点，链表 link 中每个节点由一个数据域和一个指针域组成。
#建立链表 link，代码略
head=0
key=int(input("输入要删除的数据："))
t=q=head
while link[t][0]!=key and t!=-1:
q=t;t=link[t][1]
p=t
while 　　　①　　　:
p=link[p][1]
if t==head:
head=p
else:
　　　②　　　1
A
√
题型导向二　链表节点的访问、插入和删除
胜券点拨2
明考向 本题主要考查链表的操作
审关键 链表节点的删除
考场思 维快闪 要求在降序链表中删除数据为key的所有节点，第一个while语句遍历链表link找到第一个数据域为key的节点（或确认没有这样的节点），第二个while语句从该节点开始遍历链表link，找到第一个数据域非key的节点，然后删除这之间的所有节点。①若当前节点的数据域等于key并且当前节点不是链表末尾节点，则查找下一节点，故填入代码为link[p][0]==key and p!=-1。②q为第一个数据域为key的节点的前驱节点，p为q之后第一个数据域非key的节点，删除这之间的所有节点，即将q的后继指针指向p，故填入代码为link[q][1]=p
典例 3 [2025.6浙江选考］有如下Python程序段：
tag=[0]*len(data)
p=i=0
while iif tag[p]==0 and data[p][1]!=-1:
tag[i]+=1
p=data[p][1]
else:
tag[i]+=tag[p]
i+=1
p=i
若data为[[11,3],[23,-1],[15,0],[26,1],[63,2]]，运行该程序段后，tag[4]的值为 （　　）
A.1 B.2
C.3 D.4
D
√
胜券点拨3
明考向 本题主要考查链表
审关键 链表的遍历
考场思维快闪 该程序段遍历链表data，使用tag[i]记录从节点i开始遍历的路径长度。若当前节点未访问且有后继，则当前路径长度增加1（tag[i]+=1），然后移动到后继节点（p=data[p][1]）；若当前节点已访问，则累加已计算的路径长度（tag[i]+=tag[p]），然后移动到下一个起始节点（i+=1;p=i）
典例 4 ［2025嵊州联考］列表 a 存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为 ha、hb，且 a[ha][0]p=h=ha;q=a[ha][1]
r=hb;lst=[]
while p!=-1:
lst.append(a[p][0]) #添加一个元素到 lst 中
p=a[p][1]
p=h
while q!=-1 and r!=-1:
if a[r][0] not in lst:
if a[q][0]p=q;q=a[q][1]
else:
　　　　　　　
else:
r=a[r][1]
if r!=-1:a[p][1]=r
D
√
A.a[q][1]=r B.a[q][1]=r C.a[p][1]=r D.a[p][1]=r
q=r r=a[q][1] r=a[p][1] p=r
r=a[q][1] q=r p=r r=a[p][1]
a[q][1]=p a[q][1]=p a[q][1]=p a[p][1]=q
胜券点拨4
明考向 本题主要考查链表的操作
审关键 链表的合并、去重
考场思 维快闪 列表lst在第一个循环中存储了链表ha的所有节点数据。指针p和q分别为链表ha的相邻节点的指针，指针r遍历链表hb。当链表hb中节点r的数据不在列表lst中时（a[r][0] not in lst），需要插入到链表ha中，若节点r的数据大于节点q的数据（a[q][0]典例 5 ［2024.6 浙江选考］使用列表 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 及指针区域，保持节点链接关系不变，代码略'''
B
√
A.d[i][1]=d[p][1] B.d[p][1]=d[i][1]
d[p][1]=i d[i][1]=p
题型导向三　链表节点的重排与指针维护
C.d[i][1]=p D.d[p][1]=i
d[p][1]=d[i][1] d[i][1]=d[p][1]
胜券点拨5
明考向 本题主要考查链表的操作
审关键 节点链接关系不变
考场思 维快闪 根据代码可知，当前节点为节点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的后继，再修改节点i的指针，指向节点p。循环结束后，还需要修改头指针h的值，以及重新调整每个节点的指针区域
典例 6 ［2024.1 浙江选考］使用列表 d 模拟链表结构（节点数大于 0），每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图 a 所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图 b 所示。实现该功能的程序段如下，方框中应填入的正确代码为 （　　）
t=h
p=d[h][1]
while p!=-1:
q=d[p][1]
　　　　　　　
p=q
d[t][1]=-1
A.if d[p][0]>0: B.if d[p][0]>0: C.if d[p][0]>0: D.if d[p][0]>0:
d[q][1]=p d[t][1]=q d[t][1]=p d[t][1]=q
d[t][1]=q t=q t=p d[q][1]=p
else: else: else: else:
d[h][1]=q h=p d[p][1]=h d[p][1]=h
h=p d[p][1]=t h=p h=q
C
√
胜券点拨6
明考向 本题主要考查链表的操作
审关键 绝对值由小到大排列
考场思 维快闪 分析代码可知，h为链表头指针，t指向p的前驱节点，q指向p的后继节点。理解算法实现排序的方法，链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a中的示例：-11、14、16、17、-18，若要各节点按数据区域中的数值由小到大排列，则需依次访问每个元素，若元素值为负数，则插入到链表的头部，即p节点的指针指向原头节点，原头指针h指向新的头节点p；若元素值为正数，则原链表节点关系不变，各节点关系往下迭代即可，即t变为p，p变为q
典例 7 王老师正带领同学们在操场上玩趣味游戏：n 名同学（编号为 1~n）按编号由小到大的顺序顺时针围成一个圆圈，王老师先报出一个数 m（1~10 之间的整数），然后从编号为 1 的同学开始顺时针报数，报到 m 的同学出列；下一名同学又从 1 开始报数，报到 m 的同学继续出列，以此类推，直到剩下一位同学为止。如下 Python 程序通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为 m 的节点，直到剩下一个节点为止，请在画线处填入合适的代码。
n=int(input("请输入游戏人数："))
m=int(input("请输入 m 的值："))
lst=[]
for i in range(n-1):
lst.append([i+1,i+1])
lst.append(　　　①　　　)
[n,0]
head=len(lst)-1
p=head
while n>1:
for i in range(1,m):
p=lst[p][1]
out=lst[p][1]
　　　②　　　1
n=n-1
print("最后剩下的同学编号是：",lst[p][0])
lst[p][1]=lst[out][1]
题型导向四　循环链表
胜券点拨7
明考向 本题主要考查循环链表的操作
审关键 单向循环链表的构建、链表节点的删除
考场思维快闪 ① 添加编号为n的学生，其数据域为n，指针域为0，指向编号为1的学生，故填入代码为[n,0]
② 指针out指向报数为m的节点，指针p指向其前驱节点，要删除out节点，应修改out的前驱节点的指针与out的指针一致，故填入代码为lst[p][1]=lst[out][1]
head=len(a)
a.append(new)
break
#若插入位置是链表中间
elif a[cur][0]<=new_data and a[a[cur][2]] [0]>new_data:
new[1]=cur
new[2]=a[cur][2]
　　　②　　　=len(a)
a[cur][2]=len(a)
a.append(new)
break
#若插入位置是链表尾部
elif 　　　③　　　 and a[cur][0]<=new_ data:
new[1]=cur
new[2]=-1
a[cur][2]=len(a)
a.append(new)
break
cur=a[cur][2]
print(a)
典例 8 有如下 Python 程序段，实现向一个升序排序的双向链表中插入节点的操作，链表节点中第一个数据表示节点中实际存放的数据，第二个数据为前驱指针，指向该节点的前驱节点，第三个数据为后继指针，指向该节点的后继节点。请在画线处填入合适的代码。
a=[[10,2,5],[2,-1,3],[9,4,0],[3,1,4],[7,3,2], [15,0,-1]]
head=1
new_data=int(input("输入要插入的新数据："))
#创建新节点，指针域使用初始值 0 占位
new=[new_data,0,0]
cur=head
'''通过头指针 head 进入链表，cur 变量表示当前遍历的位置'''
while cur!=-1:
#若插入位置是链表头部
if cur==head and a[cur][0]>new_data:
new[1]=　　　①　　　1
new[2]=head
a[cur][1]=len(a)
-1
a[a[cur][2]][1]
a[cur][2]==-1
题型导向五　双向链表
胜券点拨8
明考向 本题主要考查使用Python解决链表操作问题
审关键 链表的Python表示、链表的数据插入操作
考场思维快闪 ① 当新数据的插入位置是链表头部时，新节点无前驱，则设置它的前驱指针的值为-1
② 已知新节点new添加在列表末尾，即索引值为len(a)的位置上，所以先修改新节点的后继节点a[a[cur][2]]的前驱指针a[a[cur][2]][1]的值为len(a)，再修改新节点的前驱节点a[cur]的后继指针a[cur][2]的值为len(a)，这里顺序不可变，若先修改a[cur][2]为len(a)，则会丢失新节点的后继节点的位置
③ 当新数据的插入位置是链表尾部时，即当前节点的数据值小于new_data且为尾节点，应判断节点a[cur]是否是尾节点，即是否无后继，故填入代码为a[cur][2]==-1
异同 链表 数组
存储的数据特点 存储线性排列的且数据类型相同的数据
数据的访问 通过头指针进入链表，其他节点通过节点间的指针依次访问 通过数组名和下标对数组任意位置的元素进行访问
数据插入 不要求新节点的存储位置，只需要通过修改指针即可实现数据的插入 需要先将待插入位置的元素及其之后的元素后移一位，空出该位置之后再插入新数据
数据删除 通过修改指针实现节点的删除 先删除某个元素，再依次将其之后的元素前移一位
通法一　链表与数组辨析
1.链表的创建。
item=[]
head=-1 #head 值为-1，表示头指针指向为空，该链表为空链表
2.使用 Python 列表定义一个单向链表：6→1→5→9→8→3。
通法二　Python列表模拟链表的操作
4.链表节点的遍历。
head=2
a=[[4,1],[6,3],[2,0],[8,4],[9,-1]]
while head!=-1:
if a[head][1]==-1:
print(a[head][0])
else:
print(a[head][0],end="→")
head=a[head][1]
#输出：2→4→6→8→9
5.链表节点的插入。
（1）在单向链表的中间插入节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
newdata1=[5,-1] #待插入节点
#将新节点插入到数据 7 的节点后面
pre=head
while pre!=-1:
if a[pre][0]==7:
newdata1[1]=a[pre][1]
a.append(newdata1)
a[pre][1]=len(a)-1
break
else:
pre=a[pre][1]
print(a) #输出：[[6,2],[2,-1],[3,3],[7,5],[9,1],[5,4]]
（2）在单向链表的头部插入节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
newdata2=[1,-1] #待插入节点
#将新节点插入到头节点前面
newdata2[1]=head
a.append(newdata2)
head=len(a)-1
print(a) #输出：[[6,2],[2,-1],[3,3],[7,4],[9,1],[1,0]]
print(head) #输出：5
（3）在单向链表的尾部插入节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
newdata3=[8,-1] #待插入节点
#将新节点插入到链表的尾部
pre=head
while pre!=-1:
if a[pre][1]==-1:
newdata3[1]=a[pre][1]
a.append(newdata3)
a[pre][1]=len(a)-1
break
else:
pre=a[pre][1]
print(a) #输出：[[6,2],[2,5],[3,3],[7,4],[9,1],[8,-1]]
6.链表节点的删除。
（1）删除单向链表的中间节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
#删除数据 7 的节点
pre=head
while a[pre][1]!=-1:
if a[a[pre][1]][0]==7:
a[pre][1]=a[a[pre][1]][1]
break
else:
pre=a[pre][1]
print(a) #输出：[[6,2],[2,-1],[3,4],[7,4],[9,1]]
（2）删除单向链表的头节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
#删除头节点
head=a[head][1]
print(a) #输出：[[6,2],[2,-1],[3,3],[7,4],[9,1]]
print(head) #输出：2
（3）删除单向链表的尾节点。
#表示链表：6→3→7→9→2
a=[[6,2],[2,-1],[3,3],[7,4],[9,1]]
head=0
#删除尾节点
pre=head
while a[a[pre][1]][1]!=-1:
pre=a[pre][1]
a[pre][1]=-1
print(a) #输出：[[6,2],[2,-1],[3,3],[7,4],[9,-1]]
1.单向链表与单向循环链表。
2.双向链表与双向循环链表。
结构 尾节点 遍历一次的循环结束条件
单向链表 指针域为空 p!=-1
单向循环链表 指针域值为head，指向第一个节点 p!=head
结构 头节点 尾节点
双向链表 前驱指针为空 后继指针为空
双向循环链表 前驱指针指向最后一个节点 后继指针指向第一个节点
通法三　循环链表
1.下列关于链表的说法，不正确的是 （　　）
A.链表占用的存储空间不固定
B.链表中不一定有头指针
C.链表的节点由数据区域和指针区域两部分组成
D.在链表中插入一个节点，只需要修改部分节点的指针
链表中一定要有头指针，用于进入链表以及作为循环链表的边界。
一、链表的特性
B　
√
2.使用列表a模拟链表结构（节点数n>0），每个节点包含数据区域和指针区域，head为头指针。编写Python程序删除链表的头节点并将其重新插入到链表末尾，部分代码如下：
p=head
while a[p][1]!=-1:
　p=a[p][1]
　　　　　　　
有如下可选语句：
①a[a[p][1]][1]=-1　 ②a[head][1]=-1
③a[p][1]=head　 ④head=a[head][1]
则方框中应填入的语句依次为 （　　）
A.①③④ B.③④②
C.③④① D.③②④
通过while循环找到链表尾节点为p，先将尾节点的指针指向头节点，即a[p][1]=head；然后修改头节点为原头节点的后继节点，即head=a[head]；最后将原头节点（现在是原尾节点的后继节点）设为尾节点，即指针设为-1，即a[a[p][1]][1]=-1。
二、链表节点的访问、插入和删除
C
√
3.［2025杭州联考］节点数均大于0的两个链表a与b，每个节点包含数据区域和指针区域，ha和hb分别为链表a和b的头指针，链表中各节点已按数据区域中数值大小升序排序，且a[ha][0]ha=hb=0
q=ha
while hb!=-1:
　　　　（1） 　　　
　if p==-1 or a[p][0]>b[hb][0]:
　　a.append([b[hb][0],p])
　　a[q][1]=len(a)-1
　　　　　（2） 　　　
　　　　（3） 　　　
上述程序中画线处有如下可选语句：
①q=a[q][1]　②p=a[q][1]　③hb=b[hb][1]
则画线（1）（2）（3）处应填入的语句依次是 （　　）
A.③①② B.①③② C.②③① D.②①③
q遍历链表a中的节点，hb遍历链表b中的节点，p为q的后继节点（p=a[q][1]），若a[p][0]>b[hb][0]，则将数据b[hb][0]插入到链表a中节点q与p之间，然后hb指向链表b的下一个节点（hb=b[hb][1]）。然后q指向链表a的下一个节点（q=a[q][1]），继续下一轮循环。
C
√
4.对非空链表进行反转操作。该链表存储在列表d中，初始状态如图a所示，反转状态如图b所示。每个节点由数据区域和指针区域组成，h为头指针。实现上述功能的Python自定义函数如下，方框中应填入的正确代码为 （　　）
def revlst(d,h):
　p=d[h][1]
　d[h][1]=-1
　while p!=-1:
　　　　　　　　　
　return d,h
A
√
第一步，读取头节点的后继节点位置（p=d[h][1]），反转后头节点将变成新链表的尾节点，所以将头节点的指针区域值设为-1（d[h][1]=-1）。第二步，依次处理剩余节点，非尾节点的处理方法是，先获取当前节点p的后继节点位置（r=d[p][1]）；再将当前节点的指针区域值修改为其前驱节点位置（d[p][1]=h）；h指向当前节点p（h=p）；读取下一个节点进行处理（p=r）。
三、链表节点的重排与指针维护
A.r=d[p][1] 　d[p][1]=h 　h=p 　p=r B.r=d[p][1]
　p=r
　h=p
　d[p][1]=h
C.r=d[p][1] 　d[p][1]=h 　p=r 　h=p D.p=d[p][1]
　h=p
　r=d[p][1]
　p=r
5.设双向链表的某中间节点p由一个一维数组表示，其中k[p][1]和k[p][2]分别是该节点的前驱和后继。现要求从该链表中删除节点p，则下列代码正确的是 （　　）
A.k[p][1][2]=k[p][2]
　k[p][2][1]=k[p][1]
B.k[k[p][1]][2]=k[p][2]
　k[k[p][2]][1]=k[p][1]
C.k[p][2][2]=k[p][1]
　k[p][1][1]=k[p][2]
D.k[k[p][2]][2]=k[p][1]
　k[k[p][1]][1]=k[p][2]
已知中间节点p的前驱节点为k[p][1]，后继节点为k[p][2]，若删除节点p，则需要将k[p][1]的后继指针指向k[p][2]，将k[p][2]的前驱指针指向k[p][1]。
四、双向链表
B
√
6.［2026浙南名校联盟］使用列表d模拟链表结构，头指针为head，每个节点包含数据区域（0~9的整数）和指针区域。链表的节点按逆序存储为一个非负整数，例如，链表3→2→1表示数值123。现需要将该数值加c（0≤c≤9），并将结果以同样的链表结构存储，头指针仍为head。实现该功能的Python程序段如下：
c=int(input())
head=0;p=head
prev=-1
while p!=-1:
　d[p][0]+=c
　c=d[p][0]//10
　d[p][0]%=10
　prev=p;p=d[p][1]
if c>0:
　　　　　　　　
A.d.append([c,prev]) 　d[prev][1]=len(d)-1 B.d.append([c,head])
　head=len(d)-1
C.d.append([c,p]) 　d[prev][1]=len(d)-1 D.d.append([c,-1])
　head=len(d)-1
方框中应填入的正确代码是 (　　)
while循环实现从头节点开始，给当前节点数据加上c，p指向当前节点，prev指向p的前一个节点，当节点数据超出10时，将往前进位。若while循环结束后，c的值仍大于0，说明需要在链表末尾插入一个节点存放进位，待插入节点的数据为c，指针为p（即-1），对应语句d.append([c,p])或d.append([c,-1])，然后将前一个节点的指针修改该为该节点的位置，对应语句d[prev][1]=len(d)-1。
C
√
7.给定一个链表a，以表头元素为基准，将小于基准的节点移动到它的左侧，并且保持节点相对顺序不变，大于基准的节点则保持不动。如图a所示的链表处理后的结果如图b所示。实现该功能的程序段如下，head为头指针，方框中应填入的正确代码是 （　　）
tmp=a[head][0]
p,r=head,-1
while a[p][1]!=-1:
　q=a[p][1]
　if a[q][0]　　a[p][1]=a[q][1]
　　 　　　　　　　
　　r=q
　else:
　　p=a[p][1]
D
√
A.if r==-1: 　　a[q][1]=p 　　head=q 　else: 　　a[r][1]=a[q][1] 　　a[q][1]=r B.if r==-1:
　　a[p][1]=q
　　head=q
　else:
　　a[r][1]=a[p][1]
　　a[q][1]=r
C.if r==-1: 　　a[p][1]=q 　　head=q 　else: 　　a[q][1]=a[r][1] 　　a[r][1]=q D.if r==-1:
　　a[q][1]=head
　　head=q
　else:
　　a[q][1]=a[r][1]
　　a[r][1]=q
变量p、q分别标记链表中相邻的两个节点。遍历链表a，若节点q的数据小于基准tmp，则将其从原位置移除（a[p][1]=a[q][1]），然后插入到tmp左侧链表的末尾。若左侧链表为空（r==-1），则将q设为新的头节点，并指向原头节点（a[q][1]=head;head=q）；若左侧链表非空，则将q插入到末尾节点r的后面（a[q][1]=a[r][1];a[r][1]=q）。
8.［2026.1浙江选考］某中转站负责转运物品，每个物品规格相同且有唯一的正整数编号，物品送达中转站的时间先后与编号大小无关，每次运走的物品编号均需连续。
　　将中转站中的现有物品编号划分为若干序列，连续的编号按升序置于同一序列，不连续的编号置于不同序列。当需要运走x个物品时，检查当前时间现有序列中是否存在长度≥x的序列，若存在，则：
　　①选择长度最短的序列；若最短序列有多个，则选择起始编号最小的序列。
　　②选定序列后，运走从其起始编号开始的x个连续编号的物品。
若不存在符合条件的序列，则本次需求取消。请回答下列问题：
（1）若物品按如图所示的时间送达中转站，第一次需要运走的物品个数为3，时间为09:15，则该次运走物品的起始编号为　　　。
206
时间 08:15 08:20 08:30 08:55 09:00 09:05 09:10 09:25
编号 202 206 203 201 208 207 204 205
（1）在09:15时，送达中转站的物品编号有202，206，203，201，208，207，204，将连续的编号按升序置于同一序列，得到序列201，202，203，204和序列206，207，208。若需要运走的物品个数为3，则选择长度大于等于3的序列中长度最短的序列，即序列206，207，208，起始编号为206。
（2）定义如下函数check(reqs,m)，用于判断列表reqs中是否存在下列情况：任意连续60分钟内，需要运走的物品数量总和超过m。列表reqs中的每个元素包含两个数据项，依次为需要运走的时间（已转换为分钟数）和物品数量，已按时间升序排列。
def check(reqs,m):
　i=j=0
　s=0
　while j　　if reqs[j][0]-reqs[i][0]<60:
　　　s+=reqs[j][1]
　　　if s>m:
　　　　return True
　　　j+=1
　　else:
　　　s-=reqs[i][1]
　　　i+=1
　return False
True
调用该函数，请回答①和②两个问题。
①若reqs为[[6,1],[19,13],[35,3],
[70,2],[75,7]]，m为20，则返回值为 　　　　　。
②若reqs的长度为100，函数返回值为False，则while语句中循环体的执行次数最多是　　　　　　　次。
199
　（2）①在给出的reqs中，[19,13],[35,3],[70,2],[75,7]的时间差为75-19=56<60，而物品总数为13+3+2+7=25>m，因此返回True。②函数check构造了一个滑动窗口，指针i指向窗口的起点，指针j指向窗口的终点，每次检查起点和终点的时间差是否在60以内：若在60以内，则统计窗口内的物品总数s，并判断s是否大于m，然后指针j后移；若不在60以内，即超过窗口大小，则将指针i后移，并减去指针i对应的物品数量。因此，while语句中循环体的执行次数，等价于指针i和指针j的移动次数。循环中若s大于m，则会提前退出循环，因此考虑没有提前退出循环的情况，即当j为100时退出循环，j移动了100次（从0到100）。指针i只有在窗口两端时间差大于等于60时才移动，因此考虑每两个时间差都大于等于60的情况，即i移动了99次（从0到99）。故while语句中循环体的执行次数最多是100+99=199次。
（3）中转站需逐条处理需求信息，根据物品的送达时间和编号，以及需要运走的时间和数量，记录成功运走的物品编号，模拟上述过程的Python程序如下，请在画线处填入合适的代码。
def addpid(pid,lst):
　'''
　该函数根据新加入的物品编号pid更新链表。
　列表lst模拟链表结构，链表节点的前两个数据项依次为连续编号序列的起始和终
　止编号，第三个数据项为指针。lst[0]为链表的头节点（前两个数据项不存储有
　效数据），其余节点在链表中按起始编号升序排列，连续编号序列存于同一节点。
　例如：若pid为19，lst为[[-1,-1,2],[15,18,3],[11,13,1],[20,22,-1]]，调用
　addpid(pid,lst)后，lst为[[-1,-1,2],[15,22,-1],[11,13,1],[20,22,-1]]
　'''
　#代码略
def proc(reqs,items):
　res=[]
　#初始化为仅包含头节点的链表
　lst=[[-1,-1,-1]]
　idx=0
　for i in range(len(reqs)):
　　cur,need=reqs[i][0],reqs[i][1]
　　while idx　　　pid=items[idx][1]
　　　'''根据新加入的物品编号pid更新链表'''
　　　addpid(pid,lst)
　　　　　　①
　　bestnum=len(items)+1
　　bestpre,pre=-1,0
　　p=lst[0][2]
①idx+=1
　　while p!=-1 and need!=bestnum:
　　　num=lst[p][1]-lst[p][0]+1
　　　if 　　　②　　　:
　　　　bestnum=num
　　　　bestpre=pre
　　　pre=p
　　　p=lst[p][2]
　　if bestpre!=-1:
　　　p=lst[bestpre][2]
　　　#为res追加一个元素
　　　res.append([i,lst[p][0],lst[p][0]+need-1])
　　　if bestnum==need:
　　　　lst[bestpre][2]=lst[p][2]
②need<=num　　　else:
　　　　　　　　③ 　　　
　　else:
　　　#取消本次需求，代码略
　return res
'''
将物品信息存入items列表，每个元素包含两个数据项，依次为物品送达时间和编号；
将需求信息存入reqs列表，每个元素包含两个数据项，依次为需要运走的时间和数量；
两个列表均已按时间升序排列。
代码略
'''
res=proc(reqs,items)
#输出res列表中的处理结果，代码略
③lst[p][0]+=need
①idx+=1　②need<=num（3）①使用变量idx遍历所有物品信息，将要加入运送的物品编号添加到链表中，因此每次循环idx要后移1位，故填入代码为idx+=1。②变量bestnum记录当前最优序列长度，根据题干要求，应选择长度大于等于需求数量need的序列中长度最短的序列，当前序列长度为num，因此若num大于等于need且小于bestnum，则更新bestnum，故填入代码为need<=num9.[2023.6浙江选考]某工程包含n个任务（编号为0～n-1），每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2，即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。
　　现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
　　根据每个任务完成所需的天数和梳理后的依赖关系，
编写程序，首先删除标记为“F”的依赖关系，然后计算
工程最快完成所需的天数，并以工程最快完成所需的天
数为期限，计算每个任务最晚必须开始的时间。
请回答下列问题：
（1）若某工程有6个任务，任务间依赖关系如图a所示，
完成任务0～5所需天数分别为2,1,3,5,1,6，则工程最
快完成需要　　　　天。
8
（1）根据图示，可以整理出3条任务链，分别为：任务2→任务1→任务4、任务3、任务5→任务0。完成这三条任务链所需的天数分别是：3+1+1=5天、5天、6+2=8天，由于每天可以同时进行多个任务，则完成所有任务所需的天数即是所有任务链中的最大时长，即8天。
（2）定义如下erase(lst)函数，参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系，返回保留的依赖关系的个数。
def erase(lst):
　i=0
　j=len(lst)-1
　while i<=j:
　　if lst[i][2]=='T':
　　　i+=1
　　else:
　　　if lst[j][2]=='T':
　　　　lst[i]=lst[j]
　　　　i+=1
　　　j-=1
　return i
若lst列表依次存储如图b所示的依赖关系，如lst[0]为[0,5,'T']，调用erase(lst)函数，则语句“lst[i]=lst[j]”的执行次数为　　　　　　　。
1
（2）函数中使用双指针算法，指针i从前往后遍历，指针j从后往前遍历。用覆盖的方式实现删除功能，即当lst[i][2]值为“F”，lst[j][2]值为“T”时，用lst[j]将lst[i]覆盖，实现将 lst[i]删除的功能。程序执行过程如表所示，故语句“lst[i]=lst[j]”执行1次。
i j lst[i][2] lst[j][2] lst[i]=lst[j]是否执行
0 4 T F 否
1 4 F F 否
1 3 F T 是
2 2 T T 否
3 2 结束循环
（3）实现上述功能的部分Python程序如下，请在画线处填入合适的代码。
def proc(n,lst,task):
　pr=[0]*n
　#w[i]存放任务i最晚必须开始的时间
　w=[0]*n
　m=erase(lst)
　for i in 　　　①　　　:
　　task[lst[i][1]][1]=lst[i][0]
　　pr[lst[i][0]]=1
　c=[]
　#days存放工程最快完成所需的天数
　days=0
①range(m)　或　range(m-1,-1,-1)　或其他等价答案
　for i in range(n):
　　if pr[i]==0:
　　　k=i
　　　s=0
　　　while k!=-1:
　　　　c.append(k)
　　　　s+=task[k][0]
　　　　　　　② 　　　
　　　if s>days:
　　　　days=s
　for i in range(n-1,-1,-1):
　　k=c[i]
　　if task[k][1]==-1:
　　　w[k]=days-task[k][0]+1
　　else:
　　　　　　③
②k=task[k][1]　或其他等价答案
③w[k]=w[task[k][1]]-task[k][0]　
或　w[k]=w[c[i+1]]-task[k][0]　
或其他等价答案
　'''输出days，以及保存在w中的每个任务最晚必须开始的时间，代码略'''
'''
工程包含的任务数存入变量n
任务间的依赖关系存入lst列表
lst[i]包含3项，任务lst[i][0]依赖于任务lst[i][1]，lst[i][2]存放保留/删除标记，任务数据存入task列表
task[i]包含2项，task[i][0]为完成任务i所需天数，task[i][1]的初值为-1
代码略
'''
proc(n,lst,task)
（3）首先分析各变量所表示的意义。lst存储任务之间的依赖关系，task是一个存储任务数据的列表，表示包含n个任务的任务数据。对于每个任务，task[i][0]表示任务i完成所需的天数，task[i][1]表示任务i的依赖任务（任务链中i的后续任务）索引。如果任务i没有依赖任务，则task[i][1]的值为-1。理清代码的功能框架可以帮助我们更好地理解代码，根据整体可整理出代码框架如下：
①range(m)　或　range(m-1,-1,-1)　或其他等价答案　②k=task[k][1]　或其他等价答案　③w[k]=w[task[k][1]]-task[k][0]　或　w[k]=w[c[i+1]]-task[k][0]　或其他等价答案　
定义并初始化任务数据：
长度为n的数组pr，初始值设为0，用于标记任务状态。
长度为n的二维列表task，存储每个任务的耗时和依赖关系。（task[i][0]表示任务i完成所需的天数；task[i][1]表示任务i的依赖任务索引）
循环一：创建任务链task
更新任务状态pr
循环二：得到工程最快完成所需的天数
循环三：计算每个任务最晚必须开始的时间
①处循环（循环一）用于处理任务依赖关系列表lst，遍历其中的每个有效依赖关系，个数存储在变量m中。对于每个依赖关系，将其添加到任务数据列表task中，更新任务的开始时间和状态。故i在lst中循环的范围是0～m-1，填入代码为range(m)。②处所在循环（循环二）处理任务之间的依赖关系，追溯该任务链，计算完成任务链中所有任务的总耗时。起始任务的索引为当前任务的索引，然后通过task[k][1]获取该任务的依赖任务索引（类似链表指针），直到依赖任务索引为-1（即没有依赖任务）为止。此处k是一个临时变量，用于追踪任务链的索引，迭代过程中，需要将k更新为该依赖任务索引，以继续追溯任务链，故填入代码为k=stack[k][1]。③处所在循环（循环三）用于计算每个任务的最晚必须开始时间，存储在数组w中。根据任务的依赖关系链反向追溯，如果任务没有后续依赖任务（即task[k][1]==-1），则任务的最晚必须开始时间为工程最快完成所需的天数（days）减去当前任务的耗时（task[k][0]），再加1。否则如果任务有后续依赖任务，则任务的最晚必须开始时间被设置为后续依赖任务的最晚必须开始时间（w[task[k][1]]）减去当前任务的耗时task[k][0]。故填入代码为w[k]=w[task[k][1]]-task[k][0]。
10.［2025.1浙江选考］某市举行体育赛事活动，n所学校的选手已完成预赛，现计划根据预赛的成绩挑选s名选手参加市决赛。成绩位列所在学校前w名次的选手直接入选，剩余名额按成绩由高到低依次挑选，成绩相同的选手一并入选，选中的选手数一旦达到或超过s名，挑选结束。
　　现给定所有选手预赛的成绩数据表，每位选手的数据包含学校编号（0~n-1）、选手编号、成绩，成绩数据表已按成绩由高到低排列。编写程序，计算各选手的校内名次，再按上述规则挑选决赛选手，按成绩数据表中的顺序输出选手编号，同时提供查询功能。选手校内名次的计算方法是：若选手所在学校有m人成绩高于该选手，则该选手的名次为m+1。
　　在如图所示的样例中，n、s、w分别为3、8、2，根据图中前3行数据计算出了每位选手的校内名次，进而选出实际入选的9名选手。
请回答下列问题：
（1）对于如图所示前4行数据，若s、w分别为5和1，
则0号学校入选人数是　　　　。
3
（1）w为1，故先选择每所学校中名次为1的选手，对应选手编号为0002、2027、1081，剩余名额按成绩由高到低依次挑选，故选择的选手编号依次为2002、0072、0182，此时选中的选手人数超过s，挑选结束。其中0号学校入选了编号为0002、0072、0182的3人。
（2）定义如下search(data,sid,score)函数，data列表每个元素的前5个数据项依次为学校编号、选手编号、成绩、校内名次、是否入选，列表已按成绩由高到低排列。函数的功能是查找选手编号为sid、成绩为score的元素，返回其下标，若未找到则返回-1。
def search(data,sid,score):
　left,right=0,len(data)-1
　f=-1
　while left<=right:
　　mid=(left+right)//2
　　if score==data[mid][2]:
　　　f=mid
　　　left=mid+1
　　elif score　　　left=mid+1
　　else:
　　　right=mid-1
　if f==-1:
　　return -1
　for i in range( f,len(data) ):
　　if data[i][2]!=score:
　　　return -1
　　elif data[i][1]==sid:
　　　return i
　return -1
①调用search函数，若data列表长度为12，data[0][2]，data[1][2]，…，data[11][2]的值依次为：198，185，183，182，182，177，177，176，175，163，161，161，score值为177，则while语句中循环体的执行次数是　　　　　　　。
②程序中加框处代码有错，请改正。
（2）①根据代码可知，while循环采用了二分查找算法，当查找到成绩为score的元素时，将继续往右查找，若score的值为177，则依次查找的值为177、175、177、176，即循环体的执行次数为4。②while循环查找到的是最后一个成绩值等于score的索引，值存储在f中，因此for循环应从f开始，往左遍历元素，判断对应的选手编号是否为sid，故正确代码为f,-1,-1。
4
f,-1,-1　或其他等价答案
（3）实现根据选手成绩（成绩不超过200）计算校内名次，以及挑选决赛选手功能的Python程序如下，请在画线处填入合适的代码。
def proc(data,n,s,w):
　'''创建r列表，共n个元素，每个元素的值均为[0,0,201]，代码略'''
　heads=[-1,-1]
　tails=[-1,-1]
　cnt=0
　for i in range(len(data)):
　　　　　① 　　　
　　r[k][1]+=1
　　if data[i][2]　　　r[k][2]=data[i][2]
　　　　　　② 　　　
　　data[i][3]=r[k][0]
①k=data[i][0]或其他等价答案
②r[k][0]=r[k][1]　或其他等价答案
　　#为data[i]添加一个元素-1
　　data[i].append(-1)　
　　v=1
　　if data[i][3]<=w:
　　　data[i][4]=True
　　　cnt+=1
　　　v=0
　　if heads[v]==-1:
　　　heads[v]=i
　　else:
　　　data[tails[v]][5]=i
　　tails[v]=i
　p,q=heads[0],heads[1]
　'''res列表用于存放入选决赛的选手编号，顺序与data列表保持一致'''
　res=[]
　while cnt　　tmp=data[q][2]
　　while q!=-1 and data[q][2]==tmp:
　　　　　　③　　　:
　　　　res.append(data[p][1])
　　　　p=data[p][5]
　　　res.append(data[q][1])
　　　data[q][4]=True
　　　cnt+=1
　　　q=data[q][5]
　while p!=-1:
　　res.append(data[p][1])
　　p=data[p][5]
　return res
'''读取n、s、w；读取选手成绩数据表存入data列表，每个元素包含学校编号、选手编号、成绩、校内名次（初值为0）、是否入选（初值为False）5个数据项，代码略'''
res=proc(data,n,s,w)
#输出res列表中的入选选手编号，代码略
'''读取待查询的选手编号与成绩，调用search函数，根据返回值输出查询结果，代码略'''
③while p!=-1 and p（3）①r列表中有n个元素，对应n所学校，遍历data列表中的元素，提取学校编号作为r的索引k，故填入代码为k=data[i][0]。②每次循环r[k][1]的值累加1，故r[k][1]表示当前学校的总人数，根据if语句可知，r[k][2]表示当前学校选手的最低分，根据代码“data[i][3]=r[k][0]”可知，r[k][0]表示当前选手的校内名次。由于data中元素是按照成绩降序排序的，因此第1个遍历到的就是第1名，后面只有当遍历到比当前成绩低的，才会增加1个名次（即成绩相同时名次也相同），此时的人数即对应的校内名次，故填入代码为r[k][0]=r[k][1]。③根据后面代码可知，heads[0]是直接入选选手的链表表头，heads[1]是剩余选手的链表表头，tails是相应链表的表尾，p和q分别遍历两个链表，res中存储入选决赛的选手编号，并且顺序与data列表保持一致。第2层while循环用于添加剩余选手中所有成绩与当前选手成绩tmp相同的选手编号，但需要先添加所有在当前选手之前的直接入选的选手编号，即当p小于q时，将直接入选的选手编号加入列表res，之后再添加剩余选手的编号，故填入代码为while p!=-1 and p①k=data[i][0]或其他等价答案　②r[k][0]=r[k][1]　或其他等价答案　③while p!=-1 and p

展开更多......