资源简介

(共102张PPT)
课时2　链表
第二章　数组与链表
1.理解数组和链表的概念和特性。2.掌握数组和链表的基本操作。3.能运用数组和链表编程解决实际问题。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.链表的概念
(1)链表指的是将需要处理的数据对象以______的形式，通过______串联在一起的一种数据结构。
(2)每个节点一般包括两个区域：____________和____________。
(3)每个链表有个______——head(也称头指针)，是链表的入口，也便于循环链表在数据处理时的边界判断和处理。
节点
指针
数据区域
指针区域
表头
(4)链表的形式
链表的形式主要有：____________、____________、____________。
①单向链表：只有一个指针用来指向其______节点。单向链表如下图所示。
②双向链表：有两个指针分别用于指向其______节点和______节点。双向链表如下图所示。
单向链表
双向链表
循环链表
后继
前驱
后继
③循环链表：_________节点和____________节点使用指针链接。循环链表如下图所示。
第一个
最后一个
2.链表的特性
(1)同一链表中每个节点的______均相同，有数据区域和指针区域组成。
(2)每个链表必定有一个_________，以实现对链表的引用和边界处理。
(3)链表占用的空间_________。
可根据需求增删节点，提高了存储空间的利用率。
结构
头指针
不固定
3.链表的基本操作
(1)链表的创建
(2)链表节点的访问
链表只能通过头指针进行访问，其他节点通过节点间的指针依次访问。
(3)链表节点的插入与删除
插入操作：
插入datax节点
删除data2节点
(4)链表节点的访问与遍历
访问链表中的节点时，只能通过头指针进入链表并通过指针链接依次访问，直到找到目标位置上的节点。
4.链表的类实现
在Python中，链表除了可以使用列表来实现，还可以使用“类”实现。“类”是一种抽象的数据结构，它将数据及其操作封装在一起。构造单向链表类的具体实现过程如下：
(1)自定义单向链表的节点类：
class Node：　　　#定义单链表节点类
def__init__(self，data，next＝None)：#初始
化节点包含两个域self.data、self.next
　 self.data＝data #self.data域保存数据
　self.next＝next #self.next域保存指针，缺省值为None
(2)构造单向链表类：
class Link：　　　#定义单向链表类Link
　 def __init__(self)：　#初始化空链表
　 self.head＝None #空链表头指针指向为空
例题精析
2
A.同一链表中每个节点的结构均相同 B.每个链表必定有一个头指针
C.链表占用的空间不固定 D.创建的新链表中至少要有一个节点
D
解析　本题考查链表的基本性质。A选项链表节点包含数据区域和指针区域，每个节点中的数据区域中数据类型是相同的。B选项访问链表的某一节点，只能从头指针开始，依次访问。C选项链表通过指针相连，相信节点存储时不需要连续空间，因此链表空间是不固定的。D选项可以空链表，数据区域为空，头指针为－1。
A.可随机访问任一节点
B.插入、删除操作时不需要移动元素
C.不必事先估计存储空间
D.所需空间与其长度成正比
解析　本题主要考查的是链表的特点。访问链表中的某一节点时，只能从头指针开始，通过指针链接依次访问。因此答案为A。
A
例2 使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
解析　本题考查链表的构建和遍历。L的后继节点为O，因此其指针区域值为1；O的后续为V，指针区域值为0; V的后续为E，指针区域值为2；E为尾节点，因此指针区域值为－1。
C
A.0　1　2　3 B.3　1　0　2
C.2　0　－1　1 D.2　0　1　－1
变式训练　利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
B
解析　本题考查链表的遍历。A选项当前节点为p，当遍历到节点为空时停止遍历，因此遍历结束后，p节点为空，其前驱t为尾节点。B选项当前节点为p，若当前节点的指针区域值为－1，结束遍历，那么当前节点p为尾节点。C选项当前节点从头节点开始遍历，a[a[p][1]]指当前节点的后继节点，若该节点的指针区域值为－1，表示该节点为尾节点，当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点，因此len(a)的值可能大于节点总数。
例3 有如下 Python 程序段：
a＝[[3，1]，[2，2]，[3，3]，[3，4]，[17，5]，[2，6]，[3，－1]]
p＝head＝0
while p！＝－1:
q＝p
while q！＝－1:
t＝q
q＝a[q][1]
if q！＝－1 and a[q][0]＝＝a[p][0]：
　　　　　a[t][1]＝a[q][1]
　　　　　q＝t
p＝a[p][1]
p＝head
while p！＝－1：
print(a[p][0]，end＝' ')
p＝a[p][1]
运行后程序的输出结果是(　　)
A.3　2　17 B.3　2　17　2
C.3　2　17　2　3 D.17
解析　本题考查链表的操作。当a[q]节点上的值与a[p]节点上的值相同时，q指针往后移一位。程序的功能是将与p指针所指示的节点值相同的a[q]节点删除。指针t的作用是维护了去重后链表最后一个节点的位置。输出链表的所有非重复节点。
A
变式训练　有如下 Python 程序段：
def guess(cur)：
q＝cur
p＝a[cur][1]
while p！＝－1：
if a[p][0]＝＝a[cur][0]：
　　　　 a[q][1]＝a[p][1]
else：
　　　　 q＝p
p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur！＝－1：
print(a[cur][0]，end＝″″)
if a[cur][1]！＝－1：
guess(cur)
cur＝a[cur][1]
运行后，则输出的结果是(　　)
A.1234 B.1122 C.11223 D.11224
解析　本题考查链表节点的删除。在自定义函数guess中，当前节点p从cur节点的后继开始，如果后面的元素与cur节点元素值相等，则删除节点p，因此是从当前节点链表中删除重复的元素。
A
例4 有两个降序序列的链表 a，b。现将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a，实现数据合并的代码段如下，
a＝[[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b＝[[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a＝head_b＝0
pre＝p＝head_a；q＝head_b
while q！＝－1：
上述程序段中可选填的语句为：
①a[p][0]>＝b[q][0]　② a[p][0]<＝b[q][0]
③q　④len(a)－1　⑤[b[p][0]，q]
⑥[b[q][0]，p]
则加框处填写的语句依次为(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
解析　本题考查链表元素的遍历和插入操作。程序的功能将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a。分别遍历两个链表，若链表a当前元素值a[p][0]大于等于链表 b当前元素值b[q][0]，则链表a向后遍历，否则把链表 b当前元素值b[q][0]插入到链表a当前元素前面。由于是要把链表 b 中的数据合并到链表 a，因此链表b遍历完成后，结束程序。
A
变式训练　有如下 Python 程序：
def lnkid(n，head):
p＝head
while head！＝－1 and _______________：
p＝head
head＝a[head][1]
return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
a.append([n，head])
head＝len(a)－1
else：
a.append([n，a[p][1]])
_________________
用列表 a 模拟一个降序链表，运行程序，输入自然数 n，则链表增加一个新的节点，要使链表保持降序，则划线①②处代码分别为(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
B
解析　本题考查链表的插入。①自定义函数lnkid的功能是查找n在链表中插入位置，head在不断地向后移动，因此n将和a[head][0]进行比较，当比a[head][0]小时，不断地向后查找位置。②语句p＝lnkid(n，head)将返回在节点p的后面插入新的数n，因此将修改a[p]节点指针区域值为当前插入点索引。
例5 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如下图所示。
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
God Is a Girl　十年　年少有为　七里香　淡季动物园
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B
请输入歌曲：兰亭序
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B
请输入歌曲：想自由
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
God Is a Girl　十年　年少有为　七里香　淡季动物园　兰亭序　想自由
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C
请输入歌曲：七里香
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序　想自由
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C
请输入歌曲：想自由
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
想自由　七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序
请输入指令A—显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E
Python 代码如下所示，请在划线处填入合适的代码。
data＝[[″十年″，4]，[″淡季动物园″，－1]，[″God Is a Girl″，0]，[″七里香″，1]，[″年少有为″，3]]
head＝2
tail＝1
while True：
cmd＝input(″请输入指令 A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：″)
if cmd＝＝″A″：
cur＝head
while cur！＝－1:
print(data[cur][0]，end＝″″)
　　　 cur＝data[cur][1]
print()
elif cmd＝＝″B″：
song＝input(″请输入歌曲：″)
data.append([song，－1])
if head＝＝－1：
　　　head＝tail＝len(data)－1
else：
　　　_______________
　　　tail＝len(data)－1
elif cmd＝＝″C″：
song＝input(″请输入歌曲：″)
cur＝head
while cur！＝－1 and data[cur][0]！＝song:
　　　　pre＝cur
　　　　cur＝data[cur][1]
if cur！＝－1 and cur！＝head：
　　　_______________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　　_______________
elif cmd＝＝″D″：
if head＝＝tail:
　　　　head＝tail＝－1
else：
　　　_____________
elif cmd＝＝″E″：
break
答案　①data[tail][1]＝len(data)－1 ②data[pre][1]＝data[cur][1]
③tail＝pre ④head＝data[head][1]
解析　本题考查链表的操作。①输入“B”则可以自行输入歌曲并添加到歌单，新节点插入在尾节点的后面，因此原尾节点应指向新插入的节点，同时更新尾节点。②输入“C”则可以将指定的歌曲置顶，data[cur][0]值为song表示找到节点cur，pre为cur节点的前驱，将cur移动到头节点前面，因此需要3步，第1步是将cur的前驱pre指向cur的后继，第2步是将cur指前原头节点，第3步是设置新的头节点为cur。③若cur是原尾节点tail，将cur修改为头节点后，新的尾节点为cur的前驱。④输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除，条件head＝＝tail成立表示链表中只有一个节点，否则将头指针向后移动，删除头节点。
变式训练　已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　　)
A
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
解析　本题考查链表的遍历、插入和删除操作。A选项删除该链表中的最后一个节点，需修改最后一个节点的前驱节点指针域，因此需遍历多个节点。B选项只需修改头指针。C选项修改当前节点的指针值指向原头节点，并修改头指针为当前节点。D选项让原尾节点指向当前节点，并修改尾节点为当前节点。
随堂检测
3
1.在单向链表中，增加头指针的目的是(　　)
B
解析　在单向链表中，一定有一个头指针，以实现对链表的引用和边界处理，因此，增加头指针的目的是算法实现上的方便，因此，答案为B。
A.标识表节点中首节点的位置
B.算法实现上的方便
C.使单向链表至少有一个节点
D.说明单向链表是线性表的链式存储实现
2.下列关于链表的叙述中，正确的是(　　)
D
解析　单链表存储方式地址不连续，元素顺序是任意的。因此，答案为D。
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
3.某单向链表如下图所示，若要将数据 data3 和data4 同时从链表中移除，至少需要修改节点指针的数量是(　　)
A
解析　只需修改data2的指针区域值修改为data4的指针区域值。
A.1 B.2 C.3 D.4
4.某 Python 程序段如下：
C
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]！＝h：
print(b[p][0]，end＝″，″)
p＝b[p][1]
print(b[p][0])
运行该程序段，输出的内容为 (　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
解析　本题考查循环链表的遍历。h表示头节点，值为0，在链表中有一个节点指向0，因此判定该链表为循环链表。当前节点p从头节点开始遍历，若当前节点指针区域值为头节点，结束遍历，即遍历到尾节点终止循环，没有输出尾节点的值，循环结束后，再次输出尾节点的值。
5.下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。
#建立链表 link1，代码略
key＝int(input(″输入要删除的数据：″))
head＝0
while link1[head][0]＝＝key and head！＝－1:
　head＝link1[head][1]
p＝q＝head
if head＝＝－1：
　 print(″全部数据删除″)
else：
　　q＝link1[q][1]
　　while _______________：
　　 　if link1[q][0]＝＝key：
　　　　 　_______________
　　　else：
　 　　　　p＝link1[p][1]
　　 　q＝link1[q][1]
则划线①②处的代码分别为(　　)
A.①link1[q][1]！＝－1 ②link1[p][1]＝link1[q][1]
B.①link1[q][1]！＝－1 ②link1[q][1]＝link1[p][1]
C.①q！＝－1 ②link1[q][1]＝link1[p][1]
D.①q！＝－1 ②link1[p][1]＝link1[q][1]
D
解析　本题考查链表节点删除的算法实现。先判断当前节点的数据域是否为 key，如果是，则删除当前节点，即将 p节点的指针域指向 q 节点的指针域，如果不是，则将 p 指向下一个节点，q 也指向下一个节点。最后，程序通过 while 循环遍历链表并输出每个节点的数据域。
6.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。
若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1
链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
B
解析　本题考查的知识点是链表元素的插入。链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。
7.在一个单向链表(如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是(　　)
D
A.tail所指节点的data3值赋为r所指节点的data4值
B.r所指节点的next值赋为tail
C.r所指节点的next值赋为－l
D.tail所指节点的next赋为r，r所指节点的next值赋为－l
解析　本题主要考查链表的操作。链表中尾节点的next指针为－1，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是：tail所指节点的next赋为r，r所指节点的next值赋为－1。
8.有如下Python程序段：
n＝int(input(″输入一个数：″))
a＝[]；head＝－1
while n>0：
r＝1－n%2
n∥＝2
a.append([r，head])
head＝len(a)－1
解析　本题考查链表的插入和进制转换。程序的功能是十进制数转成二进制数，并把结果取反。代码a.append([r，head]); head＝len(a)－1的功能利用头插法生成链表。
p＝head
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
运行上述程序段后，如果输入11，则输出结果是(　　)
A.1101 B.1011 C.0010 D.0100
D
9.找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下：
#链表a中存储了序列数据，head为其头指针，代码略
pre＝p＝head
maxpre＝maxp＝head
while p！＝－1：
if a[p][0]>a[maxp][0]:
maxp＝p; maxpre＝pre
pre＝p
p＝a[p][1]
if maxp＝＝head:
head＝a[head][1]
elif maxp！＝pre：
　　①______
a[pre][1]＝maxp
②______
#遍历输出链表 a
划线处的代码应为(　　)
A.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝a[p][1]
B.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝p
C.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝a[p][1]
D.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝p
D
解析　本题考查链表。先查找序列中最大数的位置maxp和该节点的前驱节点maxpre，pre 为最后一个节点位置。再删除最大数节点，分两种情况，最大数节点为第一个节点或其他位置节点。如果是其他位置节点，需将该最大数节点的前驱节点指针区域指向该最大数节点的后继节点位置，即a[maxpre][1]＝a[maxp][1]。最后将最大数节点插入链尾，原最后一个节点指针区域需指向最大数节点，最大数节点为新的最后一个节点，其 指针区域为－1，即 p，所以②a[maxp][1]＝p。
10.某医院每天提前发放100个预约号，考虑到老年人身体原因，预约病人按照以下规则进行就诊：
①老年人(年龄>＝60岁)比非老年人优先就诊。
②老年人按年龄从大到小的顺序就诊，年龄相同的按预约顺序就诊。
③非老年人按预约顺序就诊。
小王根据以上规则编写了一个Python程序，程序运行时，实时读取病人预约数据，并根据以上规则，实时调整并显示当前诊顺序，程序运行界面如图所示。
(1)如图所示，若当前就诊顺序为“75 67 40 15 30”，下一位预约病人年龄为60，则就诊顺序变为__________________。
请输入病人的信息：40
当前就诊顺序为：40
请输入病人的信息：15
当前就诊顺序为：40　15
请输入病人的信息：67
当前就诊顺序为：67　40　15
请输入病人的信息：75
当前就诊顺序为：75　67　40　15
请输入病人的信息：30
当前就诊顺序为：75　67　40　15　30
(2)实现上述功能的代码如下，请在划线处填入合适的代码。
#遍历链表data，头指针为head
def visit(data，head)：
　 cur＝head
　 while cur！＝－1：
　　　print(data[cur][0]，end＝″ ″)
　　　cur＝data[cur][1]
　　print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分别表示链表头节点和尾节点所在位置
for i in range(100)：
#为了简洁，本程序只输入、存储病人的年龄信息
age＝int(input(″请输入病人的信息：″))　
cur＝head
if age>＝60：
while cur！＝－1 and data[cur][0]>＝age: #查找第一个数据域小于age的节点
　　　pre＝cur
　　　
　if cur＝＝head：　#在头节点插入新节点
　　　data.append([age，cur])
　　　head＝len(data)－1
　else：# 在链表中间插入新节点
　　　data.append([age，cur])
　　　②______
　　if cur＝＝－1：　# 更新尾指针位置
　　　　tail＝len(data)－1
　else： #直接插在链表尾节点后
　　data.append([age，－1])
　　if head＝＝－1：　# 添加第一个节点
　　　　head＝tail＝0
答案　(1)75 67 60 40 15 30
(2)①cur＝data[cur][1]
②data[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本题考查链表的遍历和插入操作。(1)老年人(年龄>＝60岁)比非老年人优先就诊，老年人按年龄从大到小的顺序就诊，因此将60插入到40前，结果是75 67 60 40 15 30。(2)当年龄大于等于 60岁时，按年龄降序插入到链表，当年龄小于60岁时，按预约顺序插入链表。①从头节点开始依次遍历，根据数据值找到第一个比当前数据小的节点cur，pre为前驱节点。②在链表中间插入新节点时，需要在插入节点后，更改前驱节点的指针区域。③直接插在链表尾节点后，尾节点变成了前驱节点，更改前驱节点的指针区域。
4
巩固与提升
基础巩固
能力提升
1.下列有关链表的说法中，正确的是(　　)
A
解析　本题主要考查是链表的特性。链表的头指针指向第一个节点，要删除第一个节点，只需将头指针移动到第一个节点指针的指向即可，因此可以删除第一个节点，故答案为A。
A.每个链表的表头一定有一个头指针，以实现对链表的引用和边界处理
B.在单向链表中，最后一个节点的指针指向第一个节点
C.链表一旦创建好后，它占用的空间将固定
D.链表的头指针指向第一个节点，因此不能删除第一个节点
2.设指针变量p指向单向链表lst的某中间节点，如图所示，则删除该节点的后继节点的正确操作是(　　)
C
解析　本题主要考查链表的删除操作。删除该节点的后继节点，需将后继节点的指针域赋值为当前节点的指针域值，实现当前节点连接后继节点的后面节点。lst[p][next]表示后继节点的指针，lst[lst[p][next]]表示后继节点。
A.lst[p][next]＝lst[p][next] [next]
B.p＝lst[p][next][next]
C.lst[p][next]＝lst[lst[p][next]][next]
D.t＝lst[p][next]；p＝lst[t][next]
3.某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标 数据)存储在数组 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)
解析　本题考查链表的遍历。从当前链表的头节点开始遍历，与他下一个节点p的距离，因此head要不断地后移，head＝p，而p为新节点的后继节点。当头指针节点的后继为－1时，表示遍历完了。
上述程序段划线处可选的代码为：
①a[head][3]！＝－1　②head＝p　③p＝a[head][3] ④head！＝－1
则(1)、(2)、(3)处的代码依次为(　　)
A.①②③ B.④②③ C.④③② D.①③②
A
4.已知链表 a 中的每个节点包含数据区域和指针区域两部分，下列 Python 程序段的功能是在链表 a 中删除数据值为 key 的所有节点。
key＝int(input(″输入要删除的数据：″))
head＝0
while head！＝－1 and a[head][0]＝＝key ：
　　head＝a[head][1]
p＝q＝head
if head！＝－1:
　　q＝a[q][1]
　　while ①______：
if a[q][0]＝＝key：
　　　　　②______
else：
　　　 p＝a[p][1]
　　　q＝a[q][1]
则划线①②处的代码分别为(　　)
A.①a[q][1]！＝－1　 ②a[p][1]＝a[q][1]
B.①a[q][1]！＝－1 ②a[q][1]＝a[p][1]
C.①q！＝－1 ②a[q][1]＝a[p][1]
D.①q！＝－1 ②a[p][1]＝a[q][1]
D
解析　本题考查链表节点的删除。①循环遍历整个链表 。②q 为当前元素指针，p是当前节点q的前驱，要删除 q 节点，只需要修改 p 的指针为 q 的后继。
5.使用Python的二维列表来模拟单向链表，每个节点都是一个列表，其第一个元素存储数据，第二个元素存储指向后继节点的指针。若要删除节点a[p]的后继节点，则需执行语句(　　)
A.p＝a[p][1] B.a[a[p][1]][1]＝a[p][1]
C.a[p][0]＝a[a[p][1]][0] D.a[p][1]＝a[a[p][1]][1]
D
解析　语句a[p][1]＝a[a[p][1]][1]是修改节点p的后继指针，使其指向后继节点的后继，以实现删除节点p后继节点的功能。
6.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点，如n＝2时，链表
更新为
部分代码如下：
#读入链表存储在列表s中，head存储链表的头节点，代码略
n＝int(input())
p1＝p2＝head
while p2！＝－1：
　　if n>＝0：
(1)_____________
n－＝1
　　else：
(2)_____________
p2＝s[p2][1]
if p1＝＝head and n>＝0：
　head＝s[head][1]
else：
　　(3)_____________
上述程序段中划线处可选的语句为：
D
①p1＝s[p1][1]　②p2＝s[p2][1]
③s[p1][1]＝s[s[p1][1]][1]
④s[p2][1]＝s[s[p2][1]][1]
则(1)～(3)划线处语句依次为(　　)
A.①③④ B.①④③ C.②①④ D.②①③
解析　本题考查链表的删除。while循环查找待删除节点的前驱节点位置。通过p1和p2遍历链表，前n次只遍历p2，后续同时遍历p1和p2，当p2遍历结束时，p1刚好指向倒数第n＋1个节点。所以(1)处选p2＝s[p2][1]，(2)处选p1＝s[p1][1]。确定p1位置后，执行删除操作。如果p1指向头节点head，要删除头节点，即更新head指向原头节点指针区域对应的节点；否则删除p1的后继节点，即p1的指针区域更新为p1后继节点的指针区域，(3)处应选s[p1][1]＝s[s[p1][1]][1]。
7.在升序链表 a 中插入一个不重复数据 data，仍保持链表的升序状态。使用 python 程序实现插入操作，代码如下：
data＝[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，－1]]
p＝head＝1
data＝int(input())
if data<＝a[head][0]:
　a.append([data，head])
　head＝len(a)－1
else：
B
　　while ①______and data>a[q][0]：
　p＝q
　q＝a[p][1]
　　②______
a.append([data，q])
则划线处的代码为(　　)
A.①p！＝－1　②a[p][1]＝len(a)－1
B.①q！＝－1 ②a[p][1]＝len(a)
C.①q！＝－1 ②a[q][1]＝len(a)－1
D.①p！＝－1 ②a[q][1]＝len(a)
解析　本题考查链表中数据查找和插入操作。p、q 是两个前后相邻的节点。根据 data>a[q][0]，可以推测出①为q！＝－1。循环结束后，应该在p节点之后插入节点，所以②处代码是：a[p][1]＝len(a)。
8.实现在链表 c 中找出最小值 m 的 Python 程序如下：
D
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历，最小值的初值为头节点大小，因此需先移动到下一节点，再与最值进行比较，同时终止遍历的条件是遍历到尾节点马上结束。
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.②④
9.将两个链表a(A→B→C)和b(D→E)按照间隔次序合并为一个链表，并将结果保存到链表a(A→D→B→E→C)中，部分程序如下：
解析　本题考查链表节点的插入操作。程序将节点q插入到节点p的后面，因此q的指针域的值将发生变化，为了链表b正常遍历，应先保存q的后继。插入过程中，由于已经保存了q的后继，因此可以先修改q的指向，再修改p的指向，最后将p移动到原插入节点q的后继。
B
填入方框处的可选代码有：①data[p][1]＝data[q][1]
②data[q][1]＝data[p][1]　③data[p][1]＝q
④data[q][1]＝p　⑤p＝data[p][1]　⑥p＝data[q][1] 已知链表 b 的长度不超过链表 a，则下列选项中，代码顺序正确的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
10.使用链表结构模拟某景区游玩路线，链表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，″分钟″)
解析　本题考查多条链表的遍历。3条链表构建在数组a中，头指针存储在数组head中，需遍历头指针数组，从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i]，变量s存储所有节点游览总时间。(2)(3)遍历链表，并统计各个节点游览时间和，由于当前节点已经计入总时间，因此先要跳转到下一点，将下一节点的时间加入到总时间，注意遍历结束的条件是当遍历到尾节点时，终止遍历。
D
上述程序划线处的可选代码有： ①p＝head
②p＝head[i]　 ③s＋＝a[p][1]　 ④ p＝a[p][2]
则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③ C.②③④ D.②④③
11.有如下Python程序：
from random import *
a＝[[″e″，4]，[″g″，8]，[″h″，5]，[″h″，0]，[″n″，1]，[″o″，7]，[″S″，3]，[″u″，6]，[″Z″，2]]
k＝randint(1，4)*2＋1
p＝q＝6
while k>0：
　　p＝a[p][1]
　　k－＝1
D
while p！＝1：
　q＝a[q][1]
　p＝a[p][1]
print(a[q][0])
解析　本题考查循环链表的操作，根据p＝q＝6可以得出链表为S－h－e－n－g－Z－h－o－u，k的范围为[3，5，7，9]，p和q相差k个节点，p为1时输出a[q][0]，即p指向g，q的可能有h、u、g。
12.使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
C
解析　题图a按绝对值升序排序数据，链表中数据依次为－11，14，16，17，－18，要求改变链接关系，使链表各节点按数据区域中的数值由小到大排列。若链表中只有1个节点，其值无论是正数还是负数，均是最小的数。同时他既是头节点h，也是尾节点t。因此变量p从链表第2个节点开始遍历各个节点，若遍历到负数，则该数绝对值越大，其值就越小，需将该节点从原链表中删除，并移动到头节点的前面，进行的操作是将该前节点p指向原头节点h，同时修改当前位置为头指针。若为正数，将该节点链接到尾节点t的后面。
13.有如下 Python 程序段，为实现在链表中插入一个[6，50]区间内的随机数后，链表 data 中的数据仍然有序。
import random
x＝random.randint(6，50)
print(″在链表 data 中插入一个值为″，x，″的数″)
data＝[[14，1]，[26，4]，[5，0]，[49，－1]，[37，3]]
head＝2; q＝head
while q！＝－1：
if x>data[q][0]：
p＝①______
q＝data[q][1]
else：
break
data.append(②________)
data[p][1]＝len(data)－1
q＝head
while q！＝－1：
print(data[q][0]，end＝'')
q＝data[q][1]
D
解析　本题考查链表的插入。在有序链表中插入一个节点x，x 的范围在6到50之间，故只需要考虑中间插入或者尾插，q 指向的就是小于 x 的最大节点，让插入的节点 x 指向 p 节点的后继节点 q，语句 data[p][1]＝len(data)－1实现让p节点指向新插入的节点 x。
请为①②两处选择正确的程序代码(　　)
A.①data[q][1]　　②[x，p]
B.①data[q][1] ②[x，data[p][1]]
C.① q ②[x，p]
D.①q ②[x，data[p][1]]
14.报数游戏。已知班上有n名学生(用编号1，2，3，……n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。
(1)当n＝12，m＝3时，最后留下的同学的编号是______。
(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①_____________) #将尾节点的指针指向头节点，构成循环单向链表
p＝len(lst)－1
while n>1：
　 for i in range(1，m): #从 1～(m－1)依次报数
p＝lst[p][1]
out＝lst[p][1]
②____________
n＝n－1
print(″最后留下的同学的编号是： ″，lst[p][0])
答案　(1)10　(2)①[n，0]　②lst[p][1]＝lst[out][1]
解析　(1)依次出队的序号为3，6，9，12，4，8，1，7，2，11，5，最后留下10号。
(2)①循环队列的特点是队尾指向队首，因此最后一个学生的编号为n，指针指向0。 ②节点p从最后一个节点开始，range(1，m)循环了m－1次，因此向后遍历了m－1个节点，下一个节点lst[p][1]就是要删除的节点，因此将当前节点的指针指向下一节点的后继，就删除了下一节点。
15.张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。
(1)根据题意，部分的单词库数据逻辑结构如图所示，查找单词”byte”的过程是”binary”→”bit”→”byte”，补充图中空白单元格的值为__________。
列表索引 数据区域 指针区域
0 audio 音频 －1
1 binary 二进制数 6
2 byte 字节 －1
3 cursor 光标 －1
4 access 存取 1
5 cache 高速缓存 3
6 bit 比特 ____▲____
(2)wordlist(data，info)函数实现将词汇数据库 data 以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置，如 info[0]表示字母 a 开头的最小单词在词汇数据库 data 中的位置。实现该功能的程序如下，请在划线处填入合适的代码。
info＝[]
def wordlist(data，info):
　 n＝len(data)
　　for i in range(n)：
data[i].append(－1)
　#data[i]追加一个元素－1
for i in range(n):
　　 　d＝data[i][0]
　　　 ①______________
　　　 if info[k]＝＝－1:
　　　 info[k]＝i
　　　else：
　 　　head＝info[k]
　　　q＝head
　　　while ②____________ ：
　　 　　　p＝q
　　　　　q＝data[q][2]
　　　if q！＝head：
　　 　　　data[p][2]＝i
　　　　　data[i][2]＝q
　　　else：
　　　　　data[i][2]＝head
　　　　　③____________
return data，info
(3)searchword(data，info，key)函数实现单词的查找。程序如下，请在划线处填入合适的代码。
def searchword(data，info，key):
　 k＝ord(key[0])－ord(″a″)
　　head＝info[k]
　　p＝head
　　while p！＝－1：
　 if data[p][0]＝＝key:
　　　　 return ________
　p＝data[p][2]
　　return ″没有找到该单词″
读取词汇数据库，存入列表 data 中，列表的每个元素包含 2 个数据项，分别为英文单词和中文翻译，如 data＝[['audio'，'音频']，['binary'，'二进制数'] …], 数据读取存入的代码略。
info＝[－1] * 26
data，info＝wordlist(data，info)
key＝input(″请输入查找单词：″).lower()
#转化为小写字母
res＝searchword(data，info，key)
print(key，″查找结果是：″，res)
答案　(1)2　(2)①k＝ord(d[0])－ord(″a″)
②q！＝－1 and d>data[q][0]　③info[k]＝i
(3)data[p][1]
解析　本题考查链表的构建、遍历和节点的插入。
(1)采用链表方式存储字母，首字母相同时按升序排序。单词bit的下一个单词为byte，因此其指针区域值为索引2。(2)①将单词d首字母转换为字母表中对应数字，info[0]表示字母 a 开头的最小单词，因此k为字母a－z对应0－25的索引号。②遍历data链表，找到单词d位置。当前节点q从头节点开始，当q值不为－1，且满足d比当前节点数据区域值大。(3)返回单词key对应的中文。每个元素包含英文单词和中文翻译。课时2　链　表
课时目标
1.理解数组和链表的概念和特性。2.掌握数组和链表的基本操作。3.能运用数组和链表编程解决实际问题。
1.链表的概念
(1)链表指的是将需要处理的数据对象以________的形式，通过________串联在一起的一种数据结构。
(2)每个节点一般包括两个区域：____________和____________。
(3)每个链表有个________——head(也称头指针)，是链表的入口，也便于循环链表在数据处理时的边界判断和处理。
(4)链表的形式
链表的形式主要有：____________、____________、____________。
①单向链表：只有一个指针用来指向其________节点。单向链表如下图所示。
②双向链表：有两个指针分别用于指向其__________节点和__________节点。双向链表如下图所示。
③循环链表：________节点和____________节点使用指针链接。循环链表如下图所示。
2.链表的特性
(1)同一链表中每个节点的________均相同，有数据区域和指针区域组成。
(2)每个链表必定有一个________，以实现对链表的引用和边界处理。
(3)链表占用的空间________。
可根据需求增删节点，提高了存储空间的利用率。
3.链表的基本操作
(1)链表的创建
(2)链表节点的访问
链表只能通过头指针进行访问，其他节点通过节点间的指针依次访问。
(3)链表节点的插入与删除
插入操作：
插入datax节点
删除data2节点
(4)链表节点的访问与遍历
访问链表中的节点时，只能通过头指针进入链表并通过指针链接依次访问，直到找到目标位置上的节点。
4.链表的类实现
在Python中，链表除了可以使用列表来实现，还可以使用“类”实现。“类”是一种抽象的数据结构，它将数据及其操作封装在一起。构造单向链表类的具体实现过程如下：
(1)自定义单向链表的节点类：
class Node：　　　#定义单链表节点类
def__init__(self，data，next＝None)：#初始
化节点包含两个域self.data、self.next
　 self.data＝data #self.data域保存数据
　self.next＝next #self.next域保存指针，缺省值为None
(2)构造单向链表类：
class Link：　　　#定义单向链表类Link
　 def __init__(self)：　#初始化空链表
　 self.head＝None #空链表头指针指向为空
例1 对于链表的描述，下列说法不正确的是(　　)
A.同一链表中每个节点的结构均相同
B.每个链表必定有一个头指针
C.链表占用的空间不固定
D.创建的新链表中至少要有一个节点
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　链表不具备的特点是(　　)
A.可随机访问任一节点
B.插入、删除操作时不需要移动元素
C.不必事先估计存储空间
D.所需空间与其长度成正比
例2 使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
A.0　1　2　3 B.3　1　0　2
C.2　0　－1　1 D.2　0　1　－1
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
例3 有如下 Python 程序段：
a＝[[3，1]，[2，2]，[3，3]，[3，4]，[17，5]，[2，6]，[3，－1]]
p＝head＝0
while p！＝－1:
q＝p
while q！＝－1:
t＝q
q＝a[q][1]
if q！＝－1 and a[q][0]＝＝a[p][0]：
　　　　　a[t][1]＝a[q][1]
　　　　　q＝t
p＝a[p][1]
p＝head
while p！＝－1：
print(a[p][0]，end＝' ')
p＝a[p][1]
运行后程序的输出结果是(　　)
A.3　2　17 B.3　2　17　2
C.3　2　17　2　3 D.17
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下 Python 程序段：
def guess(cur)：
q＝cur
p＝a[cur][1]
while p！＝－1：
if a[p][0]＝＝a[cur][0]：
　　　　 a[q][1]＝a[p][1]
else：
　　　　 q＝p
p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur！＝－1：
print(a[cur][0]，end＝″″)
if a[cur][1]！＝－1：
guess(cur)
cur＝a[cur][1]
运行后，则输出的结果是(　　)
A.1234 B.1122 C.11223 D.11224
例4 有两个降序序列的链表 a，b。现将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a，实现数据合并的代码段如下，
a＝[[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b＝[[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a＝head_b＝0
pre＝p＝head_a；q＝head_b
while q！＝－1：
if p！＝－1 and :
pre＝p
p＝a[p][1]
else：
a.append( )
if p＝＝head_a：
　　　　pre＝head_a＝len(a)－1
else：
　　　　a[pre][1]＝
　　　　pre＝len(a)－1
q＝b[q][1]
上述程序段中可选填的语句为：
①a[p][0]>＝b[q][0]　② a[p][0]<＝b[q][0]
③q　④len(a)－1　⑤[b[p][0]，q]
⑥[b[q][0]，p]
则加框处填写的语句依次为(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下 Python 程序：
def lnkid(n，head):
p＝head
while head！＝－1 and ①____________：
p＝head
head＝a[head][1]
return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
a.append([n，head])
head＝len(a)－1
else：
a.append([n，a[p][1]])
②______________
用列表 a 模拟一个降序链表，运行程序，输入自然数 n，则链表增加一个新的节点，要使链表保持降序，则划线①②处代码分别为(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
例5 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如下图所示。
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：兰亭序 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园　兰亭序　想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲：七里香 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序　想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲：想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令A—显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E
Python 代码如下所示，请在划线处填入合适的代码。
data＝[[″十年″，4]，[″淡季动物园″，－1]，[″God Is a Girl″，0]，[″七里香″，1]，[″年少有为″，3]]
head＝2
tail＝1
while True：
cmd＝input(″请输入指令 A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：″)
if cmd＝＝″A″：
cur＝head
while cur！＝－1:
　　　print(data[cur][0]，end＝″″)
　　　 cur＝data[cur][1]
print()
elif cmd＝＝″B″：
song＝input(″请输入歌曲：″)
data.append([song，－1])
if head＝＝－1：
　　　head＝tail＝len(data)－1
else：
　　　①____________
　　　tail＝len(data)－1
elif cmd＝＝″C″：
song＝input(″请输入歌曲：″)
cur＝head
while cur！＝－1 and data[cur][0]！＝song:
　　　　pre＝cur
　　　　cur＝data[cur][1]
if cur！＝－1 and cur！＝head：
　　　②____________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　　③____________
elif cmd＝＝″D″：
if head＝＝tail:
　　　　head＝tail＝－1
else：
　　　④__________
elif cmd＝＝″E″：
break
听课笔记　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　　)
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
1.在单向链表中，增加头指针的目的是(　　)
A.标识表节点中首节点的位置
B.算法实现上的方便
C.使单向链表至少有一个节点
D.说明单向链表是线性表的链式存储实现
2.下列关于链表的叙述中，正确的是(　　)
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
3.某单向链表如下图所示，若要将数据 data3 和data4 同时从链表中移除，至少需要修改节点指针的数量是(　　)
A.1 B.2 C.3 D.4
4.某 Python 程序段如下：
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]！＝h：
print(b[p][0]，end＝″，″)
p＝b[p][1]
print(b[p][0])
运行该程序段，输出的内容为 (　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
5.下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。
#建立链表 link1，代码略
key＝int(input(″输入要删除的数据：″))
head＝0
while link1[head][0]＝＝key and head！＝－1:
　head＝link1[head][1]
p＝q＝head
if head＝＝－1：
　 print(″全部数据删除″)
else：
　　q＝link1[q][1]
　　while ①____________：
　　 　if link1[q][0]＝＝key：
　　　　 　②____________
　　　else：
　 　　　　p＝link1[p][1]
　　 　q＝link1[q][1]
则划线①②处的代码分别为(　　)
A.①link1[q][1]！＝－1 ②link1[p][1]＝link1[q][1]
B.①link1[q][1]！＝－1 ②link1[q][1]＝link1[p][1]
C.①q！＝－1 ②link1[q][1]＝link1[p][1]
D.①q！＝－1 ②link1[p][1]＝link1[q][1]
6.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。
若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1
链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
7.在一个单向链表(如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是(　　)
A.tail所指节点的data3值赋为r所指节点的data4值
B.r所指节点的next值赋为tail
C.r所指节点的next值赋为－l
D.tail所指节点的next赋为r，r所指节点的next值赋为－l
8.有如下Python程序段：
n＝int(input(″输入一个数：″))
a＝[]；head＝－1
while n>0：
r＝1－n%2
n∥＝2
a.append([r，head])
head＝len(a)－1
p＝head
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
运行上述程序段后，如果输入11，则输出结果是(　　)
A.1101 B.1011 C.0010 D.0100
9.找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下：
#链表a中存储了序列数据，head为其头指针，代码略
pre＝p＝head
maxpre＝maxp＝head
while p！＝－1：
if a[p][0]>a[maxp][0]:
maxp＝p; maxpre＝pre
pre＝p
p＝a[p][1]
if maxp＝＝head:
head＝a[head][1]
elif maxp！＝pre：
　　①____
a[pre][1]＝maxp
②____
#遍历输出链表 a
划线处的代码应为(　　)
A.①a[maxp][1]＝a[maxpre][1]
②a[maxp][1]＝a[p][1]
B.①a[maxp][1]＝a[maxpre][1]
②a[maxp][1]＝p
C.①a[maxpre][1]＝a[maxp][1]
②a[maxp][1]＝a[p][1]
D.①a[maxpre][1]＝a[maxp][1]
②a[maxp][1]＝p
10.某医院每天提前发放100个预约号，考虑到老年人身体原因，预约病人按照以下规则进行就诊：
①老年人(年龄>＝60岁)比非老年人优先就诊。
②老年人按年龄从大到小的顺序就诊，年龄相同的按预约顺序就诊。
③非老年人按预约顺序就诊。
小王根据以上规则编写了一个Python程序，程序运行时，实时读取病人预约数据，并根据以上规则，实时调整并显示当前诊顺序，程序运行界面如图所示。
请输入病人的信息：40 当前就诊顺序为：40 请输入病人的信息：15 当前就诊顺序为：40　15 请输入病人的信息：67 当前就诊顺序为：67　40　15 请输入病人的信息：75 当前就诊顺序为：75　67　40　15 请输入病人的信息：30 当前就诊顺序为：75　67　40　15　30
(1)如图所示，若当前就诊顺序为“75 67 40 15 30”，下一位预约病人年龄为60，则就诊顺序变为__________________。
(2)实现上述功能的代码如下，请在划线处填入合适的代码。
#遍历链表data，头指针为head
def visit(data，head)：
　 cur＝head
　 while cur！＝－1：
　　　print(data[cur][0]，end＝″ ″)
　　　cur＝data[cur][1]
　　print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分别表示链表头节点和尾节点所在位置
for i in range(100)：
#为了简洁，本程序只输入、存储病人的年龄信息
age＝int(input(″请输入病人的信息：″))　
cur＝head
if age>＝60：
while cur！＝－1 and data[cur][0]>＝age: #查找第一个数据域小于age的节点
　　　pre＝cur
　　　①______________
　if cur＝＝head：　#在头节点插入新节点
　　　data.append([age，cur])
　　　head＝len(data)－1
　else：# 在链表中间插入新节点
　　　data.append([age，cur])
　　　②______________
　　if cur＝＝－1：　# 更新尾指针位置
　　　　tail＝len(data)－1
　else： #直接插在链表尾节点后
　　data.append([age，－1])
　　if head＝＝－1：　# 添加第一个节点
　　　　head＝tail＝0
　　else：
　　　　
　　　　tail＝len(data)－1
　print(″当前就诊顺序为：″)
visit(data，head)
课时2　链　表
知识梳理
1.(1)节点　指针　(2)数据区域　指针区域　(3)表头　(4)单向链表　双向链表　循环链表　①后继　②前驱　后继　③第一个　最后一个
2.(1)结构　(2)头指针　(3)不固定
例题精析
例1　D　[本题考查链表的基本性质。A选项链表节点包含数据区域和指针区域，每个节点中的数据区域中数据类型是相同的。B选项访问链表的某一节点，只能从头指针开始，依次访问。C选项链表通过指针相连，相信节点存储时不需要连续空间，因此链表空间是不固定的。D选项可以空链表，数据区域为空，头指针为－1。]
变式训练　A　[本题主要考查的是链表的特点。访问链表中的某一节点时，只能从头指针开始，通过指针链接依次访问。因此答案为A。]
例2　C　[本题考查链表的构建和遍历。L的后继节点为O，因此其指针区域值为1；O的后续为V，指针区域值为0; V的后续为E，指针区域值为2；E为尾节点，因此指针区域值为－1。 ]
变式训练　B　[本题考查链表的遍历。A选项当前节点为p，当遍历到节点为空时停止遍历，因此遍历结束后，p节点为空，其前驱t为尾节点。B选项当前节点为p，若当前节点的指针区域值为－1，结束遍历，那么当前节点p为尾节点。C选项当前节点从头节点开始遍历，a[a[p][1]]指当前节点的后继节点，若该节点的指针区域值为－1，表示该节点为尾节点，当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点，因此len(a)的值可能大于节点总数。]
例3　A　[本题考查链表的操作。当a[q]节点上的值与a[p]节点上的值相同时，q指针往后移一位。程序的功能是将与p指针所指示的节点值相同的a[q]节点删除。指针t的作用是维护了去重后链表最后一个节点的位置。输出链表的所有非重复节点。]
变式训练　A　[本题考查链表节点的删除。在自定义函数guess中，当前节点p从cur节点的后继开始，如果后面的元素与cur节点元素值相等，则删除节点p，因此是从当前节点链表中删除重复的元素。]
例4　A　[本题考查链表元素的遍历和插入操作。程序的功能将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a。分别遍历两个链表，若链表a当前元素值a[p][0]大于等于链表 b当前元素值b[q][0]，则链表a向后遍历，否则把链表 b当前元素值b[q][0]插入到链表a当前元素前面。由于是要把链表 b 中的数据合并到链表 a，因此链表b遍历完成后，结束程序。]
变式训练　B　[本题考查链表的插入。①自定义函数lnkid的功能是查找n在链表中插入位置，head在不断地向后移动，因此n将和a[head][0]进行比较，当比a[head][0]小时，不断地向后查找位置。②语句p＝lnkid(n，head)将返回在节点p的后面插入新的数n，因此将修改a[p]节点指针区域值为当前插入点索引。]
例5　①data[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]
③tail＝pre
④head＝data[head][1]
解析　本题考查链表的操作。①输入“B”则可以自行输入歌曲并添加到歌单，新节点插入在尾节点的后面，因此原尾节点应指向新插入的节点，同时更新尾节点。②输入“C”则可以将指定的歌曲置顶，data[cur][0]值为song表示找到节点cur，pre为cur节点的前驱，将cur移动到头节点前面，因此需要3步，第1步是将cur的前驱pre指向cur的后继，第2步是将cur指前原头节点，第3步是设置新的头节点为cur。③若cur是原尾节点tail，将cur修改为头节点后，新的尾节点为cur的前驱。④输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除，条件head＝＝tail成立表示链表中只有一个节点，否则将头指针向后移动，删除头节点。
变式训练　A　[本题考查链表的遍历、插入和删除操作。A选项删除该链表中的最后一个节点，需修改最后一个节点的前驱节点指针域，因此需遍历多个节点。B选项只需修改头指针。C选项修改当前节点的指针值指向原头节点，并修改头指针为当前节点。D选项让原尾节点指向当前节点，并修改尾节点为当前节点。 ]
随堂检测
1.B　[在单向链表中，一定有一个头指针，以实现对链表的引用和边界处理，因此，增加头指针的目的是算法实现上的方便，因此，答案为B。]
2.D　[单链表存储方式地址不连续，元素顺序是任意的。因此，答案为D。]
3.A　[只需修改data2的指针区域值修改为data4的指针区域值。]
4.C　[本题考查循环链表的遍历。h表示头节点，值为0，在链表中有一个节点指向0，因此判定该链表为循环链表。当前节点p从头节点开始遍历，若当前节点指针区域值为头节点，结束遍历，即遍历到尾节点终止循环，没有输出尾节点的值，循环结束后，再次输出尾节点的值。]
5.D　[本题考查链表节点删除的算法实现。先判断当前节点的数据域是否为 key，如果是，则删除当前节点，即将 p节点的指针域指向 q 节点的指针域，如果不是，则将 p 指向下一个节点，q 也指向下一个节点。最后，程序通过 while 循环遍历链表并输出每个节点的数据域。]
6.B　[本题考查的知识点是链表元素的插入。链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。]
7.D　[本题主要考查链表的操作。链表中尾节点的next指针为－1，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是：tail所指节点的next赋为r，r所指节点的next值赋为－1。]
8.D　[本题考查链表的插入和进制转换。程序的功能是十进制数转成二进制数，并把结果取反。代码a.append([r，head]); head＝len(a)－1的功能利用头插法生成链表。]
9.D　[本题考查链表。先查找序列中最大数的位置maxp和该节点的前驱节点maxpre，pre 为最后一个节点位置。再删除最大数节点，分两种情况，最大数节点为第一个节点或其他位置节点。如果是其他位置节点，需将该最大数节点的前驱节点指针区域指向该最大数节点的后继节点位置，即a[maxpre][1]＝a[maxp][1]。最后将最大数节点插入链尾，原最后一个节点指针区域需指向最大数节点，最大数节点为新的最后一个节点，其 指针区域为－1，即 p，所以②a[maxp][1]＝p。]
10.(1)75 67 60 40 15 30
(2)①cur＝data[cur][1]
②data[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本题考查链表的遍历和插入操作。(1)老年人(年龄>＝60岁)比非老年人优先就诊，老年人按年龄从大到小的顺序就诊，因此将60插入到40前，结果是75 67 60 40 15 30。(2)当年龄大于等于 60岁时，按年龄降序插入到链表，当年龄小于60岁时，按预约顺序插入链表。①从头节点开始依次遍历，根据数据值找到第一个比当前数据小的节点cur，pre为前驱节点。②在链表中间插入新节点时，需要在插入节点后，更改前驱节点的指针区域。③直接插在链表尾节点后，尾节点变成了前驱节点，更改前驱节点的指针区域。

展开更多......

收起↑