资源简介

课时22　链表的遍历
【学业要求】
知识点 学业水平等级
1.能结合链表的应用案例,掌握链表的概念,了解链表组织、存储结构的原理与特性。 3
2.能根据问题特点规划节点的数据域和指针域,完成创建链表、访问链表节点的操作。 4
　　使用列表d模拟链表结构,列表的每个元素就是链表的节点,该元素的下标就是链表的指针,该节点包含数据区域和指针区域,而该指针区域就是后继节点的下标。当前节点从头节点开始遍历,将指针更新为当前节点的数据区域值,实现了节点向后移动。在2023年6月的第15题中,根据任务之间的依赖关系,构建了链表,在遍历链表的过程中,将各个任务的编号依次存储在索引数组中,再进行相应的最晚时间计算。
(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
　#task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1。
　#根据任务依赖关系,让task[i][1]指向任务i的下一个任务。
　#统计每个任务是否有前置任务,并保存到pr列表中,pr列表值为1,表示该下标任务有前置任务,代码略。
　c=[]
　days=0　#days存放工程最快完成所需的天数
　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
　#计算每个任务最晚必须开始的时间,代码略
答案　k=task[k][1]
解析　本题考查链表的遍历。依次遍历各个任务,若当前任务没有前置任务,说明该任务是当前链表的头节点,当前节点k从头节点开始遍历整个链表,将每个任务的下标添加到列表c中,将每个任务所需天数累加到s中,再移到当前指针k为其后继节点,继续遍历链表。
1.链表是将需要处理的数据对象以　　　　的形式,通过指针串联在一起的一种数据结构。
2.同一个链表中每个节点的　　　　均相同,由数据区域和指针区域组成。
3.每个链表都有一个　　　　指针head,是链表的入口,也便于循环链表在数据处理时的边界判断和处理。
4.链表可以根据每个节点中指针的数量分为　　　　向链表、　　　　向链表和循环链表。
5.若链表lst每个节点只有一个值和一个指针,当前节点为q,该节点表示为　　　　,该节点的值为lst[q][0],后继节点即下一个节点的索引是　　　　。
6.前节点q初值为头指针head,通过语句q=lst[q][1]遍历整个链表,当q的值为　　　　时结束链表遍历。
7.当链表遍历结束后,q的值为-1,其前驱为　　　　节点。
自我校对:1.节点　2.结构　3.头　4.单　双　5.lst[q] 　lst[q][1]　6.-1　7.尾
【典例1】 使用列表模拟单链表,其存储结构如图所示,遍历该链表,将访问到的节点的数据域的字符依次连接,得到字符串‘LOVE’,则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 -1 1 D.2 0 1 -1
思维点拨
明考向 本题考查链表的构建和遍历
精点拨 L的后继节点为O,因此其指针区域值为1;O的后续为V,指针区域值为0; V的后续为E,指针区域值为2;E为尾节点,因此指针区域值为-1
答案　C
【变式1】 某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组a中,现计算相邻两个站点距离的总和。
import math
a=[["廊桥",3,2,3],["徐岙",6,11,2],["北门",13,8,-1],["上通",3,7,1]]
head=0;s=0
p=a[head][3]
while (1)　　　　:
　　s+=math.sqrt((a[p][1]-a[head][1])**2+(a[p][2]-a[head][2])**2)
　　(2)　　　
　　(3)　　　
print(s)
上述程序段划线处可选的代码为:
①a[head][3]!=-1　②head=p
③p=a[head][3]　④head!=-1
则(1)(2)(3)处的代码依次为(　　)
A.①②③ B.④②③
C.④③② D.①③②
答案　A
解析　本题考查链表的遍历。从当前链表的头节点开始遍历,与下一个节点p的距离,因此head要不断地后移,head=p,而p为新节点的后继节点。当头指针节点的后继为-1时,表示遍历完了。
【典例2】 (2025年6月浙江选考)有如下Python程序段:
tag=[0]*len(data)
p=i=0
while i　 if 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
思维点拨
明考向 本题考查链表的遍历
精点拨 tag列表记录节点data[i]到链表尾节点[23,-1]之间需跳转的次数。指针i依次遍历data的各个下标,将data各个节点作为链表的头节点,指针p从该节点开始向后遍历链表,若tag[p]值为0,且没有达到链表的尾节点时,跳转的次数增加1次。若节点p的到尾节点之间的跳转的次数已经统计,将该数量累加到当前tag[i],接着处理下一个起始节点。i为0时,需跳转2次。i为1时,无需跳转。i为2时,跳转到第1个节点,累加前面2次,需跳转3次。i为3时,需跳转1次。i为4时,跳转到第3个节点[15,0],累加前面3次,需跳转4次。最终tag列表的值为[2,0,3,1,4]
答案　D
【变式2】 使用链表结构模拟某校游览路线,链表a中每一个节点包含三个数据,第1个为地点名称,第2个为预计停留时间(单位:分钟),第3个为指向下一个地点指针。可以从多个地点开始浏览,但只能从“南大门”离开,输出显示从各景点进入路线及预计总时间的代码如下。
a=[["校训石",15,2],["教学楼",30,2],["风雨操场",25,5],["科技楼",40,4],["新华书店",60,5],["南大门",20,-1]]
head=[0,1,3]
for i in range(len(head)):
　(1)　　　
　s=a[p][1]
　while a[p][2]!=-1:
　　　print(a[p][0],end="→")
　　　(2)　　　
　　　(3)　　　
　print(a[p][0])
　print("预计时间:",s,"分钟")
上述程序划线处的可选代码有:
①p=head　②p=head[i]　③s=s+a[p][1]　④p=a[p][2]
则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③
C.②③④ D.②④③
答案　D
解析　本题考查多条链表的遍历。head列表有3个元素,依次遍历这些元素,当前节点p从每个头指针head[i]开始遍历各条链表的各个节点,累加各个节点的时间值s=s+a[p][1],并向后移动指针p=a[p][2]。
　　链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的,均由数据区域和指针区域组成,其中指针区域指向下一个节点的索引,尾节点的指针区域值为-1。画出链表lst节点q的结构,理解lst[q]表示整个节点,lst[q][0]表示节点的数据,lst[q][1]表示下一节点的下标。链表的访问必须从头节点开始,因此头指针是链表必不可少的元素。头指针作为链表的访问入口,若其值改变,相当于删除或新增节点,因此往往用变量q指向头节点作为当前节点,当前节点从头节点开始不断地向后遍历整个链表,直到q的值为-1为止。
1.对于链表的描述,下列说法不正确的是(　　)
A.同一链表中每个节点的结构均相同
B.每个链表必定有一个头指针
C.链表占用的空间不固定
D.创建的新链表中至少要有一个节点
答案　D
解析　本题考查链表的基本性质。A选项链表节点包含数据区域和指针区域,每个节点中的数据区域中数据类型是相同的。B选项访问链表的某一节点,只能从头指针开始,依次访问。C选项链表通过指针相连,相信节点存储时不需要连续空间,因此链表空间是不固定的。D选项可以空链表,数据区域为空,头指针为-1。
2.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点,需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
答案　D
解析　本题考查链表相关知识。A选项单向链表必定有头指针,不一定要有尾指针。B选项尾结点没有后继节点。C选项单向链表删除一个节点,只需修改删除节点的前驱节点的后继指针即可。D选项链表的访问比较低效,每次遍历都需要从head头结点开始,故算法时间复杂度为O(n)。
3.使用Python的二维列表来模拟单向链表,如下代码创建一个拥有4个节点的链表a
a=[["cat",1],["dog",2],["pig",-1],["rabbit",0]]
head=3
依次输出各节点数据域的值,内容为(　　)
A."cat","dog","pig","rabbit"
B."pig","rabbit","cat","dog"
C."pig","dog","cat","rabbit"
D."rabbit","cat","dog","pig"
答案　D
解析　本题主要考查链表的操作。head=3,即对应列表索引3,其值为“rabbit”,指向索引为0的节点,其值为“cat”,以此类推,依次输出各节点数据域的值,内容为"rabbit","cat","dog","pig"。
4.有如下Python程序段:
a=[[2,2],[5,3],[3,1],[6,-1],[1,0],[4,2]]
p=5
while a[p][1]!=-1:
　　print(a[p][0],end="→")
　　p=a[p][1]
则运行程序后,控制台输出的结果是(　　)
A.4→3→5 B.4→3→5→6→
C.4→3→5→ D.4→3→5→6
答案　C
解析　本题考查链表的遍历。条件a[p][1]!=-1表示当前节点的指针区域值为-1,即当前节点为尾节点。当遍历到尾节点时,结束循环。
5.采用Python二维列表模拟链表,
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]表示链表为:
A→B→C→D→E→F→None,有以下Python程序:
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]
head=0;p=a[head][1]
a[head][1]=-1
while p!=-1:
　　p=a[p][1]
　　if p==-1:
　　　 break
　　t=a[p][1]
　　a[p][1]=head
　　head=p
　　p=t
执行以上程序后,以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
答案　A
解析　本题考查链表的基本操作。p的初值为a[head][1],即head的后继,进入循环后,语句p=a[p][1]的功能是向后遍历,让该节点指向头节点,p再向后遍历。A后继的后继是C,当前头节点为C,C指向A;C后继的后继是E,当前头节点为E,E指向C。
6.使用链表结构模拟某景区游玩路线,链表a中每一个节点包含3个数据,第1个为景点名称,第2个为预计游玩时间(单位:分钟),第3个为下一个景点指针。景区可以从多个景点的大门进入,但只能从"天梯"离开,输出显示各大门进入路线及预计总时间的代码如下。
a=[["迎客松",21,2],["激流勇进",40,2],["天空栈道",50,5],["一线天",30,4],["飞来峰",60,5],["天梯",20,-1]]
head=[0,1,3]
for i in range(len(head)):
　(1)　　　
　s=a[p][1]
　while a[p][2]!=-1:
　　　print(a[p][0], end="→")
　　　(2)　　　
　　　(3)　　　
　print(a[p][0])
print("预计时间:",s,"分钟")
上述程序划线处的可选代码有: ①p=head
②p=head[i]　③s+=a[p][1]　④p=a[p][2]
则(1)(2)(3)处代码依次为:(　　)
A.①③④ B.①④③
C.②③④ D.②④③
答案　D
解析　本题考查多条链表的遍历。3条链表构建在数组a中,头指针存储在数组head中,需遍历头指针数组,从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i],变量s存储所有节点游览总时间。(2)(3)遍历链表,并统计各个节点游览时间和,由于当前节点已经计入总时间,因此先要跳转到下一点,将下一节点的时间加入总时间,注意遍历结束的条件是当遍历到尾节点时,终止遍历。
1.链表不具备的特点是(　　)
A.所需存储空间与存储元素个数成正比
B.插入、删除操作不需要移动元素
C.无须事先估计存储空间的大小
D.可随机访问任何一个元素
答案　D
解析　本题考查链表相关知识点。链表的访问必须从头节点开始。通过指针依次访问,不能随机访问任何一个元素。
2.在一个包含n(n>1)个节点的单链表上,设有头和尾两个指针,下列操作需要遍历多个节点的是(　　)
A.删除该链表中的第一个节点
B.删除该链表中的最后一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
答案　B
解析　B选项删除最后一个节点需修改最后一个节点前驱的指针区域值,因此需遍历多个节点找到其前驱。
3.王老师用链表模拟某次比赛中运动员的出场次序,运动员号码存储如下: a=[["e56",4],["134",-1],["215",5],["098",0],["144",2],["024",1]]。假设head=3,小明同学的号码是“215”,则他的出场次序是(　　)
A.2 B.4
C.5 D.6
答案　B
解析　本题考查链表的遍历。head值为3,["098",0]为头节点,接着是["e56",4] ["144",2] ,["215",5], ["024",1], ["134",-1]。
4.某Python程序如下:
head=4
a=[[2,2],[5,3],[3,1],[6,-1],[1,0]]
p=head
while a[p][1]!=-1:
　　print(a[p][0],end="→")
　　p=a[p][1]
程序运行后,输出的结果是(　　)
A.1→2→3→5 B.1→2→3→5→
C.1→2→3→5→6 D.1→2→3→5→6→
答案　B
解析　没有输出尾结点,输出前面4个节点的数据域,并以"→"结束,故答案为1→2→3→5→。
5.利用列表模拟非循环链表a(可能存在已被删除的节点),下列程序运行完毕后,变量p表示尾节点的节点位置是(　　)
A.p,head=0,0
　while p!=-1:
　　　t=p;p=a[p][1]
B.p,head=0,0
　while a[p][1]!=-1:
　　　p=a[p][1]
C.p,head=0,0
　while a[a[p][1]][1]!=-1:
　　　p=a[p][1]
D.p,head=0,0
　n=len(a)
　while n>1:
　　　p=a[p][1];n-=1
答案　B
解析　本题考查链表的遍历。A选项当前节点为p,当遍历到节点为空时停止遍历,因此遍历结束后,p节点为空,其前驱t为尾节点。B选项当前节点为p,若当前节点的指针区域值为-1,结束遍历,那么当前节点p为尾节点。C选项当前节点从头节点开始遍历,a[a[p][1]]指当前节点的后继节点,若该节点的指针区域值为-1,表示该节点为尾节点,当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点,因此len(a)的值可能大于节点总数。
6.某Python程序如下:
data=[]
for i in range(len(a)):
　 data.append([a[i],i+1])
data[-1][1]=-1
la=head=0
t=data[head][1]
key,c=2,0
while c<3 and t!=-1:
　　if data[t][0]-data[la][0]　　 　c+=1
　　la=t
　　t=data[t][1]
已知执行上述程序后,t的值为6,则数组a的值可能(　　)
A.[4,3,1,6,3,9,3] B.[2,6,5,1,6,4,0]
C.[7,5,2,3,2,7,5] D.[2,4,0,1,0,8,4]
答案　B
解析　本题考查链表应用。data是一个链表,t指针从链表的第二个节点开始遍历,1a指针是t节点的前驱,t节点减去前驱节点la的值小于key时,c计数,c的初值为0,计数到3时结束,也就是整个过程计数3次就结束,执行程序后t的值为6,也就是遍历到最后一个节点时程序才结束。
7.实现在链表 c 中找出最小值 m 的 Python 程序如下:
head=3;p=head;m=c[head][0]
while (1)　　　　:
　 (2)　　　
　 if c[p][0]　　　 m=c[p][0]
上述程序段中方框处可选代码为:①p!=-1
②c[p][1]!=-1　③p=p+1　④p=c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③
C.①④ D.②④
答案　D
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历,最小值的初值为头节点大小,因此需先移动到下一节点,再与最值进行比较,同时终止遍历的条件是遍历到尾节点马上结束。
8.链表中有两个不同节点指向同一个节点,构成一个环,编写程序检验链表指针设置是否合理的代码如下,请将划线处代码补充完整(　　)
#将链表数据存储在列表d中,每个节点第1个元素为值,第2个元素为指针
slow,fast=head,head
while ①　　　　:
　　slow=d[slow][1]
　　fast=d[d[fast][1]][1]
　　if ②　　　　:
　　　print("链表中有环,指针设置不合理!")
　　　break
else:
　　print("链表指针设置合理!")
A.①fast=-1 and a[fast][1]=-1　②fast!=slow
B.①fast=-1 and a[fast][1]=-1　②fast==slow
C.①fast=-1 or a[fast][1]=-1　②fast!=slow
D.①fast=-1 or a[fast][1]=-1　②fast==slow
答案　D
解析　使用两个指针,一个移动得较慢slow(每次移动一步),另一个指针fast移动得较快(每次移动两步)。如果链表中存在环,这两个指针最终会相遇。如果链表没有环,快指针会先到达链表的末尾,若链表节点数为奇数,则fast到达尾节点时结束。
9.接力比赛男女生人数相等,男女队员交替接力,实现该功能的Python程序段如下:
a=[["1号","女"],["2号","女"],["3号","男"],["4号","男"],["5号","男"],["6号","女"],["7号","女"],["8号","男"]]
print(a[0])　#输出第一棒
pre=0;i=1
que=[-1]*len(a)
head=tail=0
while i　　if head!=tail:
　　　if a[que[head]][1]!=a[pre][1]:
　　　　　print(a[que[head]])
　　　　　pre=que[head]
　　　　　head+=1
　　①　　　　 :
　　　print(a[i])
　　　pre=i
　else:　#性别与前一棒相同时则进入等待队列
　　　　que[tail]=i
　　　　tail+=1
　i+=1
if head!=tail:
　print(②　　　　)
上述程序段中划线处应填写的代码是(　　)
A.①elif a[pre][1]!=a[i][1]　②que[head])
B.①if a[pre][1]!=a[i][1]　②que[head]
C.①elif a[pre][1]!=a[i][1]　②a[que[head]]
D.①if a[pre][1]!=a[i][1]　②a[que[head]]
答案　D
解析　程序借助队列结构完成接力比赛男女队员的交替接力。对队列队首队员的性别和最近进入接力序列队员的性别进行比较,若不同,则将队列队首元素出队,否则继续对a数组进行遍历,若取到符合性别要求的元素则设定为下一趟性别比较的前驱,若性别与前一棒相同时则将该元素的索引置入等待队列。
10.通过以下Python程序段,将原链表转换为逆序链表。如原链表为'A'→'B'→'C',转换为逆序链表后,'C'→'B'→'A'。
L = [['尚书',4],['春秋',-1],['诗经',0],['周易',1],['礼记',3]]
head,p=2,2　#head为原链表头指针
q=-1
while p!=-1:
　　tmp=L[p][1]
　　
head=q
程序段中方框处可选的语句是:
①p=tmp　②q=p　③L[p][1]=q
为实现上述功能,方框处语句依次是(　　)
A.③①② B.③②①
C.①③② D.①②③
答案　B
解析　本题考查链表的遍历。p为当前节点,从头节点开始遍历链表,将遍历的新节点以头插法的形式重新构建链表。q为新链表的头节点,保存当前节点p的后续索引为tmp,先让新链表的头节点指向新链表的头节点,再将头指针指向p,p从原后续继续遍历原链表。
11.使用列表a模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,head为头指针。链表中各节点已按数据区域中的数值由小到大排列。现要计算链表中的中位数,处在链表最中间位置的数叫作中位数。说明:当数据元素为奇数个时中位数为最中间的数,偶数个时中位数为最中间两个数的平均数。实现功能的Python程序如下,划线处应填入的正确代码为(　　)
fast=slow=head
while fast!=-1 and ①　　　　:
　　p=slow
　　slow=a[slow][1]
　　fast= a[a[fast][1]][1]
if　②　　　　:
　　mid=(a[p][0]+a[slow][0])/2
else:
　　mid=a[slow][0]
print("中位数是:", mid)
A.①slow!=-1　②fast!=-1
B.①a[slow][1]!=-1　②fast==-1
C.①a[fast][1]!=-1　②fast!=-1
D.①a[fast][1]!=-1　②fast==-1
答案　D
解析　fast和slow分别表示快慢指针,fast每次遍历2个节点,若遍历完成后,fast的值为-1,表示节点数量为偶数,当a[fast][1]值为-1,遍历到尾节点,节点数量为奇数,遍历完成。(共56张PPT)
选修一　数据与数据结构
课时22　链表的遍历
知识点 学业水平等级
1.能结合链表的应用案例,掌握链表的概念,了解链表组织、存储结构的原理与特性。 3
2.能根据问题特点规划节点的数据域和指针域,完成创建链表、访问链表节点的操作。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　使用列表d模拟链表结构,列表的每个元素就是链表的节点,该元素的下标就是链表的指针,该节点包含数据区域和指针区域,而该指针区域就是后继节点的下标。当前节点从头节点开始遍历,将指针更新为当前节点的数据区域值,实现了节点向后移动。在2023年6月的第15题中,根据任务之间的依赖关系,构建了链表,在遍历链表的过程中,将各个任务的编号依次存储在索引数组中,再进行相应的最晚时间计算。
(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
　#task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1。
　#根据任务依赖关系,让task[i][1]指向任务i的下一个任务。
　#统计每个任务是否有前置任务,并保存到pr列表中,pr列表值为1,表示该下标任务有前置任务,代码略。
　c=[]
　days=0　#days存放工程最快完成所需的天数
　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
　#计算每个任务最晚必须开始的时间,代码略
答案　k=task[k][1]
解析　本题考查链表的遍历。依次遍历各个任务,若当前任务没有前置任务,说明该任务是当前链表的头节点,当前节点k从头节点开始遍历整个链表,将每个任务的下标添加到列表c中,将每个任务所需天数累加到s中,再移到当前指针k为其后继节点,继续遍历链表。
知识梳理
2
1.链表是将需要处理的数据对象以　　　　的形式,通过指针串联在一起的一种数据结构。
2.同一个链表中每个节点的　　　　均相同,由数据区域和指针区域组成。
3.每个链表都有一个　　　　指针head,是链表的入口,也便于循环链表在数据处理时的边界判断和处理。
4.链表可以根据每个节点中指针的数量分为　　　　向链表、　　　　向链表和循环链表。
节点
结构
头
单
双
5.若链表lst每个节点只有一个值和一个指针,当前节点为q,该节点表示为　　　　,该节点的值为lst[q][0],后继节点即下一个节点的索引是　　　　。
6.前节点q初值为头指针head,通过语句q=lst[q][1]遍历整个链表,当q的值为　　时结束链表遍历。
7.当链表遍历结束后,q的值为-1,其前驱为　　　　节点。
lst[q]
lst[q][1]
-1
尾
课堂突破
3
【典例1】 使用列表模拟单链表,其存储结构如图所示,遍历该链表,将访问到的节点的数据域的字符依次连接,得到字符串‘LOVE’,则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 -1 1 D.2 0 1 -1
答案　C
思维点拨
明考向 本题考查链表的构建和遍历
精点拨 L的后继节点为O,因此其指针区域值为1;O的后续为V,指针区域值为0; V的后续为E,指针区域值为2;E为尾节点,因此指针区域值为-1
【变式1】 某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组a中,现计算相邻两个站点距离的总和。
import math
a=[["廊桥",3,2,3],["徐岙",6,11,2],["北门",13,8,-1],["上通",3,7,1]]
head=0;s=0
p=a[head][3]
while (1)　　　　:
　　s+=math.sqrt((a[p][1]-a[head][1])**2+(a[p][2]-a[head][2])**2)
　　(2)　　　
　　(3)　　　
print(s)
上述程序段划线处可选的代码为:
①a[head][3]!=-1　②head=p
③p=a[head][3]　④head!=-1
则(1)(2)(3)处的代码依次为(　　)
A.①②③ B.④②③
C.④③② D.①③②
解析　本题考查链表的遍历。从当前链表的头节点开始遍历,与下一个节点p的距离,因此head要不断地后移,head=p,而p为新节点的后继节点。当头指针节点的后继为-1时,表示遍历完了。
A
【典例2】 (2025年6月浙江选考)有如下Python程序段:
tag=[0]*len(data)
p=i=0
while i　 if 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
思维点拨
明考向 本题考查链表的遍历
精点拨 tag列表记录节点data[i]到链表尾节点[23,-1]之间需跳转的次数。指针i依次遍历data的各个下标,将data各个节点作为链表的头节点,指针p从该节点开始向后遍历链表,若tag[p]值为0,且没有达到链表的尾节点时,跳转的次数增加1次。若节点p的到尾节点之间的跳转的次数已经统计,将该数量累加到当前tag[i],接着处理下一个起始节点。i为0时,需跳转2次。i为1时,无需跳转。i为2时,跳转到第1个节点,累加前面2次,需跳转3次。i为3时,需跳转1次。i为4时,跳转到第3个节点[15,0],累加前面3次,需跳转4次。最终tag列表的值为[2,0,3,1,4]
【变式2】 使用链表结构模拟某校游览路线,链表a中每一个节点包含三个数据,第1个为地点名称,第2个为预计停留时间(单位:分钟),第3个为指向下一个地点指针。可以从多个地点开始浏览,但只能从“南大门”离开,输出显示从各景点进入路线及预计总时间的代码如下。
a=[["校训石",15,2],["教学楼",30,2],["风雨操场",25,5],["科技楼",40,4],["新华书店",60,5],["南大门",20,-1]]
head=[0,1,3]
for i in range(len(head)):
　(1)　　　
　s=a[p][1]
　while a[p][2]!=-1:
　　　print(a[p][0],end="→")
　　　(2)　　　
　　　(3)　　　
　print(a[p][0])
　print("预计时间:",s,"分钟")
上述程序划线处的可选代码有:
①p=head　②p=head[i]　③s=s+a[p][1]　④p=a[p][2]
则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③
C.②③④ D.②④③
解析　本题考查多条链表的遍历。head列表有3个元素,依次遍历这些元素,当前节点p从每个头指针head[i]开始遍历各条链表的各个节点,累加各个节点的时间值s=s+a[p][1],并向后移动指针p=a[p][2]。
D
　　链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的,均由数据区域和指针区域组成,其中指针区域指向下一个节点的索引,尾节点的指针区域值为-1。画出链表lst节点q的结构,理解lst[q]表示整个节点,lst[q][0]表示节点的数据,lst[q][1]表示下一节点的下标。链表的访问必须从头节点开始,因此头指针是链表必不可少的元素。头指针作为链表的访问入口,若其值改变,相当于删除或新增节点,因此往往用变量q指向头节点作为当前节点,当前节点从头节点开始不断地向后遍历整个链表,直到q的值为-1为止。
当堂检测
4
A.同一链表中每个节点的结构均相同
B.每个链表必定有一个头指针
C.链表占用的空间不固定
D.创建的新链表中至少要有一个节点
D
解析　本题考查链表的基本性质。A选项链表节点包含数据区域和指针区域,每个节点中的数据区域中数据类型是相同的。B选项访问链表的某一节点,只能从头指针开始,依次访问。C选项链表通过指针相连,相信节点存储时不需要连续空间,因此链表空间是不固定的。D选项可以空链表,数据区域为空,头指针为-1。
2.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点,需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
D
解析　本题考查链表相关知识。A选项单向链表必定有头指针,不一定要有尾指针。B选项尾结点没有后继节点。C选项单向链表删除一个节点,只需修改删除节点的前驱节点的后继指针即可。D选项链表的访问比较低效,每次遍历都需要从head头结点开始,故算法时间复杂度为O(n)。
3.使用Python的二维列表来模拟单向链表,如下代码创建一个拥有4个节点的链表a
a=[["cat",1],["dog",2],["pig",-1],["rabbit",0]]
head=3
依次输出各节点数据域的值,内容为(　　)
A."cat","dog","pig","rabbit“ B."pig","rabbit","cat","dog"
C."pig","dog","cat","rabbit“ D."rabbit","cat","dog","pig"
D
解析　本题主要考查链表的操作。head=3,即对应列表索引3,其值为“rabbit”,指向索引为0的节点,其值为“cat”,以此类推,依次输出各节点数据域的值,内容为"rabbit","cat","dog","pig"。
4.有如下Python程序段:
a=[[2,2],[5,3],[3,1],[6,-1],[1,0],[4,2]]
p=5
while a[p][1]!=-1:
　　print(a[p][0],end="→")
　　p=a[p][1]
则运行程序后,控制台输出的结果是(　　)
A.4→3→5 B.4→3→5→6→
C.4→3→5→ D.4→3→5→6
C
解析　本题考查链表的遍历。条件a[p][1]!=-1表示当前节点的指针区域值为-1,即当前节点为尾节点。当遍历到尾节点时,结束循环。
5.采用Python二维列表模拟链表,
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]表示链表为:
A→B→C→D→E→F→None,有以下Python程序:
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]
head=0;p=a[head][1]
a[head][1]=-1
while p!=-1:
　　p=a[p][1]
　　if p==-1:
　　　 break
　　t=a[p][1]
　　a[p][1]=head
　　head=p
　　p=t
A
解析　本题考查链表的基本操作。p的初值为a[head][1],即head的后继,进入循环后,语句p=a[p][1]的功能是向后遍历,让该节点指向头节点,p再向后遍历。A后继的后继是C,当前头节点为C,C指向A;C后继的后继是E,当前头节点为E,E指向C。
执行以上程序后,以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
6.使用链表结构模拟某景区游玩路线,链表a中每一个节点包含3个数据,第1个为景点名称,第2个为预计游玩时间(单位:分钟),第3个为下一个景点指针。景区可以从多个景点的大门进入,但只能从"天梯"离开,输出显示各大门进入路线及预计总时间的代码如下。
a=[["迎客松",21,2],["激流勇进",40,2],["天空栈道",50,5],["一线天",30,4],["飞来峰",60,5],["天梯",20,-1]]
head=[0,1,3]
for i in range(len(head)):
　(1)　　　
　s=a[p][1]
　while a[p][2]!=-1:
　　　print(a[p][0], end="→")
　　　(2)　　　
　　　(3)　　　
　print(a[p][0])
print("预计时间:",s,"分钟")
上述程序划线处的可选代码有: ①p=head
②p=head[i]　③s+=a[p][1]　④p=a[p][2]
则(1)(2)(3)处代码依次为:(　　)
A.①③④ B.①④③
C.②③④ D.②④③
D
解析　本题考查多条链表的遍历。3条链表构建在数组a中,头指针存储在数组head中,需遍历头指针数组,从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i],变量s存储所有节点游览总时间。(2)(3)遍历链表,并统计各个节点游览时间和,由于当前节点已经计入总时间,因此先要跳转到下一点,将下一节点的时间加入总时间,注意遍历结束的条件是当遍历到尾节点时,终止遍历。
课时作业
5
A.所需存储空间与存储元素个数成正比
B.插入、删除操作不需要移动元素
C.无须事先估计存储空间的大小
D.可随机访问任何一个元素
D
解析　本题考查链表相关知识点。链表的访问必须从头节点开始。通过指针依次访问,不能随机访问任何一个元素。
2.在一个包含n(n>1)个节点的单链表上,设有头和尾两个指针,下列操作需要遍历多个节点的是(　　)
A.删除该链表中的第一个节点
B.删除该链表中的最后一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
B
解析　B选项删除最后一个节点需修改最后一个节点前驱的指针区域值,因此需遍历多个节点找到其前驱。
3.王老师用链表模拟某次比赛中运动员的出场次序,运动员号码存储如下: a=[["e56",4],["134",-1],["215",5],["098",0],["144",2],["024",1]]。假设head=3,小明同学的号码是“215”,则他的出场次序是(　　)
A.2 B.4
C.5 D.6
B
解析　本题考查链表的遍历。head值为3,["098",0]为头节点,接着是["e56",4] ["144",2] ,["215",5], ["024",1], ["134",-1]。
4.某Python程序如下:
head=4
a=[[2,2],[5,3],[3,1],[6,-1],[1,0]]
p=head
while a[p][1]!=-1:
　　print(a[p][0],end="→")
　　p=a[p][1]
程序运行后,输出的结果是(　　)
A.1→2→3→5 B.1→2→3→5→
C.1→2→3→5→6 D.1→2→3→5→6→
B
解析　没有输出尾结点,输出前面4个节点的数据域,并以"→"结束,故答案为1→2→3→5→。
5.利用列表模拟非循环链表a(可能存在已被删除的节点),下列程序运行完毕后,变量p表示尾节点的节点位置是(　　)
B
A.p,head=0,0
　while p!=-1:
　　　t=p;p=a[p][1]
B.p,head=0,0
　while a[p][1]!=-1:
　　　p=a[p][1]
C.p,head=0,0
　while a[a[p][1]][1]!=-1:
　　　p=a[p][1]
D.p,head=0,0
　n=len(a)
　while n>1:
　　　p=a[p][1];n-=1
解析　本题考查链表的遍历。A选项当前节点为p,当遍历到节点为空时停止遍历,因此遍历结束后,p节点为空,其前驱t为尾节点。B选项当前节点为p,若当前节点的指针区域值为-1,结束遍历,那么当前节点p为尾节点。C选项当前节点从头节点开始遍历,a[a[p][1]]指当前节点的后继节点,若该节点的指针区域值为-1,表示该节点为尾节点,当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点,因此len(a)的值可能大于节点总数。
6.某Python程序如下:
data=[]
for i in range(len(a)):
　 data.append([a[i],i+1])
data[-1][1]=-1
la=head=0
t=data[head][1]
key,c=2,0
while c<3 and t!=-1:
　　if data[t][0]-data[la][0]　　 　c+=1
　　la=t
　　t=data[t][1]
已知执行上述程序后,t的值为6,则数组a的值可能(　　)
A.[4,3,1,6,3,9,3] B.[2,6,5,1,6,4,0]
C.[7,5,2,3,2,7,5] D.[2,4,0,1,0,8,4]
B
解析　本题考查链表应用。data是一个链表,t指针从链表的第二个节点开始遍历,1a指针是t节点的前驱,t节点减去前驱节点la的值小于key时,c计数,c的初值为0,计数到3时结束,也就是整个过程计数3次就结束,执行程序后t的值为6,也就是遍历到最后一个节点时程序才结束。
7.实现在链表 c 中找出最小值 m 的 Python 程序如下:
head=3;p=head;m=c[head][0]
while (1)　　　　:
　 (2)　　　
　 if c[p][0]　　　 m=c[p][0]
上述程序段中方框处可选代码为:①p!=-1
②c[p][1]!=-1　③p=p+1　④p=c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③
C.①④ D.②④
D
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历,最小值的初值为头节点大小,因此需先移动到下一节点,再与最值进行比较,同时终止遍历的条件是遍历到尾节点马上结束。
8.链表中有两个不同节点指向同一个节点,构成一个环,编写程序检验链表指针设置是否合理的代码如下,请将划线处代码补充完整(　　)
#将链表数据存储在列表d中,每个节点第1个元素为值,第2个元素为指针
slow,fast=head,head
while ①　　　　:
　　slow=d[slow][1]
　　fast=d[d[fast][1]][1]
　　if ②　　　　:
　　　print("链表中有环,指针设置不合理!")
　　　break
else:
　　print("链表指针设置合理!")
D
A.①fast=-1 and a[fast][1]=-1　②fast!=slow
B.①fast=-1 and a[fast][1]=-1　②fast==slow
C.①fast=-1 or a[fast][1]=-1　②fast!=slow
D.①fast=-1 or a[fast][1]=-1　②fast==slow
解析　使用两个指针,一个移动得较慢slow(每次移动一步),另一个指针fast移动得较快(每次移动两步)。如果链表中存在环,这两个指针最终会相遇。如果链表没有环,快指针会先到达链表的末尾,若链表节点数为奇数,则fast到达尾节点时结束。
9.接力比赛男女生人数相等,男女队员交替接力,实现该功能的Python程序段如下:
a=[["1号","女"],["2号","女"],["3号","男"],["4号","男"],["5号","男"],["6号","女"],["7号","女"],["8号","男"]]
print(a[0])　#输出第一棒
pre=0;i=1
que=[-1]*len(a)
head=tail=0
while i　　if head!=tail:
　　　if a[que[head]][1]!=a[pre][1]:
　　　　　print(a[que[head]])
　　　　　pre=que[head]
　　　　　head+=1
　　①　　　　 :
　　　print(a[i])
　　　pre=i
　else:　#性别与前一棒相同时则进入等待队列
　　　　que[tail]=i
　　　　tail+=1
　i+=1
if head!=tail:
　print(②　　　　)
上述程序段中划线处应填写的代码是(　　)
A.①elif a[pre][1]!=a[i][1]　②que[head])
B.①if a[pre][1]!=a[i][1]　②que[head]
C.①elif a[pre][1]!=a[i][1]　②a[que[head]]
D.①if a[pre][1]!=a[i][1]　②a[que[head]]
D
解析　程序借助队列结构完成接力比赛男女队员的交替接力。对队列队首队员的性别和最近进入接力序列队员的性别进行比较,若不同,则将队列队首元素出队,否则继续对a数组进行遍历,若取到符合性别要求的元素则设定为下一趟性别比较的前驱,若性别与前一棒相同时则将该元素的索引置入等待队列。
10.通过以下Python程序段,将原链表转换为逆序链表。如原链表为'A'→'B'→'C',转换为逆序链表后,'C'→'B'→'A'。
L = [['尚书',4],['春秋',-1],['诗经',0],['周易',1],['礼记',3]]
head,p=2,2　#head为原链表头指针
q=-1
while p!=-1:
　　tmp=L[p][1]
　　
head=q
程序段中方框处可选的语句是:
①p=tmp　②q=p　③L[p][1]=q
为实现上述功能,方框处语句依次是(　　)
A.③①② B.③②①
C.①③② D.①②③
B
解析　本题考查链表的遍历。p为当前节点,从头节点开始遍历链表,将遍历的新节点以头插法的形式重新构建链表。q为新链表的头节点,保存当前节点p的后续索引为tmp,先让新链表的头节点指向新链表的头节点,再将头指针指向p,p从原后续继续遍历原链表。
11.使用列表a模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,head为头指针。链表中各节点已按数据区域中的数值由小到大排列。现要计算链表中的中位数,处在链表最中间位置的数叫作中位数。说明:当数据元素为奇数个时中位数为最中间的数,偶数个时中位数为最中间两个数的平均数。实现功能的Python程序如下,划线处应填入的正确代码为(　　)
D
fast=slow=head
while fast!=-1 and ①　　　　:
　　p=slow
　　slow=a[slow][1]
　　fast= a[a[fast][1]][1]
if　②　　　　:
　　mid=(a[p][0]+a[slow][0])/2
else:
　　mid=a[slow][0]
print("中位数是:", mid)
A.①slow!=-1　②fast!=-1
B.①a[slow][1]!=-1　②fast==-1
C.①a[fast][1]!=-1　②fast!=-1
D.①a[fast][1]!=-1　②fast==-1
解析　fast和slow分别表示快慢指针,fast每次遍历2个节点,若遍历完成后,fast的值为-1,表示节点数量为偶数,当a[fast][1]值为-1,遍历到尾节点,节点数量为奇数,遍历完成。

展开更多......

收起↑