第5课 链表1——单向链表-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第5课　链表1——单向链表(见学生用书P32) ——2.2　链表，教材P46～56 1. 掌握链表的概念，了解链表组织、存储结构的原理与特性。　2.能根据问题特点规划节点的数据域和指针域。　3.完成创建链表以及访问、删除、插入链表节点的操作。 1．链表的概念与特性 (1)链表的概念 ①链表指的是将需要处理的数据对象以　节点　的形式，通过　指针　串联在一起的一种数据结构。指针就是下一个节点的存储地址(索引)。 ②链表中的每个节点一般由“　数据区域　”和“　指针区域　”两部分构成。数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址。 ③某个节点前面的相邻节点称为该节点的　前驱节点　；后面的相邻节点称为该节点的　后继节点　。 (2)链表的特性 ①同一链表中每个节点的结构均　相同　。 ②每个链表必定有一个　头指针　，以实现对链表的引用和边界处理。 ③链表占用的空间　不固定　。 2．链表的基本操作 (1)链表的创建 首先要根据问题特点规划节点的数据域和指针域，然后根据规划创建一个空链表。 (2)链表节点的访问 链表中的节点通过节点间的指针依次访问，当需要访问某个位置的节点元素时，只能通过头指针进入链表并通过节点间的链接关系一个一个往下访问，直到找到指定位置的节点。与数组相比，其节点的访问效率较低。 (3)链表节点的插入与删除 ①链表节点的插入：根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。 ②链表节点的删除：将需删除的节点的前驱节点和其后继节点直接相连。 单向链表：只有一个指针用来指向其后继节点，单向链表如图所示： 1．链表的创建： ①创建空链表list list＝[] head＝－1 ②直接创建多节点链表list list＝[[5，1]，[6，2]，[7，3]，[8，－1]] head＝0 ③利用已有列表a，创建链表list a＝[i＋1 for i in range(6)] list＝[] for i in range(len(a))： list.append([a[i]，i＋1]) list[len(a)－1][1]＝－1 head＝0 2．链表的遍历与节点查找 (1)链表的遍历 ①程序1 a＝[[3，2]，[2，3]，[7，1]，[1，－1]] p＝head＝0 while p！＝－1： print(a[p][0]，end＝＂－>＂) p＝a[p][1] 运行结果：3－>7－>2－>1－> ②程序2 a＝[[3，2]，[2，3]，[7，1]，[1，－1]] p＝head＝0 while a[p][1]！＝－1： print(a[p][0]，end＝＂－>＂) p＝a[p][1] print(a[p][0]) 运行结果：3－>7－>2－>1 (2)链表的节点查找 a＝[[7，3]，[5，0]，[2，1]，[9，－1]] head＝2 key＝int(input()) p＝q＝head while p！＝－1 and a[p][0]<key： q＝p p＝a[p][1] 运行结束后，p指向数值域大于等于key的链表中最小位置；q是p的前驱节点 3．链表节点的插入和删除 (1)链表节点的插入 ①在头节点之前插入节点 程序实现：新节点数值域为4。 list＝[[5，1]，[6，2]，[7，3]，[8，－1]] head＝0 list.append([4，head]) head＝len(list)－1 　　②在链表中间插入新节点(在链表尾部插入同样适用)。 第1步：将待插入节点(新节点)的指针指向后继节点。 第2步：将前驱节点的指针指向待插入节点(新节点)。 程序实现：在p节点之后插入新节点，新节点数值域为4。 list＝[[5，1]，[6，2]，[7，3]，[8，－1]] head＝0 p＝2 list.append([4，list[p][1]]) list[p][1]＝len(list)－1 (2)链表节点的删除 ①删除头节点 程序实现： list＝[[5，1]，[6，2]，[7，3]，[8，－1]] head＝0 head＝list[head][1] ②删除中间节点 程序实现：删除p节点之后的节点。 list＝[[5，1]，[6，2]，[7，3]，[8，－1]] head＝0 p＝1 list[p][1]＝list[list[p][1]][1] 　　下列关于链表的说法中，不正确的是(　C　) A．链表指的是将需要处理的数据对象以节点形式，通过指针串联在一起的一种数据结构 B．节点的数据区域用于保存实际需要处理的数据元素 C．节点的指针区域用来保存当前节点的存储地址 D．某个节点前面的相邻节点称为前驱节点，后面的相邻节点称为后继节点 【解析】 实现链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，一个作为指针域存储后继节点在列表中的索引，不是当前节点的存储地址，故选项C错误。 变式1链表不具备的特点是(　A　) A．可随机访问任一节点 B．插入、删除操作时不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 【解析】 访问链表中的某一节点时，只能从头指针开始，通过指针链接依次访问。故选项A符合题意。 　　在一个单向链表中，若在尾指针tail所指节点之后插入新节点(r所指节点，如图所示)，则执行的正确操作是(　D　) A．tail所指节点的值赋为r所指节点的值 B．r所指节点的next值赋为tail C．r所指节点的next值赋为－1 D．tail所指节点的next值赋为r，r所指节点的next值赋为－1 【解析】 在尾指针后面插入新节点，先将尾指针tail指向新节点，然后将新节点的指针区域设为－1，以使新节点r成为新链表的尾节点。 变式1使用Python的二维列表来模拟单向链表，每个节点都是一个列表，其第一个元素存储数据，第二个元素存储指向后继节点的指针。若要删除节点p的后继节点，则需执行语句(　D　) 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] 【解析】 语句a[p][1]＝a[a[p][1]][1]是修改节点p的后继指针，使其指向后继节点的后继，以实现删除节点p后继节点的功能。 　　有如下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] 执行该程序段后，输出的结果是(　B　) A．1－>2－>3－>5 B．1－>2－>3－>5－> C．1－>2－>3－>5－>6 D．1－>2－>3－>5－>6－> 【解析】 遍历除尾节点的所有节点，输出遍历到的节点的数据域，不换行输出并以”－>”结束，没有输出尾节点，输出前面4 个节点的数据域，并以”－>”结束，故答案为1－>2－>3－>5－>，选项B正确。 变式1有如下Python 程序段： a＝[[7，3]，[5，0]，[2，1]，[9，－1]] head＝2 key＝int(input()) p＝q＝head while p！＝－1 and a[p][0]<key： q＝p p＝a[p][1] if p＝＝head： a．append([key，head]) head＝len(a)－1 else： 　　a．append([key，p]) 　　a[q][1]＝len(a)－1 print(a[－1]) 执行该程序段后，若输入2，则输出的结果是(　C　) A．[2，－1]　　　　　　B．[2，1]　　　　　　C．[2，2]　　　　　　D．[2，3] 【解析】 本题首先建立了一个如图1 所示的升序链表： 接下来从head 开始，查找key 插入的位置。若key>a[p][0]，则继续向后找。本题key＝2，一开始就不满足循环条件，2 应插到链表头部。首先向列表中追加key，并将指针指向head，同时调整head 指针位置，如图2 所示。故a[－1][0]＝2，指针a[－1][1]＝2，选项C正确。 变式2 有如下Python程序段： import random a＝[[1，3]，[3，4]，[5，－1]，[2，1]，[4，2]] x＝random.randint(2，4) p＝q＝0 while a[q][0]<x and a[q][1]！＝－1： p＝q q＝a[q][1] a[p][1]＝a[q][1] q＝0 while q！＝－1： print(a[q][0]，end＝” ”) q＝a[q][1] 执行该程序段后，运行结果可能是(　C　) A．1 3 5 2 B．2 3 4 5 C．1 2 4 5 D．1 3 5 4 【解析】 列表a中的数据a[i][0]表示数据，a[i][1]表示后继节点，列表a根据节点构成一有序序列：1，2，3，4，x表示随机生成的2、3、4中任意一个数，while循环找到值x所在的位置，然后通过语句a[p][1]＝a[q][1]删除该节点，最后输出有序序列，所以结果必须为升序序列，然后有可能删除了2、3、4中的任意一个数。 　　2023·遂昌中学检测在升序链表a 中插入一个不重复数据data，但仍保持链表的升序状态。使用Python 程序实现插入操作，代码如下： a＝[[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： 　　q＝a[p][1] 　　while ①　　　　　　 and data>a[q][0]： p＝q q＝a[p][1] 　　②　　　　　　　 　　a．append([data，q]) 则横线处的代码为(　B　) 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) 【解析】 根据代码q＝a[p][1]可知，p、q 是二个相邻节点，p 在前，q 在后，根据data>a[q][0]，可以推测出①：q！＝－1；条件循环结束后，应该在p 节点之后插入节点，所以②处代码是：a[p][1]＝len(a)。综上可知，选项B正确。 变式1有如下Python程序段，为实现在链表中插入一个[6，50]范围内的随机数后，链表data中的数据仍然有序。那么该程序段中①、②处填入的代码分别为(　D　) 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] A．①data[q][1]　②[x，p] B．①data[q][1]　②[x，data[p][1]] C．①q　②[x，p] D．①q　②[x，data[p][1]] 【解析】 根据题意可知将x插入到链表中： ①遍历链表，p跳转到q的位置，q跳转型Jq的后继节点上，最终找到要插入的位置，即在q之前。 ②构建新节点[new，q]或者[new，data[p] [1]]。 ③修改q的前驱节点的后继指针指向新节点。 故选项D正确。 |随|堂|检|测| 1．下列关于链表的说法中，正确的是(　A　) A．每个链表的表头一定有一个头指针，以实现对链表的引用和边界处理 B．在单向链表中，最后一个节点的指针指向第一个节点 C．链表一旦创建好后，它占用的空间将固定 D．链表的头指针指向第一个节点，因此不能删除第一个节点 【解析】 链表的特性是有一个头指针，以实现对链表的引用和边界处理，选项A正确。 2．在Python 中，采用列表模拟链表，data[p][0]为数据区域，data[p][1]为指针区域，当单向链表存储索引为p的节点(非尾节点)，前驱节点存储索引为f，则删除指针p 指向的节点，正确的操作是(　C　) A．data[f][1]＝p B．p＝data[p][1] C．data[f][1]＝data[p][1] D．data[p][1]＝f 【解析】 p为当前节点的索引，f为前驱节点的索引。删除指针p指向的节点，即删除当前节点，只要把p节点指向后继节点的指针data[p][1]的值赋给原来指向p节点的前驱节点f的指针data[f][1]，就能实现删除指针p指向的节点。 3．现用链表lb 存储了一批会员信息，链表每个节点中的数据依次为会员名、手机号、会员积分和节点指针，数据存储形式如[[”张三”，”13282825678”，280，1]，[”小明”，”13256787678”，500，3]，…]。现要实现删除某个手机号的会员节点，已知链表头指针head 与要删除会员手机号phone，实现删除节点的Python代码如下： p＝head q＝p while p！＝－1： if lb[p][1]＝＝phone： if p＝＝head： else： q＝p 上述程序段中加框处可选的代码有： ①head＝lb[p][3]　②p＝lb[p][3]　③lb[p][3]＝lb[q][3]　④lb[q][3]＝lb[p][3] 下列选项中代码顺序正确的是(　C　) A．①③② B．②④① C．①④② D．③④② 【解析】 该程序的算法思路为：遍历链表，查找待删除节点，找到后，根据该节点为第一个节点或中间节点执行不同的删除操作。 4．有如下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] p＝a[p][1] else： 　　q＝p 　　p＝a[p][1] return a＝[[1，1]，[2，2]，[3，3]，[3，4]，[4，5]，[3，6]，[5，－1]] head＝0 cur＝head while a[cur][1]！＝－1： guess(cur) cur＝a[cur][1] cur＝head while cur！＝－1： print(a[cur][0]，end＝””) cur＝a[cur][1] 执行该程序段后，输出的结果是(　D　) A．12435 B．54321 C．53421 D．12345 【解析】 原链表状态如下： guess()函数的功能是将链表中与cur节点值相同的节点删除， 如下图所示： q指针是前驱节点指针，p指针从cur指针的下一个节点开始遍历， 故选项D正确。 学科网（北京）股份有限公司 $$